[理工] 資結 sort時間複雜度
12.Suppose you are given a sorted list of N elements followed by f(N)
randomly ordered elements.How would you sort the entire list if
* A. f(N)=O(1)
* B. f(N)=O(logN)
* C. f(N)=O(N^1/2)
* D. How large can f(N) be for the entire list still to be sortable in O(N)
time?
Solution:
A. f(N)=O(1) In this case insertion sort would be the best ,giving the time
complexity of O(N)
B. f(N)=O(log N) Merge sort is the best option with a time complexity of O(N)
C.f(N)=O(N^1/2) Merge sort is the best option with a time complexity of O(N)
D.complexity = f(N)log f(N) + N +f(N)
Clearly f(N) is O(N) for the complexity to be of O(N)
這是某個題目他所給的答案
但問題A insertion sort best case 不是應該卡在 O(n)嗎? 怎麼會跑到(1)了?
問題B、C Merge sort 時間複雜度不是應該卡在O(nlogn)嗎?
問題D 更是看不懂
向高手大大們求解
資料來源: http://knowledge4uguys.blogspot.tw/ 第12題
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 27.105.238.247
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1452480691.A.1CE.html
推
01/11 15:26, , 1F
01/11 15:26, 1F
→
01/11 15:26, , 2F
01/11 15:26, 2F
→
01/11 15:27, , 3F
01/11 15:27, 3F