时间复杂度和空间复杂度，对于程序为什么那么的重要？

写程序务必要考虑时间复杂度和空间复杂度，通过分析程序，调试代码尽可能的降低时间复杂度，使程序运行起来更快更节约资源。尽而也可以判定一个程序员的优秀程度。

时间复杂度常用的七种形式：

1. O(1)  常数时间复杂度（constant complexity）：这里面的1并非只运行一次，凡是符合常数的运行规则，都叫O(1) 时间复杂度为常数的意思。

2. O(log n) 对数时间复杂度（底数为2或者3）

3. O(n) 线性时间复杂度 (时间复杂度，都忽略系数的，2n和n一样)

4. O(n²) 平方时间复杂度

5. O(n³) 立方时间复杂度

6. O(2^n) 指数时间复杂度

7. O(n!) 时间复杂度为阶乘

读程序判断时间复杂度：

O(1)举例：

常数时间复杂度1

执行语句只有一次，所以该例子为"常数时间复杂度" ，O（1）

常数时间复杂度

虽然执行语句有三句print， 但是依旧是常数时间复杂度。O（1）

正如在分类中提及的那样，常数时间复杂度不是只运行一次，而是代表执行语句是常数，无论是2还是3

O(n)举例：

O(n) 举例

执行体运行的次数跟随着n的变化而改变。本文中，n为5，所以运行了5次print；如果n=100，将运行100次。所以时间复杂度是O（n）（时间复杂度随着n的变化，呈线性关系）

o(n) 举例

执行体总共运行了10次。第一次for循环运行了5次，第二次并列的for循环运行了5次。随着n的变化，运行的次数是2n。时间复杂度是O(n) 忽略系数。

O(n²)举例：

O(n²) 举例

嵌套for循环，双层for循环时间复杂度是O（n²）。例子中n=5， 执行语句运行了25次。总共有n个循环，每一次循环中，还有一次n的遍历，所以n*n。

若是三层嵌套循环呢？时间复杂度是O（n³）

O（log n）举例：

O（log n） 举例

函数体执行次数永远是log n，底数为2，底数为3亦可。本例中，n = 8， 执行3次。log 8 = 3 （2³ = 8）所以，时间复杂度，log n。

O（k^n）举例：（k为常数，比如2，3等）

O（k^n）举例

树形结构理解递归：

递归的节点都是指数级别

当函数体是以递归形式出现时， 整个程序的时间复杂度是指数级别的增长。

正如上图用树形结构来演示递归的实现，每个节点都是复制上一个节点的模式，每多展开一层，节点数都是上一层的两倍（因为层层嵌套）。直至满足递归的退出条件，深度是2^n。斐波那契数列的退出条件是当f(0),f(1)时，返回1。

所以，当用递归方式实现斐波那契数列时，虽然简单，但是时间复杂度的成本非常高。并不是最佳方式。因为节点存在大量的重复现象，在重复进行运算。（大量冗余计算，耗费了很多内存资源）

时间复杂度曲线比较：

时间复杂度曲线比较

当n值比较小的时候，时间复杂度差不多；当n非常大的时候，发现指数级别的时间复杂度呈指数增长。所以写程序时务必考虑时间复杂度。

例如：计算等比数列从1到n累计和。

1. 暴力破解法：从1循环到n ，用sum变量

sum = 0   for i in range(n): sum+=i   print(sum)

2. 用高斯算法: sum =(1+n)*n/2

会看到程序写法不同，时间复杂度也不同。解法1 是o(n);  解法2 是常数时间复杂度 o（1）,因为无论n等于多少，只需要公式计算一次。

所以最优的解决方案，永远都是占用内存最少，时间最快。让程序跑起来更快，更节约资源。别忘了测试下程序。

常用的递归四种情形：

1. 二分查找 （binary search）

时间复杂度 log n。

推导：上维基百科搜索主定理，大概推导的公式就是 T（n）= T(n/2) + O(1)

二分查找用于在有序的数列中，找到目标数，right？所以每次都是一分为二，只查一边，依次类推下去。最后时间复杂度log n （底数为2）

2. 二叉树遍历 （binary tree traversal）

时间复杂度 O(n)

推导：还是主定理，主要公式： T（n）= 2*T(n/2) + O(1)

二叉树遍历虽然一分为二，但是遍历每一边都是相等的时间复杂度。运行时间为O（n）。最简化的思考方式是二叉树遍历，每个节点都会访问到，有且仅有访问一次。

3. 排好序的二维矩阵进行二分查找 （optimal sorted matrix search）

时间复杂度 O(n)

推导：还是主定理，主要公式： T（n）= 2*T(n/2) + O(log n)

有序矩阵进行二分查找，这块我没太理解，只能记住一件事情：一维数组进行二分查找就是log n；二维矩阵进行二分查找（有序矩阵），就是 O（n）。不是n² 。降了一维。（这个怎么算出来n，我似懂非懂confused）

4. 归并排序 （merge sort）

时间复杂度 O(nlog n)

推导：还是主定理，主要公式： T（n）= 2*T(n/2) + O(n)

思考题：

1. 二叉树遍历的前序，中序，后序的时间复杂度是多少？

O（n）， n为二叉树节点总数。无论是前序，中序，后序的遍历，对于二叉树来说，都是有且仅有访问每个节点一次。所以，时间复杂度是线性于二叉树的节点数目。同理图的遍历。

2. 搜索算法：DFS, BFS 时间复杂度

深度优先搜索和广度优先搜索时间复杂度都是O（n），n为搜索空间的节点数。因为访问的节点都是一次。（不知道DFS,BFS,请百度。广度优先搜索是用来求最短路径的，深度优先搜索算法用来遍历图的。篇幅优先，后期单独介绍实现算法）

小结：

熟悉常用的算法时间复杂度，二分查找，归并排序，二叉树遍历，广度优先和深度优先搜索算法。