Re: [問題] time complexity的問題想請教一下
※ 引述《dynamicy (小人物)》之銘言：
: How many time steps it needs to merge two sorted list
: into a sorted list?
: Assume that there are O(N) elements in total.
: a) O(log N), b) O(1), c) O(N), d) O(N log N).
: 假設兩個sroted的list
: A=1 3 5 7
: B=2 4 6 8 共有8個elements
: 2>1 4>1,3 6>1,3,5 8>1,3,5,7
: total 10
: 所以至少要O(N log N)
: 個人感覺是d,這樣的想法正確性如何?
c) O(N)
Big-O 是考慮worst case,
而worst case是 A= 1,3,5,7
B= 2,4,6,8
1<2 => 1出去
2<3 => 2出去
3<4 => 3出去
4<5 => 4出去
5<6 => 5出去
6<7 => 6出去
7<8 => 7出去
8 => 8出去
共比較了8次, 也就是N次, 所以是O(N),
算time complexity有的是用comparison次數, 有的是用exchange次數, 都可, 看情況.
: What is the average case time complexity to search in a linked list,
: where the key of the nodes are sorted?
: Assume that the number of nodes in the linked list is N.
: 這題的話,個人感覺是log N
: 想請教一下,感謝!
O(N),
這是link-list, 無法使用Binary-Search.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.113.236.219