算法基础，了解算法的基础知识，算法的种类，知道什么是好算法。
算法特性
- 输入：可以有零个或多个参数
- 输出：必须有一个或多个结果
- 有穷性：算法必须会结束，没有无限循环
- 确定性：有唯一结果
- 可行性：算法每一步都能通过执行有限次数完成
算法设计要求
- 正确性：算法至少具有输入、输出和过程明确的加工处理，正确反映问题的需求，最后得到期望的答案
- 算法程序没有语法错误
- 算法程序对于合法输入能产生期望的答案
- 算法程序对于非法输入能产生警告和提示
- 算法程序对于故意掉难得测试输入都能产生期望的结果
- 可读性：算法便于阅读、理解和交流
- 健壮性：能够处理异常、崩溃或莫名其妙的结果
- 高时间效率和低存储量：算法要考虑处理速度和内存用量
算法效率度量方法
- 事后统计方法：通过执行多个输入测试，记录执行时间平均值
- 事前估算方法：通过统计方法对算法进行估算，涉及以下因素
- 算法策略，例子使用公式或者循环等
- 编译后的代码质量，基础操作的次数统计
- 问题的输入规模，例子数值大小或元素数量等
- 机器执行指令的速度，硬件性能
算法基础种类分别有：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 次
}
2
3
4
以下 算法二 ，算法策略使用 公式 ，编译后的代码质量为1 次，问题的输入规模100，机器执行指令的速度取决于算法运行所在计算机。
let sum = 0, i = 1, n = 100;
sum = (i + n) * n / 2; // 执行 1 次
2
对比以上算法，它们的输入规模都是 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 次
}
}
2
3
4
5
6
7
8
9
10
11
以上算法，它根据表格的大小，基础操作的数量是以指数上升的，所以 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 为循环次数
}
2
3
4
常见的时间复杂度
| 例子 | 时间复杂度 | 术语 |
|---|---|---|
| 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)