13 設二元搜尋樹（binary search tree）儲存有 n 個關鍵值（keys），則搜尋一個關鍵值其最佳及最差之時間 複雜度（time complexity）分別為何？
(A)最佳＝O(1)，最差＝O(n)
(B)最佳＝O(1)，最差＝O(log n)
(C)最佳＝O(1og n)，最差＝O(log n)
(D)最佳＝O(1og n)，最差＝O(n)

答案：登入後查看
統計： A(243), B(338), C(61), D(83), E(0) #2018900

詳解 (共 2 筆)

#3458369

看到二元搜尋樹直覺就覺得最差是O(log n) 

這是跟二分搜尋法搞混了

二元搜尋樹不一定是左右平衡的

如果全部子樹都在同一邊

最差就會來到O(n) 

 

而最佳的O(1) 就是搜尋值直接在樹根了 

52
0
#3443697
最佳＝O(1)，最差＝O(n) 平均=O...
(共 30 字，隱藏中）
前往觀看
9
0