民國109年 第2梯次 電腦軟體設計(JAVA)乙級 學科
第20題
從一個擁有n 個節點的鏈結串列刪除一個值為x 之節點,在最壞情況下所需時間複雜度為多少?
題目
從一個擁有n 個節點的鏈結串列刪除一個值為x 之節點,在最壞情況下所需時間複雜度為多少?
- (1) θ(1)
- (2) θ(log n)
- (3) θ(n log n)
- (4) θ(n)
官方答案
(4) θ(n)
解析
單向鏈結串列只能從頭節點依序走訪，刪除值為 x 的節點時必須先找到它的前一個節點，才能修改指標完成刪除。最壞情況是 x 位於串列尾端或根本不存在，需檢查全部 n 個節點，比較次數與 n 成正比，故時間複雜度為 θ(n)。θ(1) 只有在已持有前驅節點指標（例如雙向串列）時才成立；θ(log n) 需具備隨機存取或已排序的索引結構；θ(n log n) 通常是排序演算法的成本。
AI 參考解析（推得答案已與官方答案比對一致），非官方公告內容，僅供備考參考。