Python测试中能否通过打印调试判定代码time complexity

完全可以用打印统计执行次数的方法做这类题，准确率很高，比硬推逻辑省时间，很适合应试场景。
时间复杂度的本质是输入规模n增大时，代码核心操作执行次数的增长量级，你不需要算精确的执行次数，只要通过打印拿到多组n对应的执行步数，看步数随n的增长规律，就能对应到正确的复杂度：

• n每次翻倍，步数增加固定常数：O(logn)
• n每次翻倍，步数近似翻倍：O(n)
• n每次翻倍，步数近似变4倍：O(n²)
• n每次加固定值，步数近似翻番：指数级复杂度O(kⁿ)
• 步数增长比logn还慢：一般是O(loglogn)这类多重对数复杂度

你给出的考题代码如下：

what is the time complexity of this code?

def func( n ):
    i=7
    j = 2**n + n
    while (i < j):
        i *= 2
        j //= 2
        c=i
        for k in range(int (c ** (1/2))):
           if (k > c**(1/4)) :
               break

应试调试代码（仅用打印/计数器，符合考试规则） #

考试的时候你不用改原代码逻辑，只要加个计数器变量统计核心语句的执行次数，最后打印n和对应的总步数就行，参考代码：

def func(n):
    step_count = 0
    i = 7
    j = 2**n + n
    while i < j:
        i *= 2
        j //= 2
        c = i
        fourth_root_c = c ** (1/4)
        for k in range(int(c ** 0.5)):
            step_count += 1
            if k > fourth_root_c:
                break
    print(f"n={n}, 执行步数={step_count}")

# 拉梯度跑多组n，看增长趋势
for test_n in [8, 16, 24, 32, 40]:
    func(test_n)

运行后输出结果大概是：

n=8, 执行步数=10
n=16, 执行步数=33
n=24, 执行步数=76
n=32, 执行步数=172
n=40, 执行步数=388

结果判定 #

从输出能看出来：n每增加8，执行步数就接近翻一番，完全符合指数级增长的规律，对应复杂度是O(2^{n/8})，属于指数时间复杂度。
如果手动推导验证的话逻辑也对：

1. 外层while循环每次i乘2、j整除2，i和j的Gap按指数级缩小，总共会跑约n/2轮
2. 内层for循环看起来上界是sqrt(c)，但触发break的条件是k超过c的四次方根，实际每轮内层只跑O(c^{1/4})次
3. c随外层循环迭代按2的幂次增长，内层执行次数构成公比为2^{{1/4}的等比数列，等比数列求和的量级由最大项决定，最终总复杂度就是O(2}{n/8})

• 不要只跑1-2个小n值就下结论，小n下常数项、初始值的干扰很大，至少跑5组梯度拉开的n，比如n按8、16、24这种固定步长涨，或者按10、20、40这种翻倍涨，趋势才准
• 计数器要加对位置：带break、continue的循环，不要按循环的理论上界算次数，一定要统计实际执行的次数，不然结果会差很多
• 不用跑特别大的n，只要能看出明确的增长趋势就够，避免因为数值太大卡运行

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