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)*kcomparisons 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屋！