fibonacci

递归

时间复杂度：O(2^n)

  • 递归函数 fibonacci 的时间复杂度可以表示为 T(n) = T(n-1) + T(n-2) + O(1),递归树的每一层都会产生两倍于上一层的节点数。

空间复杂度：O(n)

  • 递归调用的空间复杂度取决于递归树的深度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

import time
def fibonacci(n):
    if n<=1:
        return n;
    else:
     return fibonacci(n-2)+fibonacci(n-1)


t1 = time.time()
t = fibonacci(38)
t2 = time.time()
print('结果：%s, 运行时间：%s'%(t, t2-t1))


结果：39088169, 运行时间：4.343426465988159

动态规划

时间复杂度：O(n)

  • 这种方法通过从基础情况开始，逐步构建至所需的项，只需要 n-1 次循环迭代。
  • 每次迭代只进行了一些基本操作（加法和变量更新），因此整体时间复杂度是 O(n)。

空间复杂度：O(1)

  • 这种实现方式只用到了三个变量：**previousFib**, currentFib, 和临时变量 **newFib**。与 n 的大小无关，因此是常数空间复杂度 O(1)。
  • 这是一种非常空间效率高的实现方式，因为它不需要额外的空间来存储序列的中间值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import time
def fib(n):
    pre = 0
    cur = 1
    if n<= 1:
        return n
    for _ in range(n-1):
        new = pre + cur
        pre = cur
        cur = new
    return cur
t1 = time.time()
t = fib(38)
t2 = time.time()
print('结果：%s, 运行时间：%s'%(t, t2-t1))


结果：39088169, 运行时间：0.0

背包

假设我们有以下物品列表和它们的重量和价值：
物品1：重量 2，价值 3
物品2：重量 3，价值 4
物品3：重量 4，价值 5
物品4：重量 5，价值 8
我们的背包容量为 7。

递归

时间复杂度：O(2^n)

  • 每个递归调用会产生两个新的递归调用，指数级。

空间复杂度：O(n)

  • 由深度决定。
1
2
3
4
5
6
7
8
9
10
def ks(n,c):
    if n==0 or c ==0:
        result = 0
    elif w[n] > c:
        result = ks(n-1,c)
    else:
        tmp1 = ks(n-1,c)
        tmp2 = v[n] + ks(n-1,c-w[n])
        result = max(tmp1,tmp2)
    return result

动态规划

时间复杂度：O(n*c)

  • 外层循环从 1 到 n，内层循环从 1 到 c，因此总的计算次数为 O(n * c)。

空间复杂度：O(n*c)

  • 创建了一个二维数组 dp，大小为 (n+1) x (c+1)
1
2
3
4
5
6
7
示例图
    0   1   2   3   4   5   6   7
0   0   0   0   0   0   0   0   0
1   0   0   3   3   3   3   3   3
2   0   0   3   4   4   7   7   7
3   0   0   3   4   5   7   8   8
4   0   0   3   4   5   7   8   8
1
2
3
4
5
6
7
8
9
10
11
12
13
14
def ks(n, c):
    # 创建一个二维数组来存储子问题的解
    dp = [[0] * (c + 1) for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        for j in range(1, c + 1):
            if w[i] > j:
                # 当前物品的重量大于背包容量，无法放入
                dp[i][j] = dp[i - 1][j]
            else:
                # 考虑放入或不放入当前物品，选择价值较大的方案
                dp[i][j] = max(dp[i - 1][j], v[i] + dp[i - 1][j - w[i]])
    
    return dp[n][c]