Lab1斐波那契数列的实现与分析

1.多种算法实现斐波那契数列

1.1递归算法：

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

for i in range(50):
    start = time.time()
    num = fibonacci(i)
    end = time.time()
    print(str(i),num,str(end-start))

运行结果：

0 0 0.0
1 1 0.0
2 1 0.0
3 2 0.0
4 3 0.0
5 5 0.0
6 8 0.0
7 13 0.0
8 21 0.0
9 34 0.0
10 55 0.0
11 89 0.0
12 144 0.0
13 233 0.0
14 377 0.0
15 610 0.0
16 987 0.0
17 1597 0.0
18 2584 0.0009999275207519531
19 4181 0.0
20 6765 0.0010080337524414062
21 10946 0.0
22 17711 0.0009984970092773438
23 28657 0.0019931793212890625
24 46368 0.00402379035949707
25 75025 0.0064814090728759766
26 121393 0.010526657104492188
27 196418 0.017529726028442383
28 317811 0.028643131256103516
29 514229 0.04460453987121582
30 832040 0.07278108596801758
31 1346269 0.1158914566040039
32 2178309 0.19428801536560059
33 3524578 0.31592774391174316
34 5702887 0.49991607666015625
35 9227465 0.8131046295166016
36 14930352 1.300654411315918
37 24157817 2.1591711044311523
38 39088169 3.494837522506714
39 63245986 5.695884943008423
40 102334155 9.020411729812622
41 165580141 14.685189008712769
42 267914296 24.06705355644226
43 433494437 47.775323152542114

时间太长，不运行完了

1.2迭代算法:

import time

def fibonacci_iterative(n):
    if n <= 1:
        return n
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

for i in range(50):
    start = time.time()
    num = fibonacci_iterative(i)
    end = time.time()
    print(str(i),num,str(end-start))

运行结果：

40 102334155 0.0
41 165580141 0.0
42 267914296 0.0
43 433494437 0.0
44 701408733 0.0
45 1134903170 0.0
46 1836311903 0.0
47 2971215073 0.0
48 4807526976 0.0
49 7778742049 0.0

不过多展示，但用时极少

1.3矩阵乘法算法：

import time
import numpy as np

def matrix_power(matrix, n):
    result = np.identity(2, dtype=object)
    while n > 0:
        if n % 2 == 1:
            result = np.dot(result, matrix)
        matrix = np.dot(matrix, matrix)
        n //= 2
    return result

def fibonacci_matrix(n):
    if n <= 1:
        return n
    matrix = np.array([[1, 1], [1, 0]], dtype=object)
    result_matrix = matrix_power(matrix, n - 1)
    return result_matrix[0][0]

for i in range(50):
    start = time.time()
    num = fibonacci_matrix(i)
    end = time.time()
    print(str(i),num,str(end-start))

运行结果：

40 102334155 0.0
41 165580141 0.0
42 267914296 0.0
43 433494437 0.0
44 701408733 0.0
45 1134903170 0.0
46 1836311903 0.0
47 2971215073 0.0
48 4807526976 0.0
49 7778742049 0.0

时间极少

1.4通项公式算法（比内公式）：

import time
import math

def fibonacci_binet(n):
    phi = (1 + math.sqrt(5)) / 2
    return round((phi**n - (-1 / phi)**n) / math.sqrt(5))

for i in range(50):
    start = time.time()
    num = fibonacci_binet(i)
    end = time.time()
    print(str(i),num,str(end-start))

运行结果：

40 102334155 0.0
41 165580141 0.0
42 267914296 0.0
43 433494437 0.0
44 701408733 0.0
45 1134903170 0.0
46 1836311903 0.0
47 2971215073 0.0
48 4807526976 0.0
49 7778742049 0.0

时间也极少

1.5带记忆化的递归算法：

import time

