题目中已经有问题了,Python中str.find(string, substring)
的C实现的最坏情况时间复杂度是多少 if n是string
的长度,m是substring
的长度?源代码 ( https://hg.python.org/cpython/file/99f5a0475ead/Objects/stringlib/fastsearch.h ) 似乎在谈论 boyer-moore-horspool 算法,根据维基百科,该算法的最坏情况复杂度为 O(m*n ).
编辑: O(m*n) 是指 boyer-moore- 的运行时间horspool 算法,查找字符串中出现的所有 个子字符串。 Python 的 str.find
方法只找到子字符串的 one 出现,所以它的 (str.find
) 将取决于在 substring
第一次出现的位置。所以不,我还没有发布答案。
最佳答案
The source code seems to talk about the boyer-moore-horspool algorithm, which according to Wikipedia has a worst-case complexity of O(m*n).
对于 CPython,您的答案是 O(m*n)
。一般来说,它显然依赖于实现。
编辑:是的,如果您已经进行了研究,我想知道您为什么要问这个问题。
关于python - python 中 str.find 的最坏情况时间复杂度,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/29728969/