עמוד 1 מתוך 1

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

הודעהפורסם: 13:53 26/06/2010
על ידי michal cohen
זמן הריצה שלו הוא O(n) במקרה הגרוע?

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

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

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

הודעהפורסם: 15:02 26/06/2010
על ידי yuli0708

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

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

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