在有N個節點的二元樹中作搜尋的運算,其執行時間跟何者成正比?
AN
Blog N正確答案
CN^2
DN log N
答案與詳解
B
正確答案
二元樹搜尋（預設平衡狀態）的時間複雜度為 O(log N)，因每次比較可排除一半節點，執行時間與樹高成正比。
為什麼答案是 B
正解。預設為平衡二元搜尋樹，每次比較排除一半資料，搜尋時間與樹高 O(log N) 成正比。
考點：線性時間考點：對數時間考點：平方時間考點：線性對數時間
載入中…
完整詳解
Pro · 無限重點 二元樹搜尋（預設平衡狀態）的時間複雜度為 O(log N)，因每次比較可排除一半節點，執行時間與樹高成正比。
秒殺技巧
看到「二元樹搜尋」或「二元搜尋法」直接選 log N；若題目強調「遍歷(Traversal)」或「最差情況(歪斜樹)」才選 N。逐選項分析
A線性時間✕ 陷阱
線性搜尋或二元樹退化成歪斜樹（Linked List）的最差情況時間複雜度。
B對數時間✓ 正確
正解。預設為平衡二元搜尋樹，每次比較排除一半資料，搜尋時間與樹高 O(log N) 成正比。
C平方時間✕
通常為簡單排序演演算法（如氣泡排序、選擇排序、插入排序）的最差或平均時間複雜度。
D線性對數時間✕
通常為進階排序演演算法（如合併排序、快速排序、堆積排序）的平均時間複雜度。
常見演演算法時間複雜度對照
| 複雜度 | 代表意義 | 常見情境 |
|---|---|---|
| O(1) | 常數時間 | 雜湊表(Hash Table)搜尋 |
| O(log N) | 對數時間 | 平衡二元搜尋樹、二元搜尋法 |
| O(N) | 線性時間 | 線性搜尋、樹的遍歷(Traversal) |
| O(N log N) | 線性對數時間 | 合併排序、快速排序 |
陷阱提醒
嚴格來說，「一般二元樹」若未平衡（如歪斜樹），搜尋時間為 O(N)。但國營與公職計概考試中，「二元樹搜尋」通常預設指「平衡二元搜尋樹」，每次比較排除一半，故選 O(log N)。