作者flashstar (闪亮的星)
看板TransCSI
标题Re: [问题] time complexity的问题想请教一下
时间Tue Jun 21 03:40:21 2005
※ 引述《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