民國110年 第2梯次 電腦軟體設計(JAVA)乙級 學科
第19題
從一個擁有n 個節點的鏈結串列刪除一個值為x 之節點,在最壞情況下所需時間複雜度為多少?
題目
從一個擁有n 個節點的鏈結串列刪除一個值為x 之節點,在最壞情況下所需時間複雜度為多少?
- (1) θ(n)
- (2) θ(1)
- (3) θ(n log n)
- (4) θ(log n)
官方答案
(1) θ(n)
解析
鏈結串列刪除節點需先搜尋目標節點。最壞情況下，目標節點位於串列尾端或不存在，必須從頭節點遍歷所有 n 個節點，時間複雜度為 θ(n)。刪除動作本身 (調整指標) 僅 O(1)，但搜尋主導整體複雜度。雙向鏈結串列若已持有節點參考可 O(1)，但題目未給此條件。
AI 參考解析（推得答案已與官方答案比對一致），非官方公告內容，僅供備考參考。