这个函数(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;
}
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
在大O中，这些都相当于O(n^2)。关键是，一旦n变得足够大(无论可能是什么(，所有低阶项和常数因素在"大局"中都变得无关紧要。
(值得强调的是，这就是为什么在小投入上你应该警惕过分依赖大O。那时，持续的开销仍然会产生很大的影响。
关键观察：内部循环在步骤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
理论上它是"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 = f1(123);之类的东西(。
换句话说;在实践中，原始函数的时间复杂度取决于函数的使用方式以及编译器的好坏程度。