民國109年 第2梯次 電腦軟體設計(JAVA)乙級 學科
第50題
對一個擁有n 個節點的二元樹(Binary Tree)進行搜尋某一個值x,在最壞情況下所需時間複雜度為 多少?
題目
對一個擁有n 個節點的二元樹(Binary Tree)進行搜尋某一個值x,在最壞情況下所需時間複雜度為 多少?
- (1) θ(1)
- (2) θ(log n)
- (3) θ(n log n)
- (4) θ(n)
官方答案
(4) θ(n)
解析
一般二元樹（非二元搜尋樹）不具備有序性質，搜尋任意值 x 必須在最壞情況下遍歷所有 n 個節點，時間複雜度為 θ(n)。選項 1 僅適用陣列索引存取，選項 2 為平衡二元搜尋樹，選項 3 為合併排序等演算法複雜度。
AI 參考解析（推得答案已與官方答案比對一致），非官方公告內容，僅供備考參考。