00. 如何计算算法的复杂度

01. 课程总览

02. 时间复杂度

2.1 大O表示

注意：只看最高复杂度的运算，并不考虑前面系数

2.2 例子

2.3 时间复杂度曲线

不同的时间复杂度会根据n的变大差距越来越明显，时间复杂度能够降低一点，针对大数据的情况，会节省计算机很多的运算时间。

2.4 递归

Fibonacci array: 1, 1, 2, 3, 5, 8, 13, 21, 34, …
*

def fib(n):
    if n == 0 or n == 1:
      return n
    return fib(n-1) + fib(n-2)

这段代码的时间复杂度是多少呢？以n=6为例，画出其递归图：

虽然代码看上去简单，但是在计算过过程中，出现了大量的冗余计算，导致其时间复杂度高达 。

2.5 主定理以及常见算法复杂度

• 二分查找：一般在有序的数列中找到目标树，一分为二，直查询一边。
• 二叉树遍历：每个节点遍历一次，且仅遍历一次
• 排序矩阵的查找：一维矩阵；二维矩阵
• 快排、归并排序：

2.6 思考题

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

答： O(n)。n就是为二叉树的节点总数。因为二叉树遍历的过程中，每个节点会访问一次且仅访问一次。所以时间复杂度会线性于二叉树的节点总数

1. 图的遍历 ： 时间复杂度是多少

答：O(n)。每个节点会访问一次且仅访问一次

1. 搜索算法：DFS和BFS时间复杂度是多少

答： O(n)。 n：代表搜索空间中的节点总数

1. 二分查找：时间复杂度是多少

答：o(logn)

03. 算法训练方式

下手之前，将所有的解法都想一边，判断时间复杂度，选择最后时间复杂度最小的解法。

04. 参考链接

• 如何理解算法时间复杂度的表示法
• Master theorem)
• 主定理