民國114年 第2梯次 延期考區 電腦軟體設計(JAVA)乙級 學科
第33題
利用Knuth-Morris-Pratt 演算法在長度為m 的字串中搜尋長度為n 的字串,所需的時間複雜度 (Time Complexity)為何?
題目
利用Knuth-Morris-Pratt 演算法在長度為m 的字串中搜尋長度為n 的字串,所需的時間複雜度 (Time Complexity)為何?
- (1) θ(m+n)
- (2) θ(m)
- (3) θ(mn)
- (4) θ(n)
官方答案
(1) θ(m+n)
解析
KMP 演算法分兩階段：建立失敗函數（前綴表）耗時 θ(n)，掃描主字串耗時 θ(m)，總時間複雜度為 θ(m+n)。選項 2 僅計搜尋階段，選項 3 為暴力法複雜度，選項 4 僅計建表階段，均不完整。
AI 參考解析（推得答案已與官方答案比對一致），非官方公告內容，僅供備考參考。