c - 这个特定函数的时间复杂度\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) 表示法的重要之处在于它消除了“常量”。目标是随着输入大小的增长确定趋势，而不用担心具体数字。

可以将其视为在不知道 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 变得足够大(无论它可能是什么)，所有低阶项和常数因子在“大局”中变得无关紧要。

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