מחפש אלגוריתם בזמן לינארי

[kobi2579]

מחפש אלגוריתם בזמן לינארי

a+a[j]=x כש-a הוא מערך בגודל n ו: n>=j>i>=1 בתודה מראש! ואגב, יש למישהו אתר בעברית\אנגלית לפסאודו-קודים של אלגוריתמים שונים, ידועים יותר וידועים פחות? אולי ספר טוב שהוא מכיר?

 

[yonyl]

אתה יכול להסביר איזה

אלגוריתם אתה צריך. לא הצלחתי להבין מהכתוב

 

[kobi2579]

זה הולך ככה

יש מערך a של n מספרים שלמים ומספר שלם X. צריך להחזיר האם קיים זוג אינדקסים: n>=j>i>=1 כך ש: a+a[j]=X אני מקווה שעכשיו זה מוסבר קצת יותר טוב מההודעה המקורית...

 

[yuvalmadar]

נתון עוד משהו?

(למשל, אם המערך יהיה ממויין זה יהיה מאד נחמד

)

 

[kobi2579]

אם אתה רוצה

תמיין... אבל אז זה יה מינימום nlogn... אין אפשרות לעשות זאת בזמן לינארי בתכנות דינאמי לדעתך?

 

[vinney]

לא בלי הנחות על מערך

 

[kobi2579]

אוקיי... ואם הנחות על מערך?

הכי נמוך שאפשר להשיג...

 

[kobi2579]

אם=עם

 

[vinney]

O של 1, כמובן

יותר נמוך מזה אין. אילו הנחות? זה שאלה של שיעורי בית שלך? אולי כדאי שתברר עם המרצה אילו הנחות יש לך כדי שתמשיך משם? כי בלי לדעת כלום על המערך, לא תרד מNLOGN

 

[kobi2579]

אין הנחות על המערך. מותר למיין.ו..

צריך לעשות זאת בזמן הכי נמוך שיש

 

[vinney]

אם המערך ממוין

אז אתה פשוט עובר עם שני מצביעים.

 

[vinney]

שרשור הספרים

נמצא עוד בעמוד הזה בפורום (וגם בטגליינס)

 

[ron369]

אולי במקרה הערכים במערך מתפלגים

בצורה אחידה, פחות או יותר? (פשוט הבעיה הזו נשמעת לי מוכרת משיעור במבני נתונים, על טבלאות גיבוב, אני אני לא טועה)

 

[yuvalmadar]

טבלאות גיבוב לא דורשות התפלגות

הן דואגות להתפלגות בעצמן באמצעות "פונקציות גיבוב אוניברסליות". אבל פועלות טוב רק במקרה הממוצע. מה שאתה חושב עליו זה מיון דלי לדעתי.

אבל כך או כך, הוא לא אמר שנתון משהו על המערך.

 

[yonyl]

בלי מיון ובלי עזר כלשהו

לפי דעתי לא אפשרי ב N . הרי אין לך שום דרך להשוות את הזוגות השונים ב N פעולות.(כמו שבמיון אין אפשרות) לפי דעתי הכוונה שמותר לך פעם אחת למיין או לבנות מבנה נתונים שתומך בדרישה.ואז זה יסתדר בקלות עם מיון.

 

[ron369]

אני מנסה להיזכר מה היה בשיעור ../images/Emo6.gif

והדרישה להתפלגות אקראית נשמעה מתאימה לעניין

 

[indef]

רמז

תחשוב איך hash table תעזור לך פה

 

[yonyl]

זה במקרה הממוצע...

אבל רעיון נחמד.