O(n) = O(kn) b אפשר להניח את זה?

מנהל: TA_Isana

שלח תגובה
oridov
הודעות: 11
הצטרף: 14:32 29/11/2008

O(n) = O(kn) b אפשר להניח את זה?

שליחה על ידי oridov » 19:59 24/06/2009

אני אחדד את השאלה.

בתרגול האחרון ראינו כי בעזרת partition ניתן למצוא את האיבר ה- k בגודלו ב- O(n.
באתחול עלינו למצוא את מיקומם האמיתי של k איברים, זאת אומרת k*O(n. בנוסף, במהלך מציאת כל איבר, אנו מוצאים על הדרך את מיקומם האמיתי של מספרים נוספים, אותם אנו לא מחפשים אך יכולים להיות אלו שנחפש בעתיד, כך שרוב הסיכויים שלא נצטרך לחפש את כל k האיברים. אז זמן הריצה יהיה פחות מ- k*O(n.

השאלה שלי אם אפשר להתייחס ל K כקבוע, והאם הוא יכול לקבל את הערך n או משהו דומה.


אם זה נשמע סינית, אני מתנצל. זה ככל הנראה סינית באמת.

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

שליחה על ידי TA_Ariel » 20:37 24/06/2009

כן k קבוע

שלח תגובה

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