我真的很难计算大O。我掌握了基本知识，但当它嵌套到循环之类的时候，我的脑子就一片空白。我被要求写下下面算法的复杂性，但我不知道该怎么做。输入字符串只包含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是什么？
它是O(n^2)。
DDDDDDDDDDDDDDDDDDDABABABABABABABABABABABAB
前n/2个字符为D最后n/2个字符为AB
对于每个AB，(有1/4个这样的(-O(n(
- 您正在重置i(从开始迭代(
- 移动所有连续的元件以填充擦除之后产生的间隙
总计：
O(n)*(O(n) + O(n)) = O(n^2)
很容易被算法效率的精确细节所困扰。不过，从根本上讲，你关心的只是操作是否是：
- 恒定时间
- 与元素数量成比例
- 与元素数量的平方成比例
等等。。。
关于如何估计复合操作的Big-O，请参阅以下指南：https://hackernoon.com/big-o-for-beginners-622a64760e2
big-O本质上定义了方法的最坏情况复杂性，特别是在非常大的n下观察到的影响。从表面上看，你会考虑你重复一个操作的次数，但你也需要考虑是否有任何具体的方法(例如字符串擦除、字符串长度(具有复杂性，即"；"恒定时间"与元件的数量成比例"与元素的数量成比例-平方"；等等
因此，如果您的外循环执行n扫描，但也调用对每个项目执行n扫描的方法，那么您最终会得到O(n^2(。
主要关注的是指数维度；你可能有一个非常耗时的线性复杂度运算，但也有一个很快的，比如说，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(
在评估任何算法的性能时，需要单独考虑缓存友好程度；使用哈希图、链表等的算法被认为是更高效的，但在某些情况下，在缓存行内运行的O(n^2(算法不会调用页面错误或缓存刷新，其执行速度比内存分散在各处的所谓更高效的算法快得多。
我想这应该是O(n(，因为有一个循环通过字符串。字符串越长，所花费的时间就越多，所以我会说O(n(
在大O表示法中，您给出了最坏情况的答案。这里最糟糕的情况是字符串不满足任何if语句。那么这里的时间复杂度将是O(n(，因为只有一个循环。