JavaScript 算法与数据结构

本仓库包含了多种基于 JavaScript 的算法与数据结构。

每种算法和数据结构都有自己的 README,包含相关说明和链接,以便进一步阅读 (还有 YouTube 视频) 。

Read this in other languages:
English,
繁體中文,
한국어,
日本語,
Polski,
Français,
Español,
Português,
Русский,
Türk,
Italiana,
Bahasa Indonesia,
Українська,
Arabic,
Deutsch

注意:这个项目仅用于学习和研究,不是用于生产环境。

数据结构

数据结构是在计算机中组织和存储数据的一种特殊方式,使得数据可以高效地被访问和修改。更确切地说,数据结构是数据值的集合,表示数据之间的关系,也包括了作用在数据上的函数或操作。

B - 初学者, A - 进阶

算法

算法是如何解决一类问题的明确规范。算法是一组精确定义操作序列的规则。

B - 初学者, A - 进阶

算法主题

算法范式

算法范式是一种通用方法,基于一类算法的设计。这是比算法更高的抽象,就像算法是比计算机程序更高的抽象。

如何使用本仓库

安装依赖

npm install

运行 ESLint

检查代码质量

npm run lint

执行测试

npm test

按照名称执行测试

npm test -- 'LinkedList'

Playground

你可以在 ./src/playground/playground.js 文件中操作数据结构与算法,并在 ./src/playground/__test__/playground.test.js 中编写测试。

然后,只需运行以下命令来测试你的 Playground 是否无误:

npm test -- 'playground'

有用的信息

引用

▶ YouTube

大O符号

大O符号中指定的算法的增长顺序。

Big O graphs

源: Big O Cheat Sheet.

以下是一些最常用的 大O标记法 列表以及它们与不同大小输入数据的性能比较。

大O标记法计算10个元素计算100个元素计算1000个元素
O(1)111
O(log N)369
O(N)101001000
O(N log N)306009000
O(N^2)100100001000000
O(2^N)10241.26e+291.07e+301
O(N!)36288009.3e+1574.02e+2567

数据结构操作的复杂性

数据结构连接查找插入删除备注
数组1nnn
nn11
队列nn11
链表nn11
哈希表-nnn在完全哈希函数情况下,复杂度是 O(1)
二分查找树nnnn在平衡树情况下,复杂度是 O(log(n))
B 树log(n)log(n)log(n)log(n)
红黑树log(n)log(n)log(n)log(n)
AVL 树log(n)log(n)log(n)log(n)
布隆过滤器-11-存在一定概率的判断错误(误判成存在)

数组排序算法的复杂性

名称最优平均最坏内存稳定备注
冒泡排序nn^2n^21Yes
插入排序nn^2n^21Yes
选择排序n^2n^2n^21No
堆排序n log(n)n log(n)n log(n)1No
归并排序n log(n)n log(n)n log(n)nYes
快速排序n log(n)n log(n)n^2log(n)No在 in-place 版本下,内存复杂度通常是 O(log(n))
希尔排序n log(n)取决于差距序列n (log(n))^21No
计数排序n + rn + rn + rn + rYesr - 数组里最大的数
基数排序n * kn * kn * kn + kYesk - 最长 key 的升序