Python 100天-從新手到大師學習筆記番外篇：演算法入門系列課程1 — 周而復始

jackfrued/Python-100-Days

算法概述

1. 什么是算法？
2. 解决问题的正确方法和具体的实施步骤。
3. 例子1：如何在两栋相距50m的大楼的两个房间牵一条线（两个房间都有窗）？

• 养一只鸟（如鸽子），将线送过去
• 用很长的杆子将线递过去
• 用无人机（遥控飞行器）将线送过去

1. 如何评价这些方法的好坏？少花钱，不费事！
2. 例子2：大教室里坐了几百名学生一起听课，如何快速的统计学生人数？
3. 例子3：向列表容器中逆向插入100000个元素。

方法1：

nums = []
for i in range(100000):
    nums.append(i)
nums.reverse()

方法2：

nums = []
for i in range(100000):
    nums.insert(0, i)

例子3：生成Fibonacci数列（前100个Fibonacci数）。

方法1 — 递推：

a, b = 0, 1
for num in range(1, 101):
    a, b = b, a + b
    print(f'{num}: {a}')

方法2 — 递归：

def fib(num):
    if num in (1, 2):
        return 1
    return fib(num - 1) + fib(num - 2)


for num in range(1, 101):
    print(f'{num}: {fib(num)}')

方法3 — 改进的递归：

def fib(num, temp={}):
    if num in (1, 2):
        return 1
    elif num not in temp:
        temp[num] = fib(num - 1) + fib(num - 2)
    return temp[num]

方法4 — 改进的递归：

from functools import lru_cache


@lru_cache()
def fib(num):
    if num in (1, 2):
        return 1
    return fib(num - 1) + fib(num - 2)

如何评价算法的好坏？

渐近时间复杂度和渐近空间复杂度。

大O符号的意义？

表示一个函数相对于输入规模的增长速度，也可以称之为函数的数量级。

穷举法

在计算机科学中，穷举法或者暴力搜索法是一个非常非常直观的解决问题的方法，这种方法通过一项一项的列举解决方案所有可能的候选项以及检查每个候选项是否符合问题的描述，最终得到问题的解。

虽然暴力搜索很容易实现，并且如果解决方案存在它就一定能够找到，但是它的代价是和候选方案的数量成比例的，由于这一点，在很多实际问题中，消耗的代价会随着问题规模的增加而快速地增长。因此，当问题规模有限或当存在可用于将候选解决方案的集合减少到可管理大小时，就可以使用暴力搜索。另外，当实现方法的简单度比速度更重要的时候，也可以考虑使用这种方法。

暴力破解密碼

import re

import PyPDF2

with open('Python_Tricks_encrypted.pdf', 'rb') as pdf_file_stream:
    reader = PyPDF2.PdfFileReader(pdf_file_stream)
    with open('dictionary.txt', 'r') as txt_file_stream:
        file_iter = iter(lambda: txt_file_stream.readline(), '')
        for word in file_iter:
            word = re.sub(r'\s', '', word)
            if reader.decrypt(word):
                print(word)
                break