算法基础，了解算法的基础知识，算法的种类，知道什么是好算法。
# 算法特性
- 输入：可以有零个或多个参数
- 输出：必须有一个或多个结果
- 有穷性：算法必须会结束，没有无限循环
- 确定性：有唯一结果
- 可行性：算法每一步都能通过执行有限次数完成
# 算法设计要求
- 正确性：算法至少具有输入、输出和过程明确的加工处理，正确反映问题的需求，最后得到期望的答案
- 算法程序没有语法错误
- 算法程序对于合法输入能产生期望的答案
- 算法程序对于非法输入能产生警告和提示
- 算法程序对于故意掉难得测试输入都能产生期望的结果
- 可读性：算法便于阅读、理解和交流
- 健壮性：能够处理异常、崩溃或莫名其妙的结果
- 高时间效率和低存储量：算法要考虑处理速度和内存用量
# 算法效率度量方法
- 事后统计方法：通过执行多个输入测试，记录执行时间平均值
- 事前估算方法：通过统计方法对算法进行估算，涉及以下因素
- 算法策略，例子使用公式或者循环等
- 编译后的代码质量，基础操作的次数统计
- 问题的输入规模，例子数值大小或元素数量等
- 机器执行指令的速度，硬件性能
算法基础种类分别有：1、n、n*n。
一般使用公式或瀑布式条件判断的算法策略属于1；使用单个循环的属于n；使用嵌套循环的属于n*n。3种算法中往往常数算法1要优于n和n*n。给以下基础操作次数公式分类：
1：3、5、9等n：n、n+1、2n+3等n*n：n^2、n^2+5、2n^3+1等
一般判断算法好坏，更应该关注函数公式的主项：指数最高项。
比如算法2n^2+n+3对比算法n^3+2n+1，因为2n^2指数低于n^3，所以算法2n^2+n+3优于算法n^3+2n+1。
# 怎么分析一个算法的输入时间？
- 抽象算法：去除算法中循环的外包装、条件的判断、变量的声明、打印输出等操作
- 指令计数：统计关联的输入模式下基础操作的数量
# 求和1-100的算法例子分析
以下算法一，算法策略使用循环，编译后的代码质量为n次，问题的输入规模100，机器执行指令的速度取决于算法运行所在计算机。
let sum = 0, i = 1, n = 100;
for (; i <= n; i++) {
sum += i; // 执行 n 次
}
以下算法二，算法策略使用公式，编译后的代码质量为1次，问题的输入规模100，机器执行指令的速度取决于算法运行所在计算机。
let sum = 0, i = 1, n = 100;
sum = (i + n) * n / 2; // 执行 1 次
对比以上算法，它们的输入规模都是100，在同一计算机运行的情况下，算法一的基础操作次数受输入规模的影响，造成工作量超出算法二，所以算法二效率更高。
# 求和3x3表格内数值的例子分析
以下表格遍历例子，算法策略使用嵌套的循环，编译后的代码质量为n^2次，问题的输入规模3x3，机器执行指令的速度取决于算法运行所在计算机。
let sum = 0,
table = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 9],
];
for (let i = 0; i <= table.length; i++) {
for (let j = 0; j <= table[i].length; j++) {
sum += table[i][j]; // 执行 n^2 次
}
}
以上算法，它根据表格的大小，基础操作的数量是以指数上升的，所以3x3的表格内数值总和计算一共有基础操作3^2等于9次。
# 用大O记法表示算法时间复杂度
复杂度分为：时间复杂度或空间复杂度 一般计算“复杂度”是指“时间复杂度”，而不是空间复杂度，目前主流还是时间复杂度，不求用内存换取时间。
T(n) = O(f(n))，f(n)为算法的函数或入口，随着输入规模n的增长，T(n)增长最慢的算法为最优算法。因为以下原因：
基础操作数量 = 时间
所以当n翻倍时，基础操作数量增长越少，花费的时间越少。
上面用到的三个求和算法例子，如果用大O表示算法的时间复杂度分别为O(1)、O(n)、O(n^2)。
大O记法表示时间的增长率
O(1)：增长率不变O(n)：增长率倍数增长O(n^2)：增长率指数增长
# 推导大O阶方法
用一下方法来推导5、2n+3、n(n+1)/2和O(logn)的大O阶：
- 用常数1取代所有加法常数
- 只保留最高阶项
- 最高阶项不是1的话，去除这个项相乘的常数
5 => O(1)，
2n+3 => O(n)，
n(n+1)/2 => O(n^2)
一面这个例子的话就是O(logn)：
let i = 1, n = 100;
while (i < n) {
i *= 2; // 2^x = n，那么 x = log(2)n，x为循环次数
}
# 常见的时间复杂度
| 例子 | 时间复杂度 | 术语 |
|---|---|---|
| 5 | O(1) | 常数阶 |
| 3n+4 | O(n) | 线性阶 |
| 3n^2+4n+5 | O(n^2) | 平方阶 |
| 3log(2)n+4 | O(logn) | 对数阶 |
| 2n+3nlog(2)n+14 | O(nlogn) | nlogn阶 |
| n^3+2n^2+4n+6 | O(n^3) | 立方阶 |
| 2^n | O(2^n) | 指数阶 |
时间复杂度对比：
O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)
