שלום, קיבלתי את האלגוריתם הבא:

נתון: שני המערכים ממוינים.

האלגוריתם בעצם מקבל מספר 2 מערכים ומספר num . הוא בודק האם יש זוג מספרים (אחד מarr1 והשני מ arr2)

שסכומם שווה לnum

ביקשו ממני לרשום מהי הסיבוכיות שלו, הנחתי שהיא O(n²)

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

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

אם מישהו יכול להמליץ על פתרון אחר , יתקבל בברכה

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

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

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

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

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

אויי מצטער, שכחתי לציין את הנתון הזה ששני המערכים ממוינים..

אפשר לקבל את הרעיון איך לכתוב את האלגוריתם בסיבוכיות של n

תודה על התגובה.

תתחשוב על לעבור על מערך אחד מהההתחלה לסוף ועל האחר מהסוף להתחלה.