String.contains() 的时间复杂度

Question

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

Answer 1

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

一个完全幼稚的实现可能需要(n+1-k)*k比较来确定给定的 length 字符串n不包含 length 的特定子字符串k。那是O(nk)最坏的情况。

即使在第一次不相等比较后停止子字符串比较，虽然系数较小，但仍然是O(nk)。构造一个由许多独立字母重复组成的字符串，每个字母之间完全由k-1空格分隔，并在其中搜索 k 个连续空格的出现。搜索将失败，但每个子字符串比较都将进行摊销k/2比较才能找出答案，并且您仍然处于O(nk).

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

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