sort

sort

karineli 15 Jul 2009 07:54

בתרגול על מיונים במצגת
כמה "יקר" להפוך ערמה לעץ חיפוש בינארי?

? O(nlogn) למה לא יכול להיות גם חסם עליון
?ואיזה אלגוריתם מיון במודל ההשואות ביצענו כאן

תודה

Re: sort

Yahav 15 Jul 2009 08:55

אפשר להראות את החסם העליון הזה, פשוט השאלה היא על חסם תחתון.

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

Re: sort

Danny Feldman 15 Jul 2009 10:57

חסם העליון לדוגמא הוא: שים את הערימה במערך ובנה ממנו עץ אדום שחור.