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

מנהל: TA_Isana

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

הודעהעל ידי michal cohen » 13:53 26/06/2010

זמן הריצה שלו הוא O(n) במקרה הגרוע?
michal cohen
 
הודעות: 87
הצטרף: 19:04 11/11/2009

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

הודעהעל ידי danny » 14: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
danny
 
הודעות: 64
הצטרף: 12:32 23/10/2009


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

הודעהעל ידי Shahar » 17:10 26/06/2010

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

אני חושב שselect הרגיל שמבוסס על Partition עובד בO(n) בממוצע, אבל לא בטוח...
Shahar
 
הודעות: 160
הצטרף: 16:49 29/10/2009


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

מי מחובר

משתמשים הגולשים בפורום זה: אין משתמשים רשומים ואורח אחד