פורסם 2009 במאי 2416 שנים שלום, קיבלתי את האלגוריתם הבא: נתון: שני המערכים ממוינים. האלגוריתם בעצם מקבל מספר 2 מערכים ומספר num . הוא בודק האם יש זוג מספרים (אחד מarr1 והשני מ arr2) שסכומם שווה לnum ביקשו ממני לרשום מהי הסיבוכיות שלו, הנחתי שהיא O(n²) ובנוסף לפתור את התרגיל בסיבוכיות יעילה יותר מזו, הנה הפתרון שלי: (רציתי רק לדעת אם הוא אכן בסיבוכיות קטנה מזו שאלגוריתם הראשון, פשוט הנושא הזה נורא קשה לי אני ממש מסתבך איתו), תודה. אם מישהו יכול להמליץ על פתרון אחר , יתקבל בברכה מה שאני עשיתי בעצם היה לשלב את זה עם חיפוש בינרי..
פורסם 2009 במאי 2416 שנים הרעיון של חיפוש בינארי נשמע טוב, אבל בשביל זה אתה צריך ש-arr2 יהיה ממוין. כמובן אתה יכול לכתוב אלגוריתם שקודם כל ימיין את המערכים, ולאחר מכן יפעיל את הפונקציה (וזה יהיה יותר יעיל מ-n2).אבל אם המערכים ממויינים, נראה שהקוד שלך סבבה (לא התעמקתי בו). הסיבוכיות, אגב, היא nlogn, אבל אם אתה יכול להניח מראש ששני המערכים ממויינים, אז אפשר גם לכתוב משהו בסיבוכיות n.
פורסם 2009 במאי 2416 שנים מחבר הרעיון של חיפוש בינארי נשמע טוב, אבל בשביל זה אתה צריך ש-arr2 יהיה ממוין. כמובן אתה יכול לכתוב אלגוריתם שקודם כל ימיין את המערכים, ולאחר מכן יפעיל את הפונקציה (וזה יהיה יותר יעיל מ-n2).אבל אם המערכים ממויינים, נראה שהקוד שלך סבבה (לא התעמקתי בו). הסיבוכיות, אגב, היא nlogn, אבל אם אתה יכול להניח מראש ששני המערכים ממויינים, אז אפשר גם לכתוב משהו בסיבוכיות n.אויי מצטער, שכחתי לציין את הנתון הזה ששני המערכים ממוינים..אפשר לקבל את הרעיון איך לכתוב את האלגוריתם בסיבוכיות של nתודה על התגובה.
ארכיון
דיון זה הועבר לארכיון ולא ניתן להוסיף בו תגובות חדשות.