这个特定函数的时间复杂度\大(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(n^2)。问题是，一旦n变得足够大(不管是什么)，所有的低阶项和常数因子在“大图”中就变得无关紧要了。

(值得强调的是，这就是为什么在小投入上，你应该警惕过度依赖大O -在这种情况下，经常性的间接费用仍然会产生巨大的影响。)

Answer 2

键观察：内循环在步骤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

Answer 3

理论上是"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)”。

请注意，从表面上看，这类优化似乎不切实际(因为最坏的情况下内存开销)；但是对于足够高级的编译器(例如，使用“整个程序优化”来检查所有调用方并确定n总是在一定范围内)，这并不是不可想象的。以类似的方式，并非所有调用方都使用常量(例如，足够高级的编译器可以用x = constant_calculated_at_compile_time替换x = constant_calculated_at_compile_time之类的东西)。

换句话说，在实践中，原始函数的时间复杂性取决于函数的使用方式和编译器的好坏。