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