דף 1 מתוך 1

זמני ריצה של ערימות

נשלח: 12:51 27/06/2009
על ידי litanil
שלום,

יש לי בעיה עם זמני הריצה הנדרשים בעבודה:
במידה והשיטה שאתם מעוניינים שנשתמש בה היא ערימה (או 2 ערימות, או מערך באורך K שמכיל ערימה אחת או שתיים בגודל n/k כ"א), אז זמן הריצה של בניית הערימה הוא n*log(n) (בחלוקה או מכפלה כזו או אחרת ב-K, שלא רלוונטית)

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

בקיצור, מכל כיוון שאני לא אסתכל על זה - תהיה איזושהי אי-עמידה בזמן ריצה...
איפה טעיתי?

נשלח: 13:21 27/06/2009
על ידי wizard
אם אני לא טועה, החישוב ההדוק של בניית ערימה הוא O(n) ולכן אין בעיה עם הערימות.
יש הוכחה מתמטית של הידוק הסיבוכיות בשקפים באתר.