※ 引述《fzrmitsul (我的妹妹很可爱)》之铭言： : 1.在n笔资料的二元搜寻树上搜寻一笔资料，在最差情况下，其时间复杂度为? : (a)O(log n) (b)O(n) (c)O(n log n) (d)O(n^2) : 答案是b，请问为什麽不是a呢??不是应该为log2 n吗?? 在极端情况下 二元搜寻树可能会退化成左(右)倾树 这情况下是 O(n) : 再来是关於Merge Sort的问题 : 因为课本上写到每经过一次合并需要比较O(n)次，总共需要O(log2N)次 : 所以复杂度为O(n log2n) : 我想请问的是如果是4笔资料由小到大排序，如12、6、55、60 : 不是要比较3次吗?? : 他课本的范例是如果有5个元素，请问需要经过几次的合并才能完成 : 答案是log2 5 = 3(次) : 不知是否有前辈能指教呢??谢谢 1 2 3 4 5 [ ] [ ] [ ] step1 [ ] [ ] step2 [ ] step3 --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 114.45.63.88