时间复杂度、递归、尾调用— (读文笔记)
输出
读参考文章列表
问自己几个问题
- 算法复杂度中的O(logN)底数是多少， log2N 和 log10N 有区别么？
- 复习时间复杂度、空间复杂度、时间复杂度从小到大
- 时间复杂度级数
- 循环与级数的关系
- 分治、递归，递归的时间复杂度
- 从一个数组中找出最大的两个数
- 什么是动态规划，时间复杂度多少
- 尾调用和普通调用有啥不一样
问题解答
1，常底数是无所谓的，logaN/logbN = logab, 是一个常数
2，时间复杂度：
代码段执行次数累加
空间复杂度：
除了输入本身所占的空间之外，用于计算的所必须的空间量
时间复杂度从小到大
O(1)<O(logn)<O(n)<O(nlogn)<O(n²)<O(n³)<O(2ⁿ)<O(n!)
所以，O(n) 能否优化 O(logn)?优化关键
3，Ep12 时间复杂度级数
算数级数，与末项平房同阶，
1+2+3+...n = O(n^2)
幂方级数，比幂次高出一阶：
1+2^2+3^2+4^2 +... n^2 = O(n^3);
1+2^3+3^3+4^3 +... n^3= O(n^4);
1+2^4+3^4+4^4+... n^4 = O(n^5);
几何级数（a>1）:与末项同阶
a^0+a^1+a^2+... a^n = (a^(n+1) - 1)/(a-1) = O(a^n)
1+2+4+8 +... 2^n = 2^(n+1) -1 = O(2^n)
4，循环与级数的关系
for(let i = 0; i < n; i++)
for(let j = 0; i < n; j++) 坐标轴形成正方形，O(n^2)
for(let i = 0; i < n; i++)
for(let j = 0; i < j; j++) 坐标轴形成三角形，O(n^2)分治：将原问题分解为若干个规模较小但类似于原问题的子问题（Divide），「递归」的求解这些子问题（Conquer），然后再合并这些子问题的解来建立原问题的解。
递归算法是一种直接或者间接调用自身函数或者方法的算法。通俗来说，递归算法的实质是把问题分解成规模缩小的同类问题的子问题，然后递归调用方法来表示问题的解。它有如下特点：
1. 一个问题的解可以分解为几个子问题的解 2. 这个问题与分解之后的子问题，除了数据规模不同，求解思路完全一样 3. 存在递归终止条件，即必须有一个明确的递归结束条件，称之为递归出口
递归算法的世界复杂度，得分好几种
第一种：
递归中进行一次递归调用的复杂度分析，如：二分查找法
不管怎么样，最多调用了一次递归调用而已，这时候时间复杂度看什么时候跳出递归
第二种：
递归中进行多次递归调用的复杂度分析
比如说斐波拉契数列，多次调用自身
所以时间复杂度等于递归树中节点数总和，就是代码计算的调用次数。
T(n) = 各层递归实例所需时间之和
= O(1) * (2^0 + 2 ^1 + ...2^n)
= O(1) * (2^(n+1) - 1)
= O(2^n)
空间复杂度：
一个程序执行时除了需要存储空间和存储本身所使用的指令、常数、变量和输入数据外，还需要一些对数据进行操作的工作单元和存储一些为现实计算所需信息的辅助空间。
6，从一个数组中找出最大的两个数
算法一
先遍历一遍，找出最大值的位置，x1， 时间复杂度为 n-1
再遍历一遍，从剩下的n-2个数中，找最大值，时间复杂度为 n-2
总共 O(2n-3) = O(n)
算法二
x1是小值，x2是大数
如果值比x2大，替换x2
如果 x1<num<x2, 替换x1
时间复杂度O(n)
算法三
左边找最大L1，右边找最大 R1
L1<R1, 要么找右边边第二大
else, 要么找左边第二大
7，看动画轻松理解递归与动态规划
动态规划能解决的问题分治策略肯定能解决，只是运行时间长了。因此，分治策略一般用来解决子问题相互对立的问题，称为标准分治，而动态规划用来解决子问题重叠的问题。
将「动态规划」的概念关键点抽离出来描述就是这样的：
1.动态规划法试图只解决每个子问题一次
2.一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。
8.JavaScript调用栈、尾递归和手动优化
尾调用：
就是一个函数执行的最后一步是将另外一个函数调用并返回。
一般来说，如果方法a调用方法b, 那么b放到栈顶，栈指针指向栈顶, 当前帧是b, 调用帧是a,
当函数B执行完成后，还需要将执行权返回A，那么函数A内部的变量，调用函数B的位置等信息都必须保存在调用帧A中。不然，当函数B执行完继续执行函数A时，就会乱套。
那么现在，我们将函数B放到了函数A的最后一步调用（即尾调用），那还有必要保留函数A的栈帧么？当然不用，因为之后并不会再用到其调用位置、内部变量。因此直接用函数B的栈帧取代A的栈帧即可。当然，如果内层函数使用了外层函数的变量，那么就仍然需要保留函数A的栈帧，典型例子即是闭包。
总得来说，如果所有函数的调用都是尾调用，那么调用栈的长度就会小很多，这样需要占用的内存也会大大减少。这就是尾调用优化的含义。
// 尾调用错误示范1.0
function f(x){
let y = g(x);
return y;
}
// 尾调用错误示范2.0
function f(x){
return g(x) + 1;
}
// 尾调用错误示范3.0
function f(x) {
g(x); // 这一步相当于g(x) return undefined
}
1.0最后一步为赋值操作，2.0最后一步为加法运算操作，3.0隐式的有一句return undefined