שאלה

מנהל: TA_Isana

שאלה

הודעהעל ידי Brk » 10:52 16/07/2010

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

יש למישהוא רעיון איך לפתור את זה :D ?
נערך לאחרונה על ידי Brk בתאריך 11:48 16/07/2010, נערך פעם אחת בסך הכל.
Brk
 
הודעות: 87
הצטרף: 17:58 25/10/2009

Re: שאלה

הודעהעל ידי eliorar » 11:12 16/07/2010

מה האיברים במערך? שלמים? בטווח מסויים?
eliorar
 
הודעות: 35
הצטרף: 19:43 11/11/2009

Re: שאלה

הודעהעל ידי Brk » 11:48 16/07/2010

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


שלמים
Brk
 
הודעות: 87
הצטרף: 17:58 25/10/2009

Re: שאלה

הודעהעל ידי rubichi » 11:50 16/07/2010

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

Re: שאלה

הודעהעל ידי Brk » 12:11 16/07/2010

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


זה לא ממש אופטימלי אם זה יותר מn בריבוע?
Brk
 
הודעות: 87
הצטרף: 17:58 25/10/2009

Re: שאלה

הודעהעל ידי rubichi » 08:11 17/07/2010

נכון שזה זמן ריצה גדול אבל אני חושב שהדרישה היא גדולה, ובמקום לעשות את זה בn^3 כמו בתפרון הכי טריוויאלי, הורדנו קצת את זמן הריצה. אולי יש משהו יותר טוב אבל אני לא מצלי לחשוב על זה
rubichi
 
הודעות: 77
הצטרף: 18:50 22/10/2009


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

מי מחובר

משתמשים הגולשים בפורום זה: אין משתמשים רשומים ואורח אחד