新的玩具到了！ 他就是——《算法精粹》，最近写机器学习代码红温了。大一写过一次mnist识别，后来也是整个寒假都不知道bp反传错在了哪里，就放下了，现在会过来重新看🐟📕学，依旧不知道错在哪里。刚好静下来玩点别的，这里大概就是我瞎玩的记录。

实际上写了三年代码，都没好好注意过算法这个事情，我写代码的优点就是能跑。。。然而除了这个没别的了。。。

递归算法

斐波那契数列

%%time
def fib(n: int) -> int:     # 标注函数的输出输入变量type是很好的代码习惯
    # 利用基线条件
    if n == 1:
        return 0
    elif n == 2:
        return 1
    # 开始递归
    else:
        return fib(n-1) + fib(n-2)
    
fib_lst = [fib(i) for i in range(1,40,1)]
print(fib_lst)

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169]
CPU times: total: 11.5 s
Wall time: 12 s

但是上面的方法只能对比较小的数适用，原因在于每个函数都会重复计算，也就是说这个函数每次都要递归到最后才结束运行。但实际上我们可以用结果缓存的技术避免重复计算

%%time
# 字典形式存储基线条件，这样每次就不用反复调用fib去计算了
# 后续的计算就会不断地将计算结果存到memo中，所谓用内存换时间
memo = {1:0, 2:1}

def fib2(n):
    if n not in memo:
        memo[n] = fib2(n-1) + fib2(n-2)
    return memo[n]
    
fib_lst = [fib2(i) for i in range(1,40,1)]
print(fib_lst)

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169]
CPU times: total: 0 ns
Wall time: 0 ns

看看这时间差就知道我们为什么需要学习算法了，不妨动手看看两种方法谁调用的fib()次数多。上面的代码其实就干了一件事情：缓存函数的执行结果，方便后面直接调用结果不用重复计算，也就是说任何函数只需要计算一次，后面再需要就不用重复算了。这个方法其实再python标准库中自带了一个装饰器可以通过添一行代码直接自动封装函数为结果缓存形式。

%%time
from functools import lru_cache

@lru_cache(maxsize=None) # 这一行告诉python随便缓存
def fib3(n):
    # 剩下的代码和之前一样
    if n == 1:
        return 0
    elif n == 2:
        return 1
    else:
        return fib3(n-1) + fib3(n-2)
    
fib_lst = [fib2(i) for i in range(1,40,1)]
print(fib_lst)

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169]
CPU times: total: 0 ns
Wall time: 0 ns

但这也不是性能最好的版本，递归就是写起来容易，从后往前求解问题。对于任何的递归问题，也可以考虑反过来从前往后解决问题。

def fib4(n):
    last, next = 0, 1   # 初始化初值条件
    for _ in range(1,n): # 如果你用for循环，但是不需要for循环中iterater的那个参数，可以直接用for _ in ... 而不是for idx in ...
        last, next = next, next + last
    return next

print(fib4(50))

12586269025

不难发现迭代的思想也是边求解边存储，或者说更新，只是这种思想用的更彻底，只存储迭代中要用到的n-1，n-2的值，并进行更新。上面代码要注意：

next, last = next + last, next

也能得到正确的结果，因为多重赋值的计算是基于原值而非更新后的值。

from typing import Generator

def fib5(n: int) -> Generator[int, None, None]:
    yield 0
    if n > 0: yield 1
    last, next = 0, 1
    for _ in range(1,n): 
        last, next = next, next + last
        yield next
    
for i in fib5(5):
    print(i)

0
1
1
2
3
5

yield是 Python 中的关键字，用于定义生成器。它与 return 类似，但 yield 不会终止函数，而是会暂停函数的执行，并保存当前状态。下一次调用时会从上一次暂停的地方继续执行。 生成器（Generator）：生成器是使用 yield 定义的函数，执行时会返回一个迭代器对象（就是你可以用for循环迭代，返回值赋予i）。与一次性返回所有值的函数不同，生成器在每次迭代时“按需”生成值，直到达到结束条件为止。这种特性使生成器特别适合生成可能非常大的序列（例如 Fibonacci 序列），因为它可以避免存储整个序列在内存中。

针对这段代码，yield是这样起作用的：

1. 第一次调用：yield 0

• 当 for i in fib5(5) 循环开始时，fib5(5) 被调用。生成器函数 fib5 执行到第一个 yield，即 yield 0。
• 此时，fib5 函数暂停，并将 0 返回给 for 循环中的 i，因此第一次循环中 print(i) 会打印 0。
• yield 的暂停效果允许 fib5 保留其内部状态（变量 last 和 next 等），并在下一次调用时从暂停点继续执行。

2. 第二次调用：yield 1

• 在 for 循环要求下一个值时，生成器从上次暂停的地方继续执行。
• 执行到 if n > 0: yield 1，这会返回 1，并再次暂停函数执行。
• 这一次 print(i) 会打印 1。

3. 第三次及之后的调用：循环中的 yield next

• 在 for 循环的下一次调用中，fib5 会进入循环 for _ in range(1, n)，其中每次迭代都会根据 Fibonacci 序列更新 last 和 next，并将新的 next 值作为 Fibonacci 数列的下一项。
• 例如，在第三次调用时：
• last, next = next, next + last 将 last 更新为 1（前一次的 next），并将 next 更新为 2。
• yield next 生成 1 并返回。
• 在第四次调用时，循环继续执行，生成新的 next 值 2。
• 在第五次调用时，生成新的 next 值 3。
• 每次 yield next 返回当前的 Fibonacci 数列项，并暂停执行，使得 for i in fib5(5) 能够在每次迭代中逐步获取 Fibonacci 数列的下一个值。

汉诺塔

搜索算法

后记：量子Grover搜索算法

众所周知，在$N$个毫无规律（没有实现进行任何排序等预处理操作）的元素中搜索指定元素，时间复杂度也就$\mathcal{O}(N)$，但是利用量子计算机上运行的Grover搜索算法，可以将时间复杂度降低为$\mathcal{O}(\sqrt{N})$。这是一个显著的飞跃！

算法的相关介绍见任何一本量子计算书籍，目前量子计算算法能解决的问题十分有限，Grover搜索（根号加速）、量子傅里叶变换（指数加速）以及矩阵相乘计算。是量子算法已经被严格证明严格优于经典算法的三种问题类型。剩下的问题是否适合使用量子算法求解还是一个未知数。