【客服暫停服務時間】10/31(四),影響:阿摩粉絲團、系統回報、信箱、鑽石兌換商城出貨事宜。

教甄◆資訊科技概論專業(電腦科)題庫下載題庫

上一題
1. 假設兩個字串的長度分別為 M 與 N,請問 Knuth-Morris-Pratt (KMP)字串比較演算法, 其時間複雜度為何?
(A)O(M×N)
(B) O(M/N)
(C) O(M+N)
(D) O(MN) 


答案:登入後觀看
難度: 適中

10
 【站僕】摩檸Morning:有沒有達人來解釋一下?
倒數 2天 ,已有 1 則答案
browen Hsieh 高二下 (2023/05/31):

Knuth-Morris-Pratt (KMP) 字串比較演算法的時間複雜度是 O(M+N)。答案選項 (C) 正確。

KMP 演算法是一種用於在一個主字串中尋找子字串的高效方法。它的時間複雜度基於主要的操作,其中 M 是主字串的長度,N 是要尋找的子字串的長度。

KMP 演算法的核心概念是利用子字串的部分匹配表(Partial Match Table)或稱為失敗函數(Failure Function),它在預處理階段計算並儲存子字串中的部分匹配值。這些值指示著當匹配失敗時,應該跳過主字串中的一些位置,以避免不必要的比較。

在 KMP 演算法的主要迴圈中,主字串和子字串進行比較。當匹配失敗時,KMP 演算法根據部分匹配表的值來決定下一次比較的位置,這樣可以跳過一些比較,減少不必要的操作。因此,它的時間複雜度為 O(M+N),其中 M 是主字串的長度,N 是子字串的長度。

選項 (A) O(M×N) 表示時間複雜度是主字串長度 M 乘以子字串長度 N,這是不正確的。KMP 演算法通過使用部分匹配表減少了比較操作的數量。

選項 (B) O(M/N) 不正確,因為 M/N 不代表 KMP 演算法的時間複雜度。

選項 (D) O(MN) 表示時間複雜度是主字串長度 M 乘以子字串長度 N,這是不正確的。KMP 演算法通過使用部分匹配表減少了比較操作的數量。

因此,正確答案是選項 (C) O(M+N)。

1個讚
檢舉


1. 假設兩個字串的長度分別為 M 與 N,請問 Knuth-Morris-Pr..-阿摩線上測驗