[理工] 資結 sort時間複雜度

[jessede (jessede)]

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
推 goldflower: 他的f(n)就是題目size大小了 所以你就把f(n)帶進去就
→ goldflower: 會得出big o 另外你d沒看完 那不是答案
→ goldflower: 另外他沒用tighty bound