Big O Notation 求和混淆

Question

我希望使用 Big O Notation 来说服其他人关于代码增强 - 既是为了效率又是为了可读性。但是我不确定我是不是错了。

从大 O 表示法，我了解到 O(n) + O(n) = O(n)（近似值）。也就是说，前面的常数可以忽略不计。

但是，举个例子，假设一个for循环

//Case 1: One For-Loop - O(n)
for(var i=0;i<n;i++)
{
   doA(i);
   doB(i);
}

为了更好的可读性，我更喜欢这样写：

//Case 2: Two For-Loop - O(n) + O(n)
function doA(){
   for(var i=0;i<n;i++){
     //do logic A
   }
}

function doB(){
   for(var i=0;i<n;i++){
      //do Logic B
   }
}

这样，我就可以直接打电话了

doA();
doB();

...外面没有for循环。

现在的问题是，我无法说服自己，如果 for 循环实际上需要 10 秒。那么O(n) + O(n)其实就是20秒。我们怎么能说 O(n) + O(n) 近似于 O(n)

Answer 1

How can we say that O(n) + O(n) is approximate-able to O(n)

对于你（大学）的担忧，有四种类型的复杂性：

对数 ( O(log(n)) )
线性 ( O(n) )
多项式 ( O(n^k, k elemOf {1,2,3,...}) )
指数 ( O(n^n) )

你的问题是指第二种情况：

在Infinity中O(n) + O(n)是O(n)，因为两者都是线性的。
所以你可以把它想象成

linear + linear = linear

线性意味着如果输入量加倍，处理时间也会加倍。

在另一种较慢的情况下，处理时间将为

n^2, n^3, ... 在多项式复杂度[=43的情况下=]（将输入量加倍在 input^2、input^3 或 input^4 处理时间)

n^n（实际上是big/slow） ...在指数复杂度的情况下（乘以输入量本身会导致处理时间乘以自身，例如 3*3 = 9, 4*4 = 16, 5*5 = 25...).

Big O Notation 求和混淆

Big O Notation Summation confusion

big-o