search

julycoding / The-Art-Of-Programming-By-July-2nd

本项目曾冲到全球第一，干货集锦见本页面最底部，另完整精致的纸质版《编程之法：面试和算法心得》已在京东/当当上销售
21.34k stars 7.1k forks source link

我认为01.05.md中最长回文子串中Manacher算法时间复杂度不是O(N),应是O(N^2) #385

Open hongsenliu opened 10 years ago

hongsenliu commented 10 years ago

我认为01.05.md中最长回文子串中Manacher算法时间复杂度不是O(N),应是O(N^2). N是原始输入string的长度，加了分隔符#之后是2N+1，再加$符号就是2N+2. 例如：s="1234321". N=7, 加了两种分隔符后是2N+2=16， s1="$#1#2#3#4#3#2#1#" 外层的for loop, 当i=8，里面的while loop要循环7次。 所以我认为时间复杂度是O(N^2). 请勘校。

ZumiKua commented 8 years ago

当一个回文串的右边界超过mx以后，mx会被更新至该右边界，而后续的while loop均会在mx之后进行查找。实际上，当一个字符被while loop访问以后，mx会被更新至该字符之后，进而所有的while loop会在该字符之后进行查找，所以一个字符仅会被while loop访问一次（仅指通过s[i + p[i]]访问的部分），故该算法的时间复杂度为O(n)。如果不理解的话，也可以自己写个程序测试一下while循环执行的次数，相信你会弄懂的;)

ArtixZ commented 5 years ago

mx 之外的字符 不会被更新至字符之后. 我认为应该是会重复访问字符的