我是否正确计算了 big-o？

Question

以下循环：

for(var i = 0; i < A; i++) {
  for(var j = 0; j < B; j++) {
    for(var k = 0; k < C; k++) {
      //not concerned with instructions here
    }
  }
}

据我了解，每个循环的复杂度为 2n+2，因此我基于此计算出上述嵌套循环的复杂度为 (2A+2)*((2B+2)*(2C+2))。这个对吗？如果是这样，我该如何摆脱它？

编辑 1

自从有人提出这个问题以来，我学到了很多关于 big-o 的知识，并且发现了一个有趣的可视化效果，我想把它放在这里以防其他人遇到这个话题。有关详细参考（比学生教科书更好）和原始绘图，请查看 Wikipedia. There are a variety of time complexities 那里的解释。

由于原始问题涉及三个嵌套循环，每个循环都有不同的 n，因此 big-o 是答案中提到的 O(A * B * C)。当我们尝试为这样的东西确定 big-o 时，困难就出现了，其中 A 是一个对象数组（在某些语言中也称为散列）。算法本身无意义，仅供演示（虽然之前面试也被问过无意义）：

var cache = {}
for(var i = 0; i < A.length; i++) {
  var obj = A[i]

  if(!obj.someProperty) {
    continue;
  }
  else if(cache[obj.someProperty]) {
    return obj;
  }
  else if(obj.someProperty === 'some value') {
    for(var j = 1; j < A.length; j++) {
      if(A[j].someProperty === obj.someProperty) {
        cache[obj.someProperty] = obj.someProperty
        break
      }
    }
  }
  else {
    for(var j = i; j < A.length; j++) {
      //do something linear here
    }
  }
}

外循环是O(A.length)。对于内部循环：

obj.someProperty 不存在，根据理论我们没有复杂性。
obj.someProperty 在缓存中，理论上我们没有复杂性。
obj.someProperty 等于 some value 以下之一：
1. 我们有 O(A.length - 1) 个没有重复的
2. 我们有 O(A.length - x)，其中 A.length - x 指的是 A 中的重复索引。
其他的，我们有O(log A.length)

当 A[0] 和 A[1] 被认为是重复的并且 A[0].someProperty === 'some value' 因为我们将有一个外循环迭代和一个内循环迭代（3.2 A.length - x = index 1，最后第 3 次迭代 returns 缓存值完全脱离外循环。更糟糕的是，我们将 O(A.length log A.length) 作为外循环和内循环 4当没有对象具有 someProperty === 'some value'.

时耗尽

为了“优化”这个算法，我们可以简单地写成如下：

for(var i = 0; i < A.length; i++) {    
  if(A[i].someProperty === 'some value') {
    return obj
  }
  else {
    for(var j = i; j < A.length; j++) {
      //do something linear here
    }
  }
}

Answer 1

最外层的 for 循环总共运行 A 次。对于每次迭代，第二级 for 循环运行 B 次，每次触发省略指令的 C 次迭代。

因此，时间复杂度为O(A * B * C)。

Answer 2

计算时间复杂度时忽略常量

   O((2A+2)*((2B+2)*(2C+2)))
=> O((2A)(2B)(2C))
=> O(8*ABC)
=> O(ABC)

我是否正确计算了 big-o？

Am i calculating the big-o correctly?

complexity-theory

big-o

time-complexity

nested-loops