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

מנהל: TA_Isana

שלח תגובה
litanil
הודעות: 46
הצטרף: 12:17 24/11/2008

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

שליחה על ידי litanil » 12:51 27/06/2009

שלום,

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

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

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

wizard
הודעות: 18
הצטרף: 17:35 10/01/2009

שליחה על ידי wizard » 13:21 27/06/2009

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

שלח תגובה

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