算法：时间复杂度和空间复杂度

时间复杂度

1. 时间复杂度，表示形式为 Big O notation。  如何理解算法时间复杂度
   

    时间复杂度也可以理解为指令执行多少次。好的时间复杂度程序，会让程序跑起来更快更节约资源。从

所有可能的解决方法中找出 时间最快、内存最少 的最优解决方法。

2. 常见的几种时间复杂度

tips：O 表示它的复杂度是 n 的怎样的一个函数

•     O(1)：Constant Complexity 常数复杂度

•     O(log n)：Logarithmic Complexity 对数复杂度

•     O(n)：Linear Complexity 线性时间复杂度

•     O(n^2)：N square Complexity 平方

•     O(n^3)：N cubic Complexity 立方

•     O(2^n)：Exponential Complexity 指数

•     O(n!)：Factorial 阶乘

常数复杂度

线性、平方 时间复杂度

对数、指数 复杂度

时间复杂度曲线

3. 递归时间复杂度分析

递归，关键是了解它的递归总共执行了语句多少次。循环，比较好理解，n 次循环就执行了 n 次语句。递

归是层层嵌套的，通常可以把它的执行顺序画出一个树形结构。

时间复杂度：O(2^n)

两个现象：

• 每多展开一层，运行的节点数就是上面一层的 2 倍。第一层 1 个节点，第二层 2 个节点，第三层 4 个节点，第四层 8 个节点........以此类推，它每一层的节点数即它的执行次数 是按指数级递增的。由此可见，当到最后一层的话，会变成 2 的 n 次方，大概这么一个数量级的节点。那么可以肯定，最后总的执行次数，就是变成指数级了。

• 有重复的节点出现在执行状态数中。F1、F2、F3 都被重复计算很多次，这些大量冗余的计算，导致求第 6 个数的 Fibonacci 数变成了 2 的 6 次方这么一个繁复的时间复杂度。面试中不要这么写算法，可以加缓存，把中间节点的结果缓存下来，或者直接用循环来写求和。

主定理

主定理：解决所有递归函数怎么计算时间复杂度

常用主定理

• 二分查找：有序数列，一分为二，只在一边进行查找，O(log n)。

• 二叉树遍历：每次一分为二，但每一边是相等的时间复杂度这么下去。简化思维：二叉树遍历每个节点都会访问一次，且仅访问一次，O(n)。

• 有序的二维矩阵：如果是一维的数组进行二分查找为 O(log n)，有序的二维矩阵二分查找时，被降了一维就不是 n 平方的算法，而是 O(n)。

• 归并排序

空间复杂度

两条原则：

• 如果代码里开了数组，那么数组的长度基本上就是你的空间复杂度。譬如长度为 n 的一维数据，空间复杂度为 O(n)。长度为 n 平方的二维数组，空间复杂度为 O(n^2)。

• 如果有递归的话，递归的深度就是就是你的空间复杂度的最大值。如果又有数组又有递归，那两者之间的最大值就是你的空间复杂度。

算法分析题解答：爬楼梯

LeetCode 刷题

最大误区：刷题只刷一遍

核心思想：1.升维（如跳表实现原理，链表为一维，树为二维）；2.空间换时间

• 5-10 分钟，思路写下来，能想到的所有的，先不管时间空间复杂度。

没有思路的话，立即看他人解法，不要一直纠结。

• 执行代码，添加测试用例，提交。

• 再去学习官方题解和和他人的解题方法，不合适的地方自己可以对其进行改进写下来执行。

• 地址复制出来，-cn 不要，进入国际站网址，点击 Discuss 区域，按照 Most Votes 默认排序，里面有写的非常好的代码可以借鉴。

• 不熟练的话做 5 遍，五遍刷题法，五毒神掌。