书名是《图解算法数据结构》，在力扣看到的，准备开始系统学习一下算法了。会用前端的语言和思维来学习学习～希望能获得一些见解。第一篇是关于算法复杂度的学习笔记记录。
算法复杂度
复杂度概念
书中介绍，算法复杂度旨在计算在输入数据量 N 的情况下，算法的时间使用和空间使用情况；体现算法运行使用的时间和空间随「数据大小N」而增大的速度
- 时间：假设各操作的运行时间为固定常数，统计算法运行的
计算操作的数量，以代表算法运行所需时间
- 空间：统计在最差情况下，算法运行所需使用的”最大空间”
- 数据大小N：算法处理的输入数据量；根据不同算法，具有不同定义
- 排序算法：N 代表需要排序的元素数量
- 搜索算法：N 代表搜索范围的元素总数
理解：算法复杂度是在一定的输入数据量下，计算所需要的时间操作数量大小（计算操作数量）和空间的大小来体现复杂度量。
时间复杂度
概念：时间复杂度指输入数据大小为 N 时，算法运行所需花费的时间
注意的是，这里的时间是计算操作数量，和运行绝对时间呈正相关关系，并不相等。
时间复杂度具有最差、平均、最佳三种情况，分别使用O, Θ, Ω三种符号表示
1
2
3
4
5
6
7
8
9
10
11
12
13
|
const find_num = (nums) => {
for (const num in nums) {
if (num === 7) return false
}
return false
}
|
常见的算法时间复杂度大小排序：O(1) < O(logN) < O(N) < O(NlogN) < O(N^2) < O(2^N) < O(N!)
常数O(1)：不随输入数据大小 N 的变化而变化线性O(N)：循环运行次数与 N 大小呈线性关系平方O(N^2)：两层循环相互独立，都与 N 呈线性关系，因此总体与 N 呈平方关系指数O(2^N)：指数阶常出现于递归阶乘O(N!)：阶乘阶对应数学上常见的 “全排列” 。即给定 NN 个互不重复的元素，求其所有可能的排列方案。阶乘常使用递归实现，算法原理：第一层分裂出 N 个，第二层分裂出 N−1 个，…… ，直至到第 N 层时终止并回溯对数O(logN)：对数阶与指数阶相反，指数阶为 “每轮分裂出两倍的情况” ，而对数阶是 “每轮排除一半的情况”线性对数O(NlogN)：两层循环相互独立，第一层和第二层时间复杂度分别为 O(logN) 和 O(N)
个人理解
常数O(1)：就是传入变量不影响计算，相当于一个未使用的变量。eslint下应该是遇不到的线性O(N)：与输入N线性关系，其中只有一次循环是和输入的N有关平方O(N^2)：两层互相独立的线性关系嵌套，两层嵌套循环，比如冒泡排序指数O(2^N)： 树形图，每个节点都有两个操作，节节往下，第一层祖父节点，2^0 ,第二层就是2^1 ，以此类推，最后就是 2^n-1 次方，加起来就是 2^n阶乘O(N!)：全排列，和上面反过来，第一次=层全部循环一遍，然后第二层操作剔除一个特征操作，以此类推对数O(logN)：和指数反过来，就是二分法，分治这样的算法基础，一分为二或者一分为多。线性对数O(NlogN)：两层循环相互独立，第一层和第二层时间复杂度分别为O(logN)和O(N)
空间复杂度
概念：空间复杂度指在输入数据大小为 N 时，算法运行所使用的暂存空间+输出空间的总体大小
输入空间： 存储输入数据所需的空间大小；输入数据暂存空间： 算法运行过程中，存储所有中间变量和对象等数据所需的空间大小；包括数据空间``栈帧空间``指令空间
数据空间：各项变量使用的空间，包括：声明的常量、变量、动态数组、动态对象等使用的内存空间。栈帧空间：程序调用函数是基于栈实现的，函数在调用期间，占用常量大小的栈帧空间，直至返回后释放。指令空间：编译后，程序指令所使用的内存空间。
输出空间： 算法运行返回时，存储输出数据所需的空间大小；输出数据
最差情况：空间复杂度统计算法在 “最差情况” 下使用的空间大小，以体现算法运行所需预留的空间量，使用符号O表示，包含两种情况
最差输入数据：当 N≤10 时，数组 nums 的长度恒定为 10 ，空间复杂度为 O(10) = O(1)；当 N > 10时，数组 nums 长度为 N ，空间复杂度为 O(N) ；因此，空间复杂度应为最差输入数据情况下的 O(N)最差运行点：在执行nums = Array(10).fill(0)时，算法仅使用 O(1) 大小的空间；而当执行 nums = Array(n).fill(0)时，算法使用 O(N) 的空间；因此，空间复杂度应为最差运行点的 O(N)
常见的算法空间复杂度有：O(1) < O(logN) < O(N) < O(N^2) < O(2^N)
常数O(1)：普通常量、变量、对象、元素数量与输入数据大小 N 无关的集合，皆使用常数大小的空间线性O(logN)：元素数量与 N 呈线性关系的任意类型集合（常见于一维数组、链表、哈希表等）平方O(N)：元素数量与 N 呈平方关系的任意类型集合（常见于矩阵），皆使用平方大小的空间指数O(N^2)：指数阶常见于二叉树、多叉树对数O(2^N)：对数阶常出现于分治算法的栈帧空间累计、数据类型转换等。如快速排序/数字转化字符串
时空权衡
对于算法的性能，需要从时间和空间的使用情况来综合评价。优良的算法应具备两个特性，即时间和空间复杂度皆较低。而实际上，对于某个算法问题，同时优化时间复杂度和空间复杂度是非常困难的。降低时间复杂度，往往是以提升空间复杂度为代价的，反之亦然。
由于当代计算机的内存充足，通常情况下，算法设计中一般会采取空间换时间的做法，即牺牲部分计算机存储空间，来提升算法的运行速度。
一些DEMO
时间复杂度相关的demo
1
2
3
4
5
6
7
8
9
10
11
| const algorithm = (n) => {
let count = 0;
const a = 100;
for (const i in n) {
for (const j in a) {
count += 1;
}
}
return count;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
const bubbleSort = (nums) => {
const n = nums.length;
for (const i in n - 1) {
for (const j in n - i - i) {
if (nums[j] > nums[j + 1]) {
cache = nums[j]
nums[j] = nums[j + 1]
nums[j + 1] = cache
}
}
}
return nums;
}
|
1
2
3
4
5
6
7
8
|
const algorithm = (n) => {
if (n <= 0) return 1
const a = algorithm(n - 1)
const b = algorithm(n - 1)
return a + b;
}
|
1
2
3
4
5
6
7
8
9
10
|
const algorithm = (n) => {
if (n <= 0) return 1
let count = 0
for (const i in n) {
count = algorithm(n - 1)
}
return count;
}
|
1
2
3
4
5
6
7
8
9
10
11
|
const algorithm = (n) => {
let count = 0
let i = n
while (i > 1) {
i = i / 2
count += 1
}
return count
}
|
1
2
3
4
5
6
7
8
9
10
|
const algorithm = (n) => {
let count = 0
let i = n
while (i > 1) {
i = i / 2
for (const j in n) count += 1
}
}
|
空间复杂度的相关demo
1
2
3
4
5
6
| const child = () => 0
const parent = (n) => {
for (const i in n) child()
}
|
1
2
3
4
5
6
|
const parent = (n) => {
if (n <= 1) return 1
return parent(n - 1) + 1
}
|
1
2
3
4
5
6
|
const algorithm = (n) => {
const num = 5
let nums = Array(10).fill(0)
if (n > 10) nums = Array(n).fill(0)
}
|
时空权衡的demo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
|
var twoSum = function(nums, target) {
const len = nums.length;
for (let i = 0; i < len - 1; i++) {
for (let j = i + 1; j < len; j++) {
if (nums[i] + nums[j] === target) {
return [i, j]
}
}
}
};
const twoSum = function(nums, target) {
const len = nums.length;
const map = new Map();
for (let i = 0; i < len; i++) {
map.set(nums[i], i);
}
for (let i = 0; i < len; i++) {
const needNum = target - nums[i];
if (map.has(needNum) && i !== map.get(needNum)) {
return [i, map.get(needNum)]
}
}
}
const twoSum = function(nums, target) {
const len = nums.length;
const map = new Map();
for (let i = 0; i < len; i++) {
const needNum = target - nums[i];
if (map.has(needNum) && i !== map.get(needNum)) {
return [i, map.get(needNum)];
}
map.set(nums[i], i);
}
}
|
