String.contains()的时间复杂度 [英] Time complexity of String.contains()
问题描述
String.contains()的时间复杂度是多少?假设n是要与另一个长度为k的字符串进行比较的字符串的长度.
What is the time complexity of String.contains(); lets say n is the length of the string that is compared against another string of length k.
推荐答案
在不知道您感兴趣的String.contains()的实际实现的情况下没有答案.或您打算使用哪种算法.
There is no answer without knowing the actual implementation of the String.contains() that you're interested in; or what algorithm you intend to use.
一个完全幼稚的实现可能需要进行(n + 1-k)* k
的比较才能确定给定长度为 n
的字符串不包含特定长度的子字符串 k
.最糟糕的情况是 O(nk)
.
A completely naive implementation might take (n+1-k)*k
comparisons to decide that a given string of length n
does not contain a particular substring of length k
. That's O(nk)
for the worst case.
即使在第一次不相等比较之后停止子字符串比较,尽管系数较小,但仍然是 O(nk)
.构造一个字符串,该字符串是许多孤立的字母的重复,每个字母都由完全 k-1
个空格分隔,然后搜索出现的k个连续空格.搜索将失败,但是每个子字符串比较都将进行摊销的 k/2
比较以找出答案,并且您仍处于 O(nk)
.
Even stopping substring comparisons after the first unequal comparison, while having a smaller coefficient, still is O(nk)
. Construct a string that's a repetition of many isolated letters, each separated by exactly k-1
spaces, and search that for an occurrence of k consecutive spaces. The search will fail, but each substring comparison will take an amortized k/2
compares to find that out, and you're still at O(nk)
.
如果已知 k
远小于 n
,则可以将其视为 O(n)
.
If k
is known to be much less than n
, you could treat that as O(n)
.
平均大小写取决于所使用的实际算法,还取决于两个字符串中字符的分布;而且您还没有说这两个是什么.
The average case depends on the actual algorithm used, and also on the distribution of characters in the two strings; and you haven't said what either of those were.
这篇关于String.contains()的时间复杂度的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!