递归函数的时间复杂度

Question

我是一名计算机科学专业的学生，我下周要参加期末考试，我在尝试计算以下函数的时间复杂度时感到困惑。你能给我解释一下吗？

int bss(int n){
    if(n <= 1)
        return n;
    
    return bss(n/2) + bss(n/2);
}

Answer 1

像这样的问题，应该先搞清楚递推关系（看代码），再求解递推关系（用数学）。

要执行第 1 步，我们需要查看每一行，看看它对我们算法的总体运行时间 T(n) 有何贡献：

int bss(int n){
    if(n <= 1)                        // contributes a constant time a
        return n;                     // contributes a constant time b in the base case only

    return bss(n/2) + bss(n/2);       // contributes a constant time c
                                      // for the two divisions and one addition,
                                      // plus 2T(n/2)
}

加起来有两种情况：

n <= 1: T(n) = a + b
n  > 1: T(n) = a + c + 2T(n/2)

为了求解这个系统，我们可以开始为 n 的值写出项。因为我们将n除以2，所以我们不妨只选择偶数n。另外，如果已经计算出 T(n/2) 来计算 T(n) 就好了；所以，我们每次都可以将 n 的测试值加倍。

n    T(n)
---------
1    a + b
2    a + c + 2T(1) = a + c + 2a + 2b = 3a + 2b + c
4    a + c + 2T(2) = a + c + 6a + 4b + 2c = 7a + 4b + 3c
8    a + c + 2T(4) = a + c + 14a + 8b + 6c = 15a + 8b + 7c
16   a + c + 2T(8) = a + c + 30a + 16b + 14c = 31a + 16b + 15c
...
k    (2k - 1)a + kb + (k - 1)c

根据我们看到的模式，n = k 的解似乎是 (2k - 1)a + kb + (k - 1)c。我们可以尝试通过将其代入我们的方程式来验证这一点：

k = 1: (2k - 1)a + kb + (k - 1)c = a + b = T(1) ... correct
k > 1:

(2k - 1)a + kb + (k - 1)c ?= a + c + 2[(2k/2 - 1)a + (k/2)b + (k/2 - 1)c]
                          ?= a + c + (2k - 2)a + kb + (k - 2)c
                          ?= a + c + 2ka - 2a + kb + kc - 2c
                          ?= -a -c + 2ka + kb + kc
                          ?= (2k - 1)a + kb + (k - 1)c ... correct

所以，我们已经找到了递归关系的有效解。解决方案是：

T(n) = (2n - 1)a + nb + (n - 1)c

重新排列：

T(n) = (2a + c + 1)n - (a + c)

T(n)是直线方程

递归函数的时间复杂度

Time complexity for a recursive function

algorithm

time

time-complexity