这个特定函数的时间复杂度 \big(O) 是多少？

Question

这个函数(f1)的时间复杂度是多少？

正如我所见，第一个循环(i=0)-> (n/4 次) 第二个(i=3)->(n/4 - 3 次).. ..等等，结果是：(n/3)*(n/4 + (n-3)/4 + (n-6)/4 + (n-9)/4 ....

到此为止，如何继续？

int f1(int n){
  int s=0;
  for(int i=0; i<n; i+=3)
    for (int j=n; j>i; j-=4)
      s+=j+i;
  return s;
}

Answer 1

Big(O) 符号的重要之处在于它消除了 'constants'。 objective 是确定趋势随着输入大小的增长而不关心特定数字。

可以将其视为在不知道 x 轴和 y 轴的数字范围的图形上确定曲线。

因此在您的代码中，即使您在每个循环的每次迭代中跳过 n 范围内的大部分值，这也是以恒定速率完成的。所以不管你实际跳过了多少，这仍然是相对于 n^2.

的比例

如果您计算了以下任何一项都没有关系：

1/4 * n^2
0.0000001 * n^2
(1/4 * n)^2
(0.0000001 * n)^2
1000000 + n^2
n^2 + 10000000 * n

在Big O中，这些都相当于O(n^2)。关键是一旦 n 变得足够大足够（无论可能是什么），所有低阶项和常数因子在 'big picture' 中变得无关紧要。

(值得强调的是，这就是为什么在小输入上你应该警惕过度依赖大 O。那时候持续的开销仍然会产生很大的影响。)

Answer 2

理论上是 "O(n*n)"，但是...

如果编译器想要将其优化成这样怎么办：

int f1(int n){
  int s=0;
  for(int i=0; i<n; i+=3)
    s += table[i];
  return s;
}

甚至这样：

int f1(int n){
  if(n <= 0) return 0;
  return table[n];
}

那么也可以是"O(n)"或者"O(1)".

请注意，从表面上看，这些优化似乎不切实际（由于最坏情况下的内存成本）；但是使用足够先进的编译器（例如使用 "whole program optimisation" 检查所有调用者并确定 n 始终在某个范围内）这并非不可想象。以类似的方式，所有调用者都使用常量并非不可能（例如，足够先进的编译器可以将 x = f1(123); 替换为 x = constant_calculated_at_compile_time）。

换句话说；实际上，原始函数的时间复杂度取决于函数的使用方式以及good/bad编译器的方式。

Answer 3

关键观察： 内循环在步骤i中执行(n-i)/4次，因此在步骤n-i中执行i/4次。

现在对 i = 3k, 3(k-1), 3(k-2), ..., 9, 6, 3, 0 的所有这些数量求和，其中 3k 是 n 之前 3 的最大倍数（即 3k <= n < 3(k+1)）：

3k/4 + 3(k-1)/4 + ... + 6/4 + 3/4 + 0/4 = 3/4(k + (k-1) + ... + 2 + 1)
                                        = 3/4(k(k+1))/2
                                        = O(k^2)
                                        = O(n^2)

因为 k <= n/3 <= k+1 因此 k^2 <= n^2/9 <= (k+1)^2 <= 4k^2

这个特定函数的时间复杂度 \big(O) 是多少？

What is the time complexity \big(O) of this specific function?

c

complexity-theory

big-o

loops

time-complexity