请求确认三个函数的时间复杂度（Big O）判断是否正确

嘿，咱们来逐个拆解这三个函数的时间复杂度吧！你的判断有两个是完全正确的，但第一个函数的复杂度需要修正哦~

func1：递归实现的累加逻辑 #

先看函数代码：

int func1(int n, int a, int b){ 
    int res=0; 
    if (n == 1){ 
        res=a; 
    } else{ 
        res=res+func1(n-1,a,b)+b; 
    } 
    return res; 
}

你之前判断的O(2^n)是典型的分治类递归（比如未优化的斐波那契递归实现）的复杂度，但这个函数的递归路径非常直接：每次递归只会调用一次func1(n-1)，并没有分支成多个递归调用。递归的深度是n（从n一直递归到1），每一层递归里的操作（赋值、条件判断、加法）都是常数时间O(1)，总共有n次递归调用，所以它的时间复杂度是O(n)，而非O(2^n)。

func2：循环实现的累加逻辑 #

函数代码如下：

int func2(int n, int a, int b){ 
    int res = a; 
    for (int i=0; i<n-1; i++){ 
        res+=b; 
    } 
    return res; 
}

这个判断完全正确！循环会执行n-1次，每次循环内的加法操作都是常数时间，整体时间复杂度就是O(n)。

func3：公式直接计算 #

最后看这个函数：

int func3(int n, int a, int b){ 
    int res = a + (n-1)*b; 
    return res; 
}

你的判断也完全正确！不管n的取值多大，函数内部只做了一次乘法和一次加法，所有操作都是常数时间，因此时间复杂度是O(1)。

总结 #

• func1：O(n)（修正你的初始判断）
• func2：O(n)（判断正确）
• func3：O(1)（判断正确）

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