作者luckyburgess (the one)
看板Grad-ProbAsk
标题[理工] [资结]-复杂度
时间Tue Nov 17 23:13:41 2009
有底下三个小问题想问各位大大,希望大家可以帮帮忙解答^^
Q1:radix sort可以用sequential list或是linked list来执行吗?
Q2:"searching for a key in a heap takes worst-case time O(n)"
这句叙述对吗?? why??
Q3:"The time complexity of binary search is the same as searching with
binary search tree"这句叙述对吗?? why??
麻烦大家了!!
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.134.213.201
1F：→ aey:1.可以 2.应该是log n (树高) 3.都是log n 11/18 04:09
2F：推 FRAXIS:1.可以 2.没错, 因为heap没有像二元数那种顺序性 11/18 10:47
3F：→ FRAXIS:3. 不对, 要平衡的二元树才是O(lg n) 11/18 10:48
4F：推 aey:嗯 楼上才是对的 11/18 11:21
5F：→ polomoss:2. 1~n由小到大建立BST，搜寻就会花O(n) 11/18 18:53
6F：→ luckyburgess:恩 那请问第一题是两个都可以吗?? 11/18 20:44
7F：→ abien:yes 11/19 11:00