首页 > 试题广场 >

有如下递归函数 test(n)，其时间复杂度为多少

[单选题]

有如下递归函数 test(n)，其时间复杂度为多少？

int  test(int n) {
    if (n <= 1) return 1;
    return (2 *  test(n - 1) + 3 *  test(n - 2));
}

```
O(logn)
```
```
O(nlogn)
```
```
O(n^2)
```
```
O(n^3)
```
```
O(2^n)
```

查看正确选项

Yanshsf

每一层递归调用两次递归，所以是2^n

发表于 2021-06-26 17:39:59 回复(1)

刘汉东

对于这个递归函数，可以使用递归树或者递归展开来分析时间复杂度。

递归树的方式是将每次递归的调用画成一棵树，然后计算每一层的节点数。在这个函数中，每次递归会产生两个子问题，因此递归树是一棵二叉树。根据递归函数的定义，树的深度是 n，因此最后一层有 2^n 个节点。其余层的节点数是前一层的两倍，因此总共的节点数是：

1 + 2 + 4 + ... + 2^n = 2^(n+1) - 1

因此，递归函数的时间复杂度是 O(2^n)。

递归展开的方式是将递归函数展开成一系列非递归的表达式。展开后的函数如下：

test(n) = 2 * test(n-1) + 3 * test(n-2) = 2 * (2 * test(n-2) + 3 * test(n-3)) + 3 * test(n-2) = 2^2 * test(n-2) + (2 * 3 + 3) * test(n-3) = 2^2 * test(n-2) + 2^1 * test(n-3) + 3^1 * test(n-4) = 2^3 * test(n-3) + 2^2 * test(n-4) + 3^1 * test(n-4) = 2^3 * test(n-3) + (2^2 + 3^1) * test(n-4) = 2^4 * test(n-4) + (2^3 + 2^2 + 3^1) * test(n-5) ... = 2^(n-1) * test(1) + (2^(n-2) + 2^(n-3) + ... + 2^0) * test(0)

其中，test(1) 和 test(0) 都是常数，因此时间复杂度取决于展开式中加和符号后面的部分。这一部分可以写成：

2^(n-2) + 2^(n-3) + ... + 2^0

这是一个等比数列，其和为 2^(n-1) - 1。因此，展开后的函数的时间复杂度是 O(2^n)。

因此，无论是使用递归树还是递归展开的方式，都可以得到递归函数 test 的时间复杂度是 O(2^n)。

发表于 2023-03-27 16:30:59 回复(0)