民國111年 第2梯次 電腦軟體設計(JAVA)乙級 學科
第52題
從一個擁有n 個節點的鏈結串列刪除一個值為x 之節點,在最壞情況下所需時間複雜度為多少?
題目
從一個擁有n 個節點的鏈結串列刪除一個值為x 之節點,在最壞情況下所需時間複雜度為多少?
- (1) θ(n log n)
- (2) θ(n)
- (3) θ(1)
- (4) θ(log n)
官方答案
(2) θ(n)
解析
鏈結串列不支援隨機存取，只能由頭節點開始逐一走訪，比對節點值是否為 x。最壞情況是目標位於串列末端，或根本不存在而需走完全部節點，此時須檢查 n 個節點，時間複雜度為 θ(n)。找到節點後的刪除動作本身只需調整指標，為 θ(1)，但前置的搜尋才是決定整體成本的關鍵，故答案為 2。
AI 參考解析（推得答案已與官方答案比對一致），非官方公告內容，僅供備考參考。