鍍金池/ 問(wèn)答/C++  網(wǎng)絡(luò)安全/ KMP算法的時(shí)間復(fù)雜度是如何計(jì)算的？

KMP算法的時(shí)間復(fù)雜度是如何計(jì)算的？

假設(shè)在M字符串中找N字符串的起始位置，長(zhǎng)度分別為m和n，使用KMP算法，一般認(rèn)為時(shí)間復(fù)雜度是O（m+n），也就是計(jì)算next數(shù)組的時(shí)間復(fù)雜度是O(n)，而匹配的時(shí)候是O（m），但是在匹配的時(shí)候假設(shè)i用來(lái)標(biāo)識(shí)M中的位置,j用來(lái)標(biāo)識(shí)N中的位置，i是只增不減的可以理解，但是j也會(huì)按照next數(shù)組來(lái)回溯呀，也可能會(huì)回溯多次呀，為什么匹配的時(shí)候時(shí)間復(fù)雜度不是O(m*n)呢？求解

回答
編輯回答
瘋浪

j的回溯只會(huì)影響搜索主循環(huán)次數(shù)的上下界（[m, 2m]），而不會(huì)像你說(shuō)的使其變成m*n的關(guān)系。

你可以這樣理解，由于m是只增不減的，所以最壞的情況是這樣的：

  1. 每次匹配都會(huì)失?。╩保持不變）
  2. 再次匹配也失?。╩+1）

在這種情況下，對(duì)于M中的每個(gè)字符，實(shí)際上都比較了2次，所以一共執(zhí)行了2m次循環(huán)。這是循環(huán)次數(shù)的上限。其他任何情況，都至少有若干次循環(huán)是m直接+1的。

2017年1月9日 09:04
編輯回答
離殤

j雖然回溯，但是向前進(jìn)的

2017年1月11日 03:42