def fibonacci_memoization(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fibonacci_memoization(n - 1, memo) + fibonacci_memoization(n - 2, memo)
    return memo[n]

for i in range(50):
    start = time.time()
    num = fibonacci_memoization(i)
    end = time.time()
    print(str(i),num,str(end-start))

运行结果：

40 102334155 0.0
41 165580141 0.0
42 267914296 0.0
43 433494437 0.0
44 701408733 0.0
45 1134903170 0.0
46 1836311903 0.0
47 2971215073 0.0
48 4807526976 0.0
49 7778742049 0.0

时间极少。

可以看到，除了递归算法要花费极长的时间外，其他的算法用时都很短。

那么为什么会这样，这几种算法的优缺点又是什么呢？

2.分析算法优点与缺点

2.1 分析不同算法的时间复杂度

1. 递归算法：
   • 时间复杂度：O(2^n)
   • 分析：递归算法的时间复杂度是指数级的，因为每次调用都会产生两个新的递归调用，导致计算量呈指数增长。例如，计算 fibonacci(40) 需要进行大约 2^40 次递归调用，计算量非常大。
2. 迭代算法：
   • 时间复杂度：O(n)
   • 分析：迭代算法通过循环来计算斐波那契数列，每次循环只进行常数次操作，因此时间复杂度是线性的。计算 fibonacci(40) 只需要进行 40 次循环。
3. 矩阵乘法算法：
   • 时间复杂度：O(log n)
   • 分析：矩阵乘法算法利用矩阵快速幂的方法来计算斐波那契数列。矩阵的幂运算可以通过二分法快速计算，因此时间复杂度是对数级的。计算 fibonacci(40) 只需要进行大约 log2(40) ≈ 5 次矩阵乘法。
4. 通项公式算法（比内公式）：
   • 时间复杂度：O(1)
   • 分析：通项公式算法直接使用数学公式计算斐波那契数列，时间复杂度是常数级的。计算 fibonacci(40) 只需要进行一次公式计算。
5. 带记忆化的递归算法：
   • 时间复杂度：O(n)
   • 分析：带记忆化的递归算法通过缓存已经计算过的斐波那契数，避免了重复计算。每个斐波那契数只需要计算一次，因此时间复杂度是线性的。计算 fibonacci(40) 只需要进行 40 次递归调用。

2.2 对比不同算法的优点与缺点

1. 递归算法：
   • 优点：代码简单，易于理解。
   • 缺点：时间复杂度高，计算量大，容易导致栈溢出，不适合计算较大的斐波那契数。
2. 迭代算法：
   • 优点：时间复杂度低，计算速度快，适合计算较大的斐波那契数。
   • 缺点：代码相对复杂一些，需要手动管理循环和变量。
3. 矩阵乘法算法：
   • 优点：时间复杂度非常低，适合计算非常大的斐波那契数。
   • 缺点：代码实现复杂，需要理解矩阵运算和快速幂算法。
4. 通项公式算法（比内公式）：
   • 优点：时间复杂度最低，计算速度最快，适合计算非常大的斐波那契数。
   • 缺点：由于浮点数精度问题，当 n 较大时，计算结果可能会有误差。
5. 带记忆化的递归算法：
   • 优点：时间复杂度低，避免了重复计算，适合计算较大的斐波那契数。
   • 缺点：需要额外的空间来存储已经计算过的斐波那契数，空间复杂度为 O(n)。

2.3 总结用空间换时间的算法特点

• 带记忆化的递归算法 和 矩阵乘法算法 都是典型的用空间换时间的算法。
  • 带记忆化的递归算法 通过缓存已经计算过的结果，避免了重复计算，从而将时间复杂度从指数级降低到线性级。
  • 矩阵乘法算法 通过快速幂运算，将时间复杂度降低到对数级，但需要额外的空间来存储矩阵。
• 通项公式算法 虽然时间复杂度最低，但由于浮点数精度问题，不适合计算非常大的斐波那契数。
• 迭代算法 是一种平衡了时间和空间复杂度的算法，适合大多数场景。

3.总结

3.1 算法总结

• 递归算法 适合小规模计算，代码简单但效率低。
• 迭代算法 适合中等规模计算，效率高且代码相对简单。
• 矩阵乘法算法 和 通项公式算法 适合大规模计算，但实现复杂。
• 带记忆化的递归算法 适合中等规模计算，效率高但需要额外空间。

3.2 个人总结

本次实验报告的初始内容学习主要来自于大模型，如除递归之外的算法，主要依赖于大模型我才能把他写出来，对各类算法的了解度还是较少，在后期需要补充学习。

但本次学习让我加深了对各类算法的认知，让我更加了解了各类算法的优缺点和时间复杂度，是一次颇有意义的学习。

这个也是作业