דף 1 מתוך 1

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

נשלח: 19:59 24/06/2009
על ידי oridov
אני אחדד את השאלה.

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

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


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

נשלח: 20:37 24/06/2009
על ידי TA_Ariel
כן k קבוע