String.contains();的时间复杂度是多少？ 假设 n 是与另一个长度为 k 的字符串进行比较的字符串的长度。
最佳答案
如果不知道您感兴趣的 String.contains() 的实际实现，就没有答案；或者您打算使用什么算法。
一个完全幼稚的实现可能需要(n+1-k)*k比较来确定长度为n的给定字符串不包含长度为特定的子字符串k。最坏情况下的时间复杂度为 O(nk)。
即使在第一次不等比较后停止子字符串比较，虽然系数较小，但仍然是O(nk)。构造一个由许多独立字母重复组成的字符串，每个字母之间恰好由 k-1 空格分隔，并在其中搜索 k 个连续空格的出现。搜索将会失败，但每个子字符串比较都需要进行摊销 k/2 比较才能找到答案，而且您的时间仍然是 O(nk)。
如果已知 k 远小于 n，您可以将其视为 O(n)。
平均情况取决于实际使用的算法，也取决于两个字符串中字符的分布；而且你还没有说其中任何一个是什么。
关于string - String.contains() 的时间复杂度，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/51391513/