递归函数时间复杂度求解咨询：两个递归函数的复杂度判定疑问

嘿，你对第一个函数的时间复杂度判断完全正确！让我帮你把两个函数的时间复杂度都拆解清楚：

先看func_1的代码：

def func_1(n):
    if n <= 0:
        return True
    return func_1(n // 2)

每次递归调用时，n都会被整除2，直到n小于等于0才停止递归。咱们来数一下递归的次数：假设n是正整数，第一次调用n，第二次n//2，第三次n//4……直到变成0，这个过程的次数就是以2为底n的对数，也就是log₂n次。

而每次递归内部只做了一个简单的条件判断和返回操作，属于*O(1)*的常数时间操作。所以总的时间复杂度就是递归次数乘以每次的操作时间，也就是O(log n)，你的判断完全没问题！

再看func_2：

def func_2(n):
    if n <= 0:
        return
    x = 0
    for i in range(n):
        x += 0.1
    return func_2(n // 2)

这个函数和func_1的递归逻辑一样，但每次递归多了一个**O(n)**的循环（循环执行n次，每次都是常数操作）。咱们需要把每次递归里的循环操作次数加起来：

第一次调用时，循环执行n次；
第二次调用func_2(n//2)，循环执行n//2次；
第三次是n//4次；
……
直到最后一次调用func_2(0)，循环不执行。

这是一个等比数列求和：n + n/2 + n/4 + ... + 1，这个数列的和是2n - 1（当n是2的幂时），即使n不是2的幂，总和也不会超过2n。所以总的时间复杂度是O(n)。

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