0%

递归如何计算时间复杂度

看例子:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
package main

import (
"fmt"
)

func test(n int) int {
if n < 1 {
return 0
}
if n == 2 {
return 2
}
if n == 1 {
return 1
}
return test(n-1) + test(n-2)
}

func main() {
fmt.Println(test(10))
}

递归的计算往往都可以抽象成一棵树,上面的树就是这样的:

可以看出总的计算次数是 2^0+2^1+2^2+…+2^n = 2^(n+1) - 1,就可以认为时间复杂度是O(2^n)