זמן ריצה לאלגוריתם. מה שפורסם מדויק?

מנהל: TA_Isana

שלח תגובה
golaniu
הודעות: 17
הצטרף: 21:55 04/12/2008

זמן ריצה לאלגוריתם. מה שפורסם מדויק?

שליחה על ידי golaniu » 20:09 29/06/2009

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

O(n(logn + (m+n)logn)1


ה - n החיצוני הוא ריצה עבור כל קודקוד המוכנס לB
ועבור כל כזה קודקוד יש לעדכן את שכניו - במקרה הגרוע) = O((m+n)logn)1

כי הרי יש את המקרה הקיצון שבו לכל קודקוד (או אפילו לקודקוד אחד) כולם שכנים שלו.
כלומר עבור כל איבר בערימה ועבור כל שכן שלו מעדכנים את העלות ביניהם ועושים hipify
סה"כ נגיע לזמן ריצה של
. O(n(n+m) logn)1
אי אפשר להתחמק מזה.
יכול להיות שזהו זמן הריצה שצריך להיות??
או שיכול להיות שלעשות hipify לשכנים של קודקוד מסוים , ניתן להתייחס לכך k קבוע
k*logn?

TA_Ariel
הודעות: 261
הצטרף: 00:53 23/04/2009

שליחה על ידי TA_Ariel » 20:23 29/06/2009

הניתוח שלך לא נכון ,
כי גם אם כולם שכנים של כולם , יש לך לכל היותר m עדכונים ולכן
(n+m)*logn
כשכל עדכון עולה logn

golaniu
הודעות: 17
הצטרף: 21:55 04/12/2008

שליחה על ידי golaniu » 20:31 29/06/2009

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

Topic
הודעות: 15
הצטרף: 17:16 26/12/2008

זמן ריצה לאלגוריתם. מה שפורסם מדוייק?.

שליחה על ידי Topic » 16:48 30/06/2009

מה ז"א הערמה הקודמת?? למיטב הבנתי יש ערמה אחת בלבד שמתעדכנת במהלך הריצה
וכמו כן בהינתן לי רשימת זוגות התחלתית מ-A על מנת לבנות ערמה שבה כל קודקוד מופיע פעם אחת זה כבר עסק של M^2 כאשר M זה מס' הזוגותת, כי כל פעם יש לבדוק שהקודקוד בזוג הנוכחי לא הוכנס כבר ולשם כך יש לרוץ על בערמה או הזוגות עד עכשיו..
דבר נוסף למה בדיוק עידכון של כל שכן בקודוקד של LOGN הרי כדי למצא אותו בערמה של לוקח O של N ולעדכן N קודקודים ייקח N^2 ....
אשמח לתיקונים במידת הצורך..

שלח תגובה

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