מבני-נתונים ומבוא לאלגוריתמים - שאלה מבחינה

[vinney]

S זה מערך המקור אם כן

אל תשתמש במונח קבוצה, כי זה לא

 

[thankful]

די מסכים (מדוע המשורר השתמש בקבוצה ? לא ברור)

ובכל אופן , מה קורה עם זמני הריצה ? יש הטוענים , כפי שציינתי , שהעתקת S ל - T , כך שב - T לא תהיינה כפילויות , לוקח יותר מאשר (THETA(N . ואז עלולה להיות בעייה בלעמוד בדרישות זמן הריצה המבוקש בשאלה ...

 

[vinney]

תכניס אותם לעץ

 

[thankful]

כנראה שזה אכן הכיוון

עוד מישהו הציע את זה בפורום הקורס - להכניס את האיברים לעץ אדום-שחור צריך לחשוב על זה ... בהזדמנות

 

[SatanD]

אולי הכנסה לערימה ואז משהו...

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

 

[vinney]

בשביל מה ערימה???

התיאור שלו די בסדר, הוא פשוט עשה מיון בסיבוכיות גדולה מדי.

 

[SatanD]

צודק

נכון, ערימה לא תעזור, ובאמת המיון יכול להיות בסיבוכיות הנדרשת עם אלג' אחר.