?

[JohnnyPiloni]

?

נתון מערך לא ממוין שמכיל את כל הערכים בין 0 ל-n חוץ מאחד מהם. תכננו אלגוריתם הפרד ומשול שסיבוכיות הזמן שלו נתונה על ידי הנוסחא: t=t(n/2) + o(n הסבירו את האלגוריתם שלכם, ונתחו את סיבוכיות.

 

[freak2100]

"אלגוריתם הפרד ומשול"? מה הכוונה? ../images/Emo3.gif

אם אתה צריך למצוא איזה איבר לא מופיע, אתה יכול לעשות את זה בסיבוכיות של n - תסכום את כל האיברים, ותעשה:

(n*(n+1)/2) - sum​

זה מאוד פשוט, זה הסכום של כל האיברים בין 0 לn (סכום של סדרה חשבונית), פחות סכום של כל האיברים בין 0 לn חוץ מאחד מהם... זה מחזיר לך את האיבר האחד הזה

אם אתה רוצה משהו של nlogn, אתה יכול למיין את המערך (merge-sort) ואז לעשות בו חיפוש (logn), האמת שלא השוותי לסיבוכיות שמבקשים ממך אבל כנראה שזה מה שהם חשבו עליו.

 

[Okuryo]

../images/Emo119.gifהכוונה לאלגוריתם

אשר מחלק את הקלט למספר קלטים קטנים ממנו, מטפל בכל אחד מהם באופן רקורסיבי, ואז מאחד את הקטעים. למשל Merge-Sort ו-Quick-Sort עובדים כך. אבל איך ידעת מה האלגוריתם שהוא מבקש אמור לעשות? הוא לא כתב את זה

 

[freak2100]

אה, לא ידעתי שזה נקרא "הפרד ומשול"

אז מה שנתתי לו בכלל לא טוב

(חוץ מזה שאנחנו באמת לא יודעים מה הוא צריך לבצע

)

 

[JohnnyPiloni]

Okuryo

Okuryo לפי ההסבר שלך להפרד ומשול השאלה בכלל לא תקינה (חסר משהו בשאלה). זה אפשרי למצוא את המספר שחסר באמצעות הפרד ומשול?(נגיד שזה מה שהיה כתוב) * בסיבוכיות o, לפי הנוסחא הרקורסיבית

 

[Okuryo]

../images/Emo119.gifאני מניח שהכוונה לאלגוריתם דומה

לחיפוש בינארי. אם נסמן את המערך ב-A ונניח שהוא מתחיל מ-0, אז אפשר לבדוק אם A[n/2]=n/2 (כאשר n/2 מעוגל למטה או למעלה). אם כן, נמשיך לחפש אחרי האמצע, ואם לא אז נחפש לפני האמצע. אם נשאר רק איבר אחד במערך, אז אם נחסר ממנו 1 נקבל את הערך שחסר. נראה לי שזה עובד, אבל הנוסחה לזמן הריצה היא (T=T(n/2)+Θ(1... אפשר גם לעבור על כל המערך בשביל הכיף בכל קריאה, בשביל זמן רוצה ארוך יותר

ושים לב שיש הבדל בין הסימון (o(n ו-(O(n, אז כתוב את מה שאתה מתכוון אליו.