如何计算指定循环的代价函数及其Big-O表示法？

代价函数推导 #

先看给定的循环代码：

for (int i=3; i^2<N; i=i+2) {
    // One operation here
}

循环的代价函数等于它的执行次数，因为每次循环内固定执行1个操作。推导过程如下：

• 循环终止条件是i² ≥ N，换句话说，只要i < √N，循环就会继续执行。
• i从3开始，每次步长加2，取值序列为3、5、7……k（k是小于√N的最大奇数）。
• 这是首项为3、公差为2的等差数列，第n项的表达式为2n + 1（代入n=1得3，n=2得5，完全匹配序列）。
• 令第n项小于√N，得到不等式：2n + 1 < √N，解后得n < (√N - 1)/2。循环次数n就是这个值的向下取整。
• 还要考虑边界情况：当N≤9时，初始i=3的平方等于9，此时i²<N不成立，循环执行0次。

最终代价函数T(N)：

• 当N ≤9时，T(N) = 0
• 当N >9时，T(N) = ⌊(√N - 1)/2⌋

Big-O表示法 #

分析代价函数的增长趋势：(√N -1)/2中的常数项和系数对渐进复杂度没有影响，忽略后可得循环的时间复杂度为O(√N)。

内容的提问来源于stack exchange，提问作者Udbhav Prasad