# 漫画算法-算法概述

# 时间复杂度

1、10cm的面包，3分钟吃掉1cm，需要多少时间？

t = 3 * 10;

如果长度是 n，T(n) = 3n;

2、面包长度16cm，每5分钟吃掉面包长度的一半，把面包吃得只剩1cm，需要多少时间？

用数学表达就是用 16 不断除以 2，除多少次结果为1.

用对数表示 t = log₂¹⁶

如果长度是 n，T(n) = log₂ⁿ;

3、有10cm的面包和1个鸡腿，吃掉一个鸡腿需要2分钟，吃掉整个鸡腿需要多久？

t = 2;

如果有 n 个鸡腿，T(n) = 2n;

4、长度为10cm的面包，吃掉第1个1cm需要1分钟，第二个1cm需要2分钟，以此类推，吃掉整个面包需要多久？

t = 1 + 2 + 3 + 4 + 5 + ... + 10 = (1 + 10) * 10 / 2；

如果长度为 n，T(n) = (1 + n ) * n / 2 = 0.5n + 0.5n²;

渐进时间复杂度

asymtotic time complexity

定义：当存在函数 f(n) ，使得当n趋近无穷大时，T(n) / f(n) 的极限值为不等于零的常数，则称 f(n) 是 T(n) 的同数量级函数，记作 T(n) = O(f(n)，O 为算法的渐进时间复杂度，简称时间复杂度。

# 空间复杂度

# 常量空间

算法的存储空间大小固定，和输入规模没有直接关系时，记作 O(1)。

# 线性空间

算法空间是一个线性的集合（如数组），并且集合大小和输入规模 n 成正比，记作 O(n)。

# 二维空间

算法分配的空间是一个二维数组集合，并且集合的长度和宽度都和输入规模 n 成正比，记作 O(n²)

# 递归空间

计算机在执行程序时，会分配一块内存用来存储方法调用栈。

方法调用时会入栈，调用完后会出栈，直到全部方法调用完成出栈后，结束。

执行递归操作所需的内存空间和深度成正比，所以记作 O(n)。

# 时间与空间的取舍

在绝大多数时候，时间复杂度更为重要一些，宁可多分配一些内存空间，也要提升程序的执行速度。