民國109年 第2梯次 電腦軟體設計(C++)乙級 學科
第31題
對一個擁有n 個節點的二元樹(Binary Tree)進行搜尋某一個值x,在最壞情況下所需時間複雜度為 多少?
題目
對一個擁有n 個節點的二元樹(Binary Tree)進行搜尋某一個值x,在最壞情況下所需時間複雜度為 多少?
- (1) θ(1)
- (2) θ(log n)
- (3) θ(n log n)
- (4) θ(n)
官方答案
(4) θ(n)
解析
一般二元樹（非二元搜尋樹）並沒有「左小右大」的排序性質，也沒有平衡保證，因此搜尋某個值 x 時，最壞情況必須走訪每一個節點，仍找不到或最後才找到，比較次數與節點數 n 成正比，時間複雜度為 θ(n)。只有平衡的二元搜尋樹高度約為 log n，搜尋才是 θ(log n)；θ(1) 是陣列以索引直接存取的常數時間；θ(n log n) 則是合併排序、快速排序平均等排序演算法的等級。本題關鍵在於「最壞情況」與「未平衡的二元樹」。
AI 參考解析（推得答案已與官方答案比對一致），非官方公告內容，僅供備考參考。