【图解算法】学习图解算法数据结构笔记(一)之算法复杂度

【图解算法】学习图解算法数据结构笔记(一)之算法复杂度

书名是《图解算法数据结构》,在力扣看到的,准备开始系统学习一下算法了。会用前端的语言和思维来学习学习~希望能获得一些见解。第一篇是关于算法复杂度的学习笔记记录。

算法复杂度

复杂度概念

书中介绍,算法复杂度旨在计算在输入数据量 N 的情况下,算法的时间使用空间使用情况;体现算法运行使用的时间和空间随「数据大小N」而增大的速度

  • 时间:假设各操作的运行时间为固定常数,统计算法运行的计算操作的数量,以代表算法运行所需时间
  • 空间:统计在最差情况下,算法运行所需使用的”最大空间”
  • 数据大小N:算法处理的输入数据量;根据不同算法,具有不同定义
    • 排序算法:N 代表需要排序的元素数量
    • 搜索算法:N 代表搜索范围的元素总数

理解:算法复杂度是在一定的输入数据量下,计算所需要的时间操作数量大小(计算操作数量)和空间的大小来体现复杂度量。

时间复杂度

概念:时间复杂度指输入数据大小为 N 时,算法运行所需花费的时间

注意的是,这里的时间是计算操作数量,和运行绝对时间呈正相关关系,并不相等。

时间复杂度具有最差平均最佳三种情况,分别使用O, Θ, Ω三种符号表示

1
2
3
4
5
6
7
8
9
10
11
12
13
// demo
const find_num = (nums) => {
for (const num in nums) {
if (num === 7) return false
}
return false
}

// 最佳情况Ω(1): nums = [7, a, b, c, ...] ,即当数组首个数字为 77 时,无论 nums 有多少元素,线性查找的循环次数都为 11 次;

// 最差情况O(N): nums = [a, b, c, ...] 且 nums 中所有数字都不为 77 ,此时线性查找会遍历整个数组,循环 N 次

// 平均情况Θ: 需要考虑输入数据的分布情况,计算所有数据情况下的平均时间复杂度;例如本题目,需要考虑数组长度、数组元素的取值范围等

常见的算法时间复杂度大小排序: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;
}
// 时间复杂度是o(N),一直一层循环是与输入有关
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;
}
// 时间复杂度是O(N^2),第一层复杂的o(N), 第二层平均循环次数为N/2,复杂度也为o(N)
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;
}
// 时间复杂度是O(2^N)
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;
}
// 时间复杂度是O(N!)
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
}
// 时间复杂度是O(logN)
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
}
}
// 时间复杂度是O(NlogN)

空间复杂度的相关demo

1
2
3
4
5
6
const child = () => 0

const parent = (n) => {
for (const i in n) child()
}
// 空间复杂度o(1),因为栈帧空间被释放掉了,每次掉用child()后
1
2
3
4
5
6
// 递归调用
const parent = (n) => {
if (n <= 1) return 1
return parent(n - 1) + 1
}
// 空间复杂度o(N),因为递归调用,会存在N个未返回的函数,累计使用O(N)大小的栈帧空间
1
2
3
4
5
6
// 最差运行点
const algorithm = (n) => {
const num = 5 // O(1)
let nums = Array(10).fill(0) // O(1)
if (n > 10) nums = Array(n).fill(0) // O(N)
}

时空权衡的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]
}
}
}
};
// 时间复杂度 O(N^2),空间复杂度 O(1);属于时间换空间,虽然仅使用常数大小的额外空间,但运行速度过慢。


// 方法二:辅助哈希表
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)]
}
}
}
// 时间复杂度 O(N),空间复杂度 O(N);属于「空间换时间」,借助辅助哈希表 dic,通过保存数组元素值与索引的映射来提升算法运行效率,是本题的最佳解法。

// 方法三:哈希优化
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);
}
}

【图解算法】学习图解算法数据结构笔记(一)之算法复杂度

https://blog.vadxq.com/article/illustration-of-algorithm-01/

作者

vadxq

发布于

2021-09-22

更新于

2021-09-22

许可协议

评论