האלגוריתם למציאת האיבר ה-i בגודלו

מנהל: TA_Isana

שלח תגובה
michal cohen
הודעות: 87
הצטרף: 19:04 11/11/2009

האלגוריתם למציאת האיבר ה-i בגודלו

שליחה על ידי michal cohen » 14:53 26/06/2010

זמן הריצה שלו הוא O(n) במקרה הגרוע?

danny
הודעות: 64
הצטרף: 12:32 23/10/2009

Re: האלגוריתם למציאת האיבר ה-i בגודלו

שליחה על ידי danny » 15:52 26/06/2010

אני מאמין שכן
הסבר:
הראנו שניתן לבנות Heap ממערך נתון בזמן (O(n (החסם הפשוט הוא (O(nlogn והחסם הצמוד יותר הוא (O(n לאחר הסבר מפורט יותר)
-אז בונים Heap (סוג הערימה לפי הצורך: אם צריך את האיבר ה-k בגודלו בסדר יורד או עולה) מהמערך הנתון
-הצעד הבא הוא להדפיס את k האיברים הגדולים (קטנים) ביותר ע"י Heap בזמן (O(klogk - פתרון שהוצג במבחן מ-2009
אז סה"כ

קוד: בחירת הכל

O(n)+O(klogk)=O(n)
Error is Created. Truth is Eternal. Error, or Creation, will be Burned up, & then, & not till Then, Truth or Eternity will appear


Shahar
הודעות: 160
הצטרף: 16:49 29/10/2009

Re: האלגוריתם למציאת האיבר ה-i בגודלו

שליחה על ידי Shahar » 18:10 26/06/2010

@danny
זה לא מדוייק, כי אתה מניח שk קבוע. מה אם רוצים למצוא את החציון (n/2 בגודלו)?
אז klogk כבר לא זניח ביחס לn...
האלג' שיולי הביאה (חלוקה לחמישיות וכו') עובד בO(n) במקרה הגרוע, בכמט "הוכיח" את זה בכיתה

אני חושב שselect הרגיל שמבוסס על Partition עובד בO(n) בממוצע, אבל לא בטוח...

שלח תגובה

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