gpt4 book ai didi

algorithm - KMP算法的最佳和最差时间复杂度是多少

转载 作者:行者123 更新时间:2023-12-04 12:05:21 25 4
gpt4 key购买 nike

需要澄清 KMP 算法的最佳时间复杂度和最坏时间复杂度。令我困惑的是 O(n) 的最差搜索时间复杂度。我在网上阅读后了解到,有两个索引。一个索引 i 用于文本,另一个索引 j 用于模式。我们不减少文本索引 i。但是当存在不匹配且 j 值大于 0 时,我们会递减模式索引 j。在这种情况下,i 保持不变。那么最坏的时间复杂度怎么会是O(n)呢?它应该比 O(mn) 还多。对于特定的 i 值,我们可以对 j 进行多次迭代。
最好的情况是什么?它与最坏的情况有什么不同吗?我正在寻找简单的解释,因为我已经阅读了不同的教程。

最佳答案

KMP 不会在不增加 i 的情况下增加 j。因此,即使在 i 的每次增量之间可以有 j 的 Theta(m) 减量,但在算法过程中 j 的减量总数不能超过 j 的增量总数,即等于增量数我的所有都是 Theta(n),KMP 的最坏和最好情况渐近运行时间(假设我们找到了所有匹配项;如果不是,那么显然最好的情况是 Theta(m))。

关于algorithm - KMP算法的最佳和最差时间复杂度是多少,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/63867161/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com