שאלה במערכים
נתונים שני מערכים שממוינים בסדר עולה ממש,צריך למשש שיטה בוליאנית שתחזיר True אם ישנם שני תאים (תא מכל מערך) שסכומם זהה לערך מסוים. מצאתי שתי דרכים 1. להשוות/לבדוק את התא הראשון במערך הראשון עם כל התאים במערך השני, לעבור לתא השני במערך הראשון ולבדוק עם כל התאים במערך השני וכך הלאה. 2. לבדוק במערך השני בעזרת חיפוש בינארי אם יש תא שמתאים לתא הראשון שבמערך הראשון ואז לעבור לתא השני במערך הראשון ושוב לבדוק בעזרת חיפוש בינארי עם הנתונים שכבר ידועים מהחיפוש הראשון וכך הלאה. הפתרון הראשון הוא בסיבוכיות של n^2 והשני nlogn אני כמעט בטוח שאנחנו אמורים לממש את השיטה בסיבוכיות של n או פחות. למישהו יש רעיון או כיוון ?
נתונים שני מערכים שממוינים בסדר עולה ממש,צריך למשש שיטה בוליאנית שתחזיר True אם ישנם שני תאים (תא מכל מערך) שסכומם זהה לערך מסוים. מצאתי שתי דרכים 1. להשוות/לבדוק את התא הראשון במערך הראשון עם כל התאים במערך השני, לעבור לתא השני במערך הראשון ולבדוק עם כל התאים במערך השני וכך הלאה. 2. לבדוק במערך השני בעזרת חיפוש בינארי אם יש תא שמתאים לתא הראשון שבמערך הראשון ואז לעבור לתא השני במערך הראשון ושוב לבדוק בעזרת חיפוש בינארי עם הנתונים שכבר ידועים מהחיפוש הראשון וכך הלאה. הפתרון הראשון הוא בסיבוכיות של n^2 והשני nlogn אני כמעט בטוח שאנחנו אמורים לממש את השיטה בסיבוכיות של n או פחות. למישהו יש רעיון או כיוון ?