שאלה

[Brk]

נתקלתי בשאלה הבאה: דומה לקצת לשאלה 4 שהופיע בעבודה 6 רק יותר קשה לטעמי. נתון מערך בגודל n הצע אלגוריתם יעיל מבחינת סיבוכיות זמן . המכריע האם קיימים במערך שלושה איברים במערך x,y,z כך ש: x+y=z.שלושת האיברים אינם נתונים ונמצאים במערך עצמו.
האיברים במערך הם שלמים

יש למישהוא רעיון איך לפתור את זה ?

[eliorar]

מה האיברים במערך? שלמים? בטווח מסויים?

[Brk]

מה האיברים במערך? שלמים? בטווח מסויים?

שלמים

[rubichi]

אני חושב שהדבר הראשון שמתבקש הוא למיין את המערך ב nlogn
כעת, לאחר שהוא ממויין אני מצליח לחשוב על לעבור על כל הזוגות ועבור כל זוג לחפש חיפוש בינארי את הסכום שלהם -O(n^2(logn)) I

[Brk]

אני חושב שהדבר הראשון שמתבקש הוא למיין את המערך ב nlogn
כעת, לאחר שהוא ממויין אני מצליח לחשוב על לעבור על כל הזוגות ועבור כל זוג לחפש חיפוש בינארי את הסכום שלהם -O(n^2(logn)) I

זה לא ממש אופטימלי אם זה יותר מn בריבוע?

[rubichi]

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