算法

tags: 知识点 算法 2020年 01月

洗牌算法

洗牌算法Fisher–Yates shuffle 算法由 Ronald Fisher 和 Frank Yates 于 1938 年提出，在 1964 年由 Richard Durstenfeld 改编为适用于电脑编程的版本。这个算法很牛逼却很好理解，通俗的解释就是：将最后一个数和前面任意 n-1 个数中的一个数进行交换，然后倒数第二个数和前面任意 n-2 个数中的一个数进行交换。。。

参考链接: 洗牌算法

TODO 数据结构基础知识 数据结构是什么，其特性有缺点，使用场景，基础使用等等

TODO 算法的基础使用，优缺点，使用场景，底层逻辑，时间空间复杂度分析等等

数据结构

常见数据结构与算法整理总结(上)

算法

迭代法

关键点:

• 将一个原问题修改为子问题
• 对子问题重复调用计算
• 特性：
  • 重复计算多，耗时高，时间复杂度高

动态规划

• 关键点:
  • 将一个原问题修改为子问题
  • 试图只解决每个子问题一次，一旦其问题已经解决，会将其存储，从而避免重复计算
  • 特性:
    • 尽量避免重复计算，时间复杂度低。
• 关键概念
  • 最优子结构
  • 边界
  • 状态转移公式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

# 动态规划 存储计算中值，减少计算量
def fun(n):
    if n == 1:
        return 1
    if n == 2:
        return 2

    a = 1
    b = 2
    tmp = a + b
    for i in range(3, n):
        tmp = a + b
        a = b
        b = tmp
    return tmp
# 迭代法
def fun(n):
    if n == 1:
        return 1
    if n == 2:
        return 2
    return fun(n-1) + fun(n-2)

f(10) = f(9) + f(8) 是【最优子结构】
f(1) 与 f(2) 是【边界】
f(n) = f(n-1) + f(n-2) 【状态转移公式】

相关资源

• ★★★★★ TODO 五分钟学算法：算法与数据结构文章详细分类与整理！
• 图解 递归与动态规划

Resources

Python 算法及其实现

https://github.com/qiwsir/algorithm
https://github.com/keon/algorithms

https://github.com/TheAlgorithms/Python
https://github.com/Jack-Lee-Hiter/AlgorithmsByPython
https://github.com/apachecn/Interview

https://github.com/openai/gym