selection problem 最後算出的time complexity

115 views

Skip to first unread message

unread,

Sep 2, 2015, 7:47:55 AM9/2/15

to 黃子嘉 - 線代離散研究室

老師請問selection problem 最後算出的time complexity為 T(n)=T(n/5)+T(3/4n)+O(n)

為什麼求p(medium的medium)利用遞迴? 第2步驟已經把n/5堆的medium找出來,在排序此n/5堆的medium,找出此數列的medium,應該只需sort的時間O(n^2)吧?

unread,

Sep 6, 2015, 4:14:13 AM9/6/15

to 黃子嘉 - 線代離散研究室

因為用遞迴作的話時間分析出來比直接用排序快阿

如過你要對那 n/5 個medium作sorting, 花O(n log n)的時間

那還不如一開始對那 n 個數作sorting再找第 k 小的數,

時間一樣是O(n log n), 也不用作sorting了

可是那一步若用遞迴時間分析出來就只需要 T(n) = O(n)

Reply all

Reply to author

Forward

0 new messages