1

我是一名计算机科学专业的学生，​​我下周参加了期末考试，我很困惑试图找出以下函数的时间复杂度。你能给我解释一下吗？

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

1 回答 1

2

对于这样的问题，你应该先弄清楚递推关系（通过查看代码），然后解决递推关系（使用数学）。

要执行第 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。因为我们除以n2，我们还不如只选择偶数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)是一条线的方程。

于 2021-06-04T15:39:47.420 回答