算法复杂度

Question

我正在尝试计算以下算法的复杂度

private static List<int> GetIndexes(string strippedText, string searchText)
    {
        List<int> count = new List<int>();
        int index = 0;
        while (strippedText.Length >= index && index != -1)
        {
            index = strippedText.IndexOf(searchText.Trim(), index,
                                         StringComparison.OrdinalIgnoreCase);
            if (index != -1)
            {
                count.Add(index);
                index++;
            }
            else continue;
        }
        return count;
    }

我知道如果count在每次迭代中递增1，则循环的复杂度为O(n)，但是，递增取决于找到的索引。在每次迭代中，它可以递增1或strippedText.lenght()。

有什么想法吗？

Answer 1

不过，最坏的情况是O(n)。

Answer 2

它仍然是O(n) -这是因为它以与O(n)相同的速率渐近增长

大O符号用于算法增长的上限-也就是说，它是一个函数，保证算法以相同或更慢的速度增长。

在平均情况下，您的算法将以O(n/m)的速率增长，其中m是对字符串中索引密度的某种估计(0 =无索引，1=每个字符的索引)。假设这在n上大致不变，你可以忽略m，仍然可以说算法是O(n)。

事实上，在现实世界中，你的算法几乎肯定会比O(n)快，这并不会阻止它开始使用O(n)函数。

看一看this page，特别是：

符号O用于用另一个更简单的函数来描述一个函数的大小的渐近上界。这意味着对于x> k，当x趋于无穷大时，f(x)的值将始终低于C *g(x) (其中C是常数)。

Answer 3

O(n)，其中n是strippedText字符串的长度。

最坏的情况是，每个字符都等于searchText，并导致n次迭代，但即使不是这样(我假设不会)，您的平均情况也是n的某个因子，其中c大于0但小于1，所以循环的数量将是cn，但n的常数因子仍将表示为O(n)。