用时间复杂度来描述一个算法的性能，其关键是运行在这个算法上的数据规模

到底什么是大O

二分查找法 O(lgn)

寻找数组中的最大/最小 O(n)

算法A：O(n) 所需执行指令数：10000*n

算法B：O(n^2) 所需执行指令数：10*n^2 双重循环2次扫描n这个数据，但是只需要执行10行指令就能完成这个算法

数据规模大的时候，算法之间所表现出来的差距就会非常惊人

要想在1秒之内解决问题：

O(n^2) 的算法可以处理大约10^4 级别的数据

O(n) 的算法可以处理大约10^8 级别的数据

O(nlogn) 的算法可以处理大约10^7 级别的数据

空间复杂度：

多开一个辅助的数组： O(n)

多开一个辅助的二维数组： O(n^2)

多开常数空间： O(1)

O(n) 一般有一个for循环

O(n^2) 一般是两个嵌套的for循环

O(logn) 一般是二分查找

写一个测试用例

具体问题具体分析

只进行一次递归调用，此时递归的深度就是调用的次数

递归深度为depth，在每个递归函数中，时间复杂度为T，则总体时间复杂度为O(T * depth)

递归深度：n 时间复杂度：O(n)

递归深度：O(logn) 时间复杂度： O(logn)

递归中进行多次递归调用： 关心的是调用的次数

当f(3)的时候会两次调用f(2), 当f(2)的时候会两次调用f(1) 当f(1)的时候会两次调用f(0)。要知道f(3)进行了几次递归调用，其实就是数以下这课数的节点

如图，

如果从node 3 开始往下数节点的话，

第一层为1 ，

第二层为2

第三层为4

第四层为8

那么，推广来说的话，如果有n层，则

这种指数级的时间复杂度是非常高的

第2章面试中的复杂度分析

results matching ""