算法

算法(Algorithm)：一个计算过程，解决问题的方法。

尼古拉斯-沃斯(Niklaus Writh)：程序=数据结构+算法。

时间复杂度

时间复杂度：用来评估算法运行效率的式子。

一般来说，在同等条件下，时间复杂度高的算法比复杂度第的算法慢。

常见的时间复杂度，按效率排序： $$ O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)<O(n^2logn)<O(n^3) $$ 复杂问题的时间复杂度： $$ O(n!),O(2^n),O(n^n)... $$ 简单快速的判断算法的复杂度(适用于绝大多数简单的情况)：

确定问题规模n，比如循环列表，要判断列表的长度。
循环减半过程：logn
k层关于n的循环：n的k次方，n^k^

对于复杂情况，要根据算法的执行过程和其他条件具体展开分析。

空间复杂度

空间复杂度：用来评估算法内存占用大小的式子

空间复杂度的表示方式与时间复杂度完全一样：

算法中只使用了几个变量，那它的空间复杂度：O(1)
算法使用了长度为n的一维列表，那它的空间复杂度：O(n)
算法使用了m行n列的二维列表，那它的空间复杂度：O(mn)

大多数算法都遵循：用"空间换时间"。

递归

递归的两个特点：

调用自身
结束条件

来看几个递归的例子：

python

def func1(x):
    print(x)
    func1(x - 1)


def func2(x):
    if x > 0:
        print(x)
        func2(x + 1)


def func3(x):
    if x > 0:
        print(x)
        func3(x - 1)


# 合法递归
def func4(x):
    if x > 0:
        func4(x - 1)
        print(x)


# func1(5)  # 死递归
# func2(5)  # 死递归
# func3(5)  # 合法递归 5 4 3 2 1
func4(5)  # 合法递归 1 2 3 4 5

递归实例：汉诺塔问题

大梵天创造世界的时候，做了三根金刚石柱子，在一根柱子上从上往下按照大小顺序摞着64片黄金圆盘。

大梵天命令婆罗门把圆盘从下面开始按照大小顺序重新摆放在另一根柱子上。

在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

64个圆盘移动完毕之日，就是世界毁灭之时！！！

当然，上面说的是假的，是一位法国的数学家编出来的.....为了吸引大家学习汉诺塔。

汉诺塔圆盘移动次数的递推式： $$ h(x)=2h(x-1)+1 $$ 当有64个圆盘要移动时，那么一共要移动： $$ h(64)=18446744073709551615 $$ 假设婆罗门每秒移动一个圆盘，则共需要5800亿年。

怎么用递归的思想去解决汉诺塔问题呢？

首先，去这个地址：http://www.hannuota.cn/把游戏玩几遍再往下看。

个人理解

规则，只有三根柱子塔1、塔2、塔3。圆盘数量表示为n，且目标都是从塔1移动到塔3。

当n=0时，表示只有三个塔，没有圆盘，没啥可移动的。

当n=1时，将圆盘从塔1直接移动到塔3就完事了。

当n=2时，一个中圆盘和一个大圆盘：

把中圆盘从塔1移动到塔2
将大圆盘从塔1移动到塔3
把中圆盘从塔2移动到塔3

当n=3时，小、中、大三个圆盘，如果一次只能移动一个圆盘的话：

将小圆盘从塔1移动到塔3
将中圆盘从塔1移动到塔2，此时塔1只剩下一个大圆盘
将小圆盘从塔3移动到塔2，此时塔3空出来了
- 如果一次可以同时将n-1个圆盘，也就是小、中两个圆盘移动的话
- 目的就是从塔1经过塔3(中间步骤)最终将这n-1个圆盘移动到塔2
- 那么上面1、2、3可以合为一步：把n-1个圆盘从塔1经过塔3移动到塔2，省略掉中间环节
将大圆盘从塔1移动到塔3，此时塔1空出来了
- 只有这一步一次只移动一个圆盘
将小圆盘从塔2移动到塔1，此时三个塔各有一个圆盘
将中圆盘从塔2移动到塔3
将小圆盘从塔1移动到塔3，完事了
- 5、6、7这三步，也可以省略掉中间环节
- 也可以合为一步：把n-1个圆盘从塔2经过塔1移动到塔3

当有n个圆盘时，我们把n-1个圆盘看成一个整体(如果有三个圆盘，n-1表示小、中圆盘)，把剩下的一个大圆盘看成一个整体。

把n-1个圆盘从塔1经过塔3移动到塔2
- 包含中间环节
把第n个圆盘从塔1移动到塔3
- 只有这一步一次只移动一个圆盘
把n-1个圆盘从塔2经过塔1移动到塔3
- 包含中间环节

最终，无论有多少个圆盘，都可以分为上面这三(大)步。

python

def hanoi(n, tower_1, tower_2, tower_3):
    """
    :param n: 有多少个盘子
    :param tower_1: 塔1
    :param tower_2: 塔2
    :param tower_3: 塔3
    :return:
    """
    if n > 0:  # 当 n = 0 的时候，没有盘子，无需移动，也是递归结束的条件
        # 第一步：把 n-1 个圆盘从塔1经过塔3移动到塔2
        hanoi(n - 1, tower_1, tower_3, tower_2)
        # 第二步：把第n个圆盘从塔1移动到塔3
        print('moving from {} to {}'.format(tower_1, tower_3))
        # 第三步：把 n-1 个圆盘从塔2经过塔1移动到塔3
        hanoi(n - 1, tower_2, tower_1, tower_3)


hanoi(3, '塔1', '塔2', '塔3')
"""
# 对照上面我们手推的7步，你发现移动过程一致，也都是7步
moving from 塔1 to 塔3
moving from 塔1 to 塔2
moving from 塔3 to 塔2
moving from 塔1 to 塔3
moving from 塔2 to 塔1
moving from 塔2 to 塔3
moving from 塔1 to 塔3
"""

我找个动图，大家参考下：

图片来自知乎：如何理解汉诺塔的递归？ - 酱紫君的回答 - 知乎

24385418/answer/282940567)

算法 ​

时间复杂度 ​

空间复杂度 ​

递归 ​

算法

时间复杂度

空间复杂度

递归