如何找到Python中内置函数的复杂度

我有问题的特殊情况，但很高兴知道它是否适用于任何函数。

所以我想找到字符串中子字符串的位置。好的，在Python中有一个查找方法 https://docs.python.org/2/library/string.html#string.find这正是所需要的。

string.find(s, sub[ 开始[ 结束]])

返回 s 中的最低索引，其中 找到子串 sub 使得 sub 完全包含在 s[开始:结束]。失败时返回-1。开始和结束的默认值 负值的解释与切片相同。

令人惊奇，但问题是在一个大字符串中找到一个大子字符串可以从O(n*m) to O(n)（这是一件大事）取决于算法 http://en.wikipedia.org/wiki/String_searching_algorithm。文档没有提供有关时间复杂度的信息，也没有提供有关底层算法的信息。

我看到几种解决此问题的方法：

• 基准
• 转到源代码并尝试理解它

两者听起来都不太容易（我希望有一种更简单的方法）。那么如何找到内置函数的复杂度呢？

您说，“查看源代码并尝试理解它”，但这可能比您想象的要容易。一旦你得到了实际的实现代码，对象/stringlib/fastsearch.h https://hg.python.org/cpython/file/9c35973829e6/Objects/stringlib/fastsearch.h， 你发现：

/* fast search/count implementation, based on a mix between boyer-
   moore and horspool, with a few more bells and whistles on the top.
   for some more background, see: http://effbot.org/zone/stringlib.htm */

The 那里引用的 URL http://effbot.org/zone/stringlib.htm对算法及其复杂性进行了很好的讨论。