string - String.contains() 的时间复杂度

Question

String.contains();的时间复杂度是多少？假设 n 是与另一个长度为 k 的字符串进行比较的字符串的长度。

Answer 1

如果不知道您感兴趣的 String.contains() 的实际实现，就没有答案；或者您打算使用什么算法。

一个完全天真的实现可能需要(n+1-k)*k比较来决定给定长度n的字符串不包含特定长度的子字符串k。这是最坏情况下的 O(nk)。

即使在第一次不相等比较后停止子串比较，虽然系数较小，但仍然是 O(nk)。构造一个由多个独立字母重复组成的字符串，每个字母恰好由 k-1 空格分隔，然后搜索其中出现的 k 个连续空格。搜索将失败，但每个子字符串比较都将进行摊销的 k/2 比较以找出结果，而您仍在 O(nk)。

如果已知 k 远小于 n，您可以将其视为 O(n)。

平均情况取决于实际使用的算法，也取决于两个字符串中字符的分布；而且您还没有说出其中任何一个是什么。