如何计算时间复杂度？

Question

我在计算大 O 时真的遇到了麻烦。我了解了基础知识，但是当涉及到嵌套 for 循环等等时，我的脑子一片空白。我被要求写下以下算法的复杂性，但我不知道该怎么做。输入字符串只包含 A,B,C 和 D

string solution(string &S) {
    int length = S.length();
    int i = 0;
    while(i < length - 1)
    {
        if ( (S[i] == 'A' && S[i+1] == 'B') || (S[i] == 'B' && S[i+1] == 'A'))
        {
            S = S.erase(i,2);
            i = 0;
            length = S.length();
        }
        
        if ( (S[i] == 'C' && S[i+1] == 'D') || (S[i] == 'D' && S[i+1] == 'C'))
        {
            S = S.erase(i,2);
            i = 0;
            length = S.length();
        }
        
        i++;
    }
    
    return S;
}

这个算法的大 O 是什么？

Answer 1

我想这会是 O(n)，因为有一个循环遍历字符串。字符串越长，花费的时间就越多，所以我会说 O(n)

Answer 2

是O(n^2).

DDDDDDDDDDDDDDDDDDDABABABABABABABABABABABAB

前n/2个字符是D 最后 n/2 个字符是 AB

对于每个AB，（有1/4n这样的）- O(n)

您正在重置 i（从头开始迭代）
移动所有连续的元素以填充擦除后产生的空隙。

总计：

O(n)*(O(n) + O(n)) = O(n^2)

Answer 3

在大O表示法中，你给出了最坏情况的答案。这里最坏的情况是字符串不满足任何 if 语句。那么这里的时间复杂度就是O(n)了，因为只有一个循环。

Answer 4

人们很容易对算法效率的精确细节感到困惑。不过从根本上说，您所关心的只是操作是否是：

常数时间
与元素个数成正比
与元素个数的平方成正比

等...

请参阅此指南，了解如何估算复合操作的 Big-O： https://hackernoon.com/big-o-for-beginners-622a64760e2

big-O 本质上定义了一种方法的 worst-case 复杂性，特别是在非常大的情况下会观察到的效果 n.从表面上看，您会考虑重复操作多少次，但您还需要考虑是否有任何具体方法（例如字符串擦除、字符串长度）具有“恒定时间”、“与元素数量成比例”的复杂性, "与元素个数成正比 - 平方" 等等

因此，如果您的外循环执行 n 次扫描，但也调用同样对每个项目执行 n 次扫描的方法，那么您最终会得到 O(n^2)。

主要关注的是指数维度；你可以有一个非常 time-consuming linear-complexity 的操作，但也有一个非常快的，比如 power-of-4 元素。在这种情况下，它被认为是 O(n^4) （ 而不是 O(20000n + n^4) ）因为 因为 n 趋于无穷大，所有较小的指数因子都变得无关紧要。看这里：https://en.wikipedia.org/wiki/Big_O_notation#Properties

所以在你的情况下，你有以下循环：

重复扫描（设置i=0），其频率与匹配次数成正比（最坏情况n为了论证 - 即使它是一个分数，当 n 变成无穷大时，它仍然很重要 )。虽然这不是外层循环，但它从根本上决定了执行其他扫描的次数。
频率与长度成正比的字符串扫描(n)，PLUS中体现循环字符串擦除 - n 在最坏的情况下。请注意，这些操作是 孤立地执行的 ，一起由上述重复的频率决定。如其他地方所述，O(n)+O(n) 减少为 O(n) 因为我们只关心指数。

所以在这种情况下，复杂度是 O(n^2)

在评估任何算法的性能时，一个单独的考虑因素是缓存友好程度；使用散列图、链表等的算法被认为 prima-facie 更有效，但在某些情况下，O(n^2) 算法在缓存行内运行并且不t 调用页面错误或缓存刷新可以比内存分散在各处的更高效算法执行得更快。

如何计算时间复杂度？

How to calculate time complexitiy?

c++

big-o

time-complexity