TOC
算法
什么是算法
算法（algorithm），在数学（算学）和计算机科学之中，为任何良定义的具体计算步骤的一个序列，常用于计算、数据处理和自动推理。精确而言，算法是一个表示为有限长列表的有效方法。算法应包含清晰定义的指令用于计算函数。- wiki
算法的性能衡量
为了统一算法的性能衡量标准，我们需要放弃一切变量，放弃具体的数值，而是用一些比较抽象的手段去描述一个算法。简单来说，放弃具体运行时间，重点研究算法的增长！
当然，算法其实是数学与工程相结合的东西，这意味着一个高增长的算法并不是一无是处的，因为你的输入n的规模如果很小，那么高增长可能也并不是很危险。所以，你需要两者结合共同思考。
** 基本的符号 **
θ - theta 放弃一切常数以及低阶项
这里记录一下递归树解法 当一颗递归树以每层两个子节点往下延伸到1为止，那么其高度为logn其总子节点之和为n
要用到的基本数学公式
BIG O
f(n) = O(g(n)) 例子 2n^2 = O(n^3)
含义
- 两边并不相等
- 初略的说表示小于等于
- f(n) 属于 g(n)构成的函数集
- 可以说 2n^2属于 n^3构成的一个函数集
用法
- 宏 f(n) = n^3 + O(n^2) 含义为 f(n)主要是 n^3 但是有一些至多为n^2的误差项 ，可以被认为是上下界描述
- 当在左边的时候，他代表的是is n^2 + O(n) = O(n^2)
Omega
Omega符号一般用来描述最优情况
f(n) = Ω(g(n)) 例子 √￣n = Ω(lgn) 当n充分大的时候，前面的永远是后面的常数倍
含义
- 两边并不相等
- 粗略的说表示大于等于
BIG Theta
Θ 其实就是类似世界的等于符号，上面分别是小于等于，大于等于，这个就是等于符号
small Omega and O
ω 大于
o 小于
解递归式
解递归式的方法有很多种，到目前还没有通用的方法
只学会了一种递归树方法，利用其递归式来分解，并把每一层级加起来
递归树方法
function pusu(x, n) {
function _pusu(n) {
if (n === 1) { return x }
let half
let res
if (n % 2 === 0) {
half = _pusu(n / 2)
res = half * half
} else {
half = _pusu((n - 1) / 2)
res = half * half * x
}
return res
}
return _pusu(n)
}