חיפוש

עזרה

הרשמה

התחברות

עדכונים

תיכנות
UnderWarrior Forums : תיכנות

נושא: אלגוריתם יעיל

כותב

הודעה

<< נושא קודם | נושא הבא >>

one21
משתמש מתחיל

הצטרף / הצטרפה: 06 June 2007
משתמש: מנותק/ת
הודעות: 1

נשלח בתאריך: 06 June 2007 בשעה 17:23

| IP רשוּם

יש לי מטלה לכתוב שיטה שמקבלת שני מערכים של מספרים ממוינים ומספר n, ובודקת האם יש שני מספרים (כל אחד ממערך אחר) ששווים למספר n. האם יש דרך לכתוב אותה ביעילות גבוהה יותר מזמן ריצה של ( O(n log n? ומהי?

חזרה לתחילת העמוד

צחי@
משתמש חבר

הצטרף / הצטרפה: 02 January 2007
מדינה: Israel
משתמש: מנותק/ת
הודעות: 209

נשלח בתאריך: 06 June 2007 בשעה 18:37

| IP רשוּם

אפשר ביעילות

קוד:

log(k*m)

כאשר k הוא גודל המערך הראשון ו-m הוא גודל המערך השני.

1. חיפוש בינארי על המערך הראשון בגודל k -
   אם לא נמצא המספר n - תחזיר תשובה שהמספר לא נמצא בשני המערכים יחדיו.
2. חיפוש בינארי על המערך השני בגודל m -
   אם לא נמצא המספר n - תחזיר תשובה שהמספר לא נמצא בשני המערכים יחדיו.
           אחרת - תחזיר תשובה חיובית.

יעילות:
חיפוש בינארי על מערך ממויין מבוצע ב-log של גודל הקלט, ולכן 2 חיפושים על מערכים בגודל m ו-k

קוד:

log(k) + log(m) = log(k*m)

חזרה לתחילת העמוד

guest
אורח

הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647

נשלח בתאריך: 06 June 2007 בשעה 20:28

| IP רשוּם

שזה בקיצור logn ולא n*logn

חזרה לתחילת העמוד

עודד
אורח

הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647

נשלח בתאריך: 09 June 2007 בשעה 17:25

| IP רשוּם

זאת השיטה המקורית:

קוד:

public boolean what (int [] arr1, int [] arr2, int num)
{
for (int i=0; i<arr1.length; i++)

for (int j=0; j<arr2.length; j++)

if (arr1 + arr2[j] == num)

return true;

return false;
}

לא הבנתי איך מה שצחי הציע פותר את זה

חזרה לתחילת העמוד

guest
אורח

הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647

נשלח בתאריך: 09 June 2007 בשעה 19:44

| IP רשוּם

אתה אמרת בתיאור הראשוני שלך שני מספרים ששוווים ל-N, לא שני מספרים שסכומם N...

אתה יכול לצמצם את החיפושים שלך לכך שאם הסכום עבר את N לעבור לערך הבא במערך הראשון... אבל זה עדיין N^2

אהממ...הצעה לשיפור בסדר גודל ל-N*logn
עבור כל איבר במערך הראשון לבצע חיפוש בינארי של N פחות האיבר במערך השני...

שזה אני מניח מה שהגעת אליו...

אתה יכול גם מכיוון שזה מערך ממוין לא לבדוק מספר אם הוא זהה לקודמו...

באופן עקרוני (ולא עצלני) אתה יכול גם לסמן עד איזה אינדקס לחפש, לדוגמא, אם מצאת בחיפוש הבינארי מספר קטן מהמספר שאתה מחפש כרגע אין סיכוי שהוא יתאים בחיפושים הבאים...

(רק הבהרתי את העניינים)

חזרה לתחילת העמוד

yigael_o
משתמש מתחיל

הצטרף / הצטרפה: 25 January 2007
מדינה: Israel
משתמש: מנותק/ת
הודעות: 30

נשלח בתאריך: 12 June 2007 בשעה 15:01

| IP רשוּם

יש דרך.

האלגוריתם לינארי. תרוץ על מערך אחד מהתחלה לסוף ובשני מהסוף להתחלה. זה סך הכל רמז. תחשוב על זה, אם אתה לא מוצא את השיטה אני אסביר לך בפירוט.

תזכור שהאלגוריתמים ממוינים.

חזרה לתחילת העמוד

shoshan
מנהל האתר

הצטרף / הצטרפה: 16 July 2005
מדינה: Israel
משתמש: מנותק/ת
הודעות: 4637

נשלח בתאריך: 12 June 2007 בשעה 15:09

| IP רשוּם

האלגוריתמים לא ממוינים, המערכים ממוינים...

בכל מקרה, כבר שלחתי את הפתרון הזה (o(n)) ומחקתי כדי לתת לאנשים להרהר, שים לב אם עברת את N ומה צריך לעשות אז...

__________________
עד מתי רשעים יעלוזו?

עַל כֵּן אֶמְאַס וְנִחַמְתִּי עַל עָפָר וָאֵפֶר.

חזרה לתחילת העמוד

אם ברצונך להגיב לנושא זה עליך קודם להתחבר
אם אינך רשום/ה כבר עליך להרשם

גרסת הדפסה

אינך יכול/ה לשלוח נושאים חדשים בפורום זה
אינך יכול/ה להגיב לנושאים בפורום זה
אינך יכול/ה למחוק את הודעותיך ותגוביך בפורום זה
אינך יכול/ה לערוך את הודעותיך ותגובותיך בפורום זה
אינך יכול/ה לצור סקרים בפורום זה
אינך יכול/ה להצביע בסקרים בפורום זה