שאלה

מנהל: TA_Isana

שלח תגובה
Brk
הודעות: 87
הצטרף: 17:58 25/10/2009

שאלה

שליחה על ידי Brk » 11:52 16/07/2010

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

יש למישהוא רעיון איך לפתור את זה :D ?
נערך לאחרונה על ידי Brk ב 12:48 16/07/2010, נערך פעם 1 בסך הכל.

eliorar
הודעות: 35
הצטרף: 19:43 11/11/2009

Re: שאלה

שליחה על ידי eliorar » 12:12 16/07/2010

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

Brk
הודעות: 87
הצטרף: 17:58 25/10/2009

Re: שאלה

שליחה על ידי Brk » 12:48 16/07/2010

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

rubichi
הודעות: 77
הצטרף: 18:50 22/10/2009

Re: שאלה

שליחה על ידי rubichi » 12:50 16/07/2010

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

Brk
הודעות: 87
הצטרף: 17:58 25/10/2009

Re: שאלה

שליחה על ידי Brk » 13:11 16/07/2010

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

rubichi
הודעות: 77
הצטרף: 18:50 22/10/2009

Re: שאלה

שליחה על ידי rubichi » 09:11 17/07/2010

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

שלח תגובה

חזור אל “- מבני נתונים 2010”