算法的复杂性

03. 08. 2021

Jan Barášek

Obsah článku

每种算法都有自己的复杂性，可以用数学符号表示。这个概述显示了根据输入数据的大小（即它们所处理的元素的数量）以及哪种类型的算法适合哪种类型的任务的典型复杂性。

一般来说，每种类型的问题都有一个最佳的专门算法。没有哪种算法是普遍最好的，你总是需要知道你的背景。

大O记号

大O符号*是用来根据算法的运行时间或内存需求如何随着输入规模的增加而增加来对算法进行分类。

下图显示了用大O符号指定的算法的最常见增长顺序。

下面是一些最常用的大O符号的列表，以及它们在不同输入数据大小方面的性能比较。

大O记法	10个元素的复杂度	100个元素的复杂度	1000个元素的复杂度
O(1)	1	1	1
O(log N)	3	6	9
o(n)	10	100	1000
O(N log N)	30	600	9000
o(n^2)	100	10000	1000000
O(2^N)	1024	1.26e+29	1.07e+301 !
O(N!)	3628800	9.3e+157	4.02e+2567

数据结构操作的复杂性

数据结构	访问	搜索	插入	删除	注释
数组	1	n

| 链接的列表 | n | n | 1 | n | 哈希表 | - | n | n | n | 在完美哈希函数的情况下，复杂度将是O(1) | 。 | 二进制搜索树 | n | n | n 在平衡树的情况下，复杂性将是O(log(n))。 | | B-Tree | log(n) | log(n) | log(n) | log(n) | | log(n) |红黑树 |对数(n) |对数(n) |对数(n) |对数(n) |AVL树 |对数(n) |对数(n) |对数(n) |对数(n) | Bloom Filter | - | 1 | 1 | - | 搜索 "假阳性 "时 |

分拣算法的复杂性

算法名称	最好的	平均的	最差的	记忆的	稳定的?	评论的
气泡排序	n	n²	n²	1	是
插入式排序	n	n²	n²	1
选择排序	n²	n²	n²	1	!
堆排序	n log(n)	n log(n)	n log(n)	1		No
合并排序	n log(n)	n log(n)	n log(n)	n	是的
快速排序	n log(n)	n log(n)	n²	log(n)	No	Quicksort通常以O(log(n))的堆栈复杂度进行。
壳排序	n log(n)	取决于序列	n (log(n))²	1		不
计数排序	n + r	n + r	n + r	n + r	Yes	r - 阵列中最大的数字
Radix sort	n * k	n * k	n + k	Yes	k - 最长钥匙的长度

Jan Barášek Více o autorovi

Autor článku pracuje jako seniorní vývojář a software architekt v Praze. Navrhuje a spravuje velké webové aplikace, které znáte a používáte. Od roku 2009 nabral bohaté zkušenosti, které tímto webem předává dál.

Rád vám pomůžu: