作者fzrmitsul (我的妹妹很可爱)
看板TransCSI
标题[问题] 排序时间复杂度问题
时间Thu May 28 12:53:59 2009
1.在n笔资料的二元搜寻树上搜寻一笔资料，在最差情况下，其时间复杂度为?
(a)O(log n) (b)O(n) (c)O(n log n) (d)O(n^2)
答案是b，请问为什麽不是a呢??不是应该为log2 n吗??
再来是关於Merge Sort的问题
因为课本上写到每经过一次合并需要比较O(n)次，总共需要O(log2N)次
所以复杂度为O(n log2n)
我想请问的是如果是4笔资料由小到大排序，如12、6、55、60
不是要比较3次吗??
他课本的范例是如果有5个元素，请问需要经过几次的合并才能完成
答案是log2 5 = 3(次)
不知是否有前辈能指教呢??谢谢
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 61.62.164.121