如何通过递推关系证明该Python算法的时间复杂度为O(n)

首先给出待分析的代码实现：

def exercise2(N):
    count = 0 
    i = N
    while ( i > 0 ):
        for j in range(0,i): 
            count = count + 1
        i = i//2

循环执行逻辑拆解 #

算法的执行由两层循环构成：

• 外层while循环控制变量i从初始值N开始，每次循环结束后执行整除2操作（i = i//2），直到i<=0时终止，因此i的取值序列为N, N//2, N//4, N//8 ... 1, 0。
• 内层for循环每次从0遍历到当前i值（不包含i），单次内层循环固定执行1次count自增操作，因此单次外层循环对应的基本操作次数，等于当前外层循环的i值。

递推关系建立 #

我们定义T(k)为外层循环初始i值为k时，算法执行的总基本操作次数，可以得到如下递推关系：

1. 边界条件：当k=0时，外层循环不触发，T(0) = 0
2. 递推式：当k>0时，当前轮次外层循环会执行k次基本操作，之后i变为k//2，剩余操作次数等价于初始i值为k//2时的总操作次数，即：
   T(k) = T(k//2) + k

递推式展开与求和 #

将递推式逐层展开直到触达边界条件：

T(N) = N + T(N//2)
     = N + N//2 + T(N//4)
     = N + N//2 + N//4 + T(N//8)
     = N + N//2 + N//4 + ... + 1 + T(0)
     = N + N//2 + N//4 + ... + 1

这是一个公比为1/2的等比数列求和序列，即使考虑整数整除带来的截断误差，每一项的取值都不会超过对应公比序列的理论值：

• 等比数列无穷项求和的上界为 N * (1 + 1/2 + 1/4 + 1/8 + ...) = N * 2 = 2N
• 实际有限项的总和一定小于2N，例如N=8时总和为8+4+2+1=15 < 16=28；N=7时总和为7+3+1=11 <14=27。

大O复杂度结论 #

根据大O记号的定义：存在正常数c=2、n₀=1，对所有N≥n₀，都满足T(N) ≤ c*N，因此该算法的时间复杂度为O(n)。

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