עמוד 1 מתוך 1

שאלה

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

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

Re: שאלה

הודעהפורסם: 11:12 16/07/2010
על ידי eliorar
מה האיברים במערך? שלמים? בטווח מסויים?

Re: שאלה

הודעהפורסם: 11:48 16/07/2010
על ידי Brk
eliorar כתב:מה האיברים במערך? שלמים? בטווח מסויים?


שלמים

Re: שאלה

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

Re: שאלה

הודעהפורסם: 12:11 16/07/2010
על ידי Brk
rubichi כתב:אני חושב שהדבר הראשון שמתבקש הוא למיין את המערך ב nlogn
כעת, לאחר שהוא ממויין אני מצליח לחשוב על לעבור על כל הזוגות ועבור כל זוג לחפש חיפוש בינארי את הסכום שלהם -O(n^2(logn)) I


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

Re: שאלה

הודעהפורסם: 08:11 17/07/2010
על ידי rubichi
נכון שזה זמן ריצה גדול אבל אני חושב שהדרישה היא גדולה, ובמקום לעשות את זה בn^3 כמו בתפרון הכי טריוויאלי, הורדנו קצת את זמן הריצה. אולי יש משהו יותר טוב אבל אני לא מצלי לחשוב על זה