常用数据结构操作与算法复杂度总结

Dear 丶 2023-06-15 13:30 26阅读 0赞

### 文章目录 ###

*  时间复杂度
 *  常用数据结构操作与算法的复杂度
 *  输入规模较小时的情况
 *  引用

博客： [blog.shinelee.me][] | [博客园][Link 1] | [CSDN][]

# 时间复杂度 #

如何评估一个算法的计算时间？

一个算法的**实际运行时间很难评估**，当时的输入、CPU主频、内存、数据传输速度、是否有其他程序在抢占资源等等，这些因素都会影响算法的实际运行时间。为了公平地对比不同算法的效率，需要脱离开这些物理条件，抽象出一个数学描述。在所有这些因素中，**问题的规模往往是决定算法时间的最主要因素**。因此，**定义算法的时间复杂度 T ( n ) T(n) T(n)，用来描述算法的执行时间随着输入规模的增长将如何变化，增长速度是怎样的**。

在输入规模较小时，运行时间本来就少，不同算法的差异不大。所以，时间复杂度通常关注的是输入规模 n n n较大时运行时间的变化趋势，称之为**渐进复杂度**，采用大O记号，表示**渐进上界**，对于任意的 n > > 2 n >> 2 n>>2，若有常数 c c c和函数 f ( n ) f(n) f(n)满足  
 T ( n ) ≤ c ⋅ f ( n ) T(n) \\leq c \\cdot f(n) T(n)≤c⋅f(n)  
则记作  
 T ( n ) = O ( f ( n ) ) T(n) = O(f(n)) T(n)=O(f(n))  
可以简单地认为， **O ( f ( n ) ) O(f(n)) O(f(n))表示运行时间与 f ( n ) f(n) f(n)成正比，比如 O ( n 2 ) O(n^2) O(n2)表示运行时间与输入规模的平方成正比，这样讲虽然并不严谨，但一般情况下无伤大雅**。

\*\*在 n n n很大时，常数 c c c变得无关紧要，不同算法间的比较主要关注 f ( n ) f(n) f(n)部分的大小。\*\*比如，在 n > > 100 n >> 100 n>>100时， n 2 n^2 n2要比 100 n 100n 100n大得多，因此重点关注 n 2 n^2 n2和 n n n增长速度的差异即可。

不同时间复杂度的增长速度对比如下，图片来自[Big-O Cheat Sheet Poster][]，

![Big-O Complexity][]

除了大 O O O记号，还有大 Ω \\Omega Ω记号和 Θ \\Theta Θ记号，分别表示下界和确界，  
 Ω ( f ( n ) ) :   c ⋅ f ( n ) ≤ T ( n ) Θ ( f ( n ) ) :   c 1 ⋅ f ( n ) ≤ T ( n ) ≤ c 2 ⋅ f ( n ) \\Omega(f(n)) : \\ c\\cdot f(n) \\leq T(n) \\\\\\Theta(f(n)) : \\ c\_1 \\cdot f(n) \\leq T(n) \\leq c\_2 \\cdot f(n) Ω(f(n)): c⋅f(n)≤T(n)Θ(f(n)): c1⋅f(n)≤T(n)≤c2⋅f(n)  
他们的关系如下图所示，图片截自[邓俊辉-数据结构C++描述第三版][-_C]

![渐进复杂度不同记号关系][format_png]

# 常用数据结构操作与算法的复杂度 #

下面汇总摘录了常用数据结构操作和排序算法的复杂度，来源见引用。其中包含最坏时间复杂度、平均时间复杂度以及空间复杂度等，对于排序算法还含有最好时间复杂度。

![Common Data Structure Operations][]

![Graph and Heap Operations][]

![array sorting algorithms][]

附带上链接：

[Array][] [Stack][] [Queue][] [Singly-Linked List][] [Doubly-Linked List][] [Skip List][] [Hash Table][] [Binary Search Tree][] [Cartesian Tree][] [B-Tree][] [Red-Black Tree][] [Splay Tree][] [AVL Tree][] [KD Tree][]

[Quicksort][] [Mergesort][] [Timsort][] [Heapsort][] [Bubble Sort][] [Insertion Sort][] [Selection Sort][] [Tree Sort][] [Shell Sort][] [Bucket Sort][] [Radix Sort][] [Counting Sort][] [Cubesort][]

以及[ Data Structures in geeksforgeeks][Data Structures in geeksforgeeks]。

# 输入规模较小时的情况 #

渐进复杂度分析的是输入规模较大时的情况，输入规模较小时呢？

**在输入规模较小时，就不能轻易地忽略掉常数 c c c的作用**，如下图所示，图片来自[Growth Rates Review][]。**复杂度增长快的在输入规模较小时可能会小于复杂度增长慢的**。

![complexity growth rates][]

所以在选择算法时，不能无脑上看起来更快的高级数据结构和算法，还得具体问题具体分析，因为高级数据结构和算法在实现时往往附带额外的计算开销，如果其带来的增益无法抵消掉隐含的代价，可能就会得不偿失。

这同时也给了我们在代码优化方向上的启示，

*  一是从 f ( n ) f(n) f(n)上进行优化，比如使用更高级的算法和数据结构；
 *  还有是对常数 c c c进行优化，比如移除循环体中不必要的索引计算、重复计算等。

以上

# 引用 #

*  [Big-O Cheat Sheet Poster][]
 *  [Know Thy Complexities][]
 *  [邓俊辉-数据结构C++描述第三版][-_C]
 *  [Growth Rates Review][]

[blog.shinelee.me]: https://blog.shinelee.me/
[Link 1]: https://www.cnblogs.com/shine-lee/
[CSDN]: https://blog.csdn.net/blogshinelee
[Big-O Cheat Sheet Poster]: https://imgur.com/gallery/7tIk0/comment/727923588
[Big-O Complexity]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9zMi5heDF4LmNvbS8yMDE5LzExLzIyL003RVRZUS5wbmc?x-oss-process=image/format,png
[-_C]: https://book.douban.com/subject/25859528/
[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9zMi5heDF4LmNvbS8yMDE5LzExLzIyL003blZ2ZC5wbmc?x-oss-process=image/format,png
[Common Data Structure Operations]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9zMi5heDF4LmNvbS8yMDE5LzExLzIyL003VlRISy5wbmc?x-oss-process=image/format,png
[Graph and Heap Operations]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9zMi5heDF4LmNvbS8yMDE5LzExLzIyL003ZWtkSy5wbmc?x-oss-process=image/format,png
[array sorting algorithms]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9zMi5heDF4LmNvbS8yMDE5LzExLzIyL01UVWRZOS5wbmc?x-oss-process=image/format,png
[Array]: http://en.wikipedia.org/wiki/Array_data_structure
[Stack]: http://en.wikipedia.org/wiki/Stack_%28abstract_data_type%29
[Queue]: http://en.wikipedia.org/wiki/Queue_%28abstract_data_type%29
[Singly-Linked List]: http://en.wikipedia.org/wiki/Singly_linked_list#Singly_linked_lists
[Doubly-Linked List]: http://en.wikipedia.org/wiki/Doubly_linked_list
[Skip List]: http://en.wikipedia.org/wiki/Skip_list
[Hash Table]: http://en.wikipedia.org/wiki/Hash_table
[Binary Search Tree]: http://en.wikipedia.org/wiki/Binary_search_tree
[Cartesian Tree]: https://en.wikipedia.org/wiki/Cartesian_tree
[B-Tree]: http://en.wikipedia.org/wiki/B_tree
[Red-Black Tree]: http://en.wikipedia.org/wiki/Red-black_tree
[Splay Tree]: https://en.wikipedia.org/wiki/Splay_tree
[AVL Tree]: http://en.wikipedia.org/wiki/AVL_tree
[KD Tree]: http://en.wikipedia.org/wiki/K-d_tree
[Quicksort]: http://en.wikipedia.org/wiki/Quicksort
[Mergesort]: http://en.wikipedia.org/wiki/Merge_sort
[Timsort]: http://en.wikipedia.org/wiki/Timsort
[Heapsort]: http://en.wikipedia.org/wiki/Heapsort
[Bubble Sort]: http://en.wikipedia.org/wiki/Bubble_sort
[Insertion Sort]: http://en.wikipedia.org/wiki/Insertion_sort
[Selection Sort]: http://en.wikipedia.org/wiki/Selection_sort
[Tree Sort]: https://en.wikipedia.org/wiki/Tree_sort
[Shell Sort]: http://en.wikipedia.org/wiki/Shellsort
[Bucket Sort]: http://en.wikipedia.org/wiki/Bucket_sort
[Radix Sort]: http://en.wikipedia.org/wiki/Radix_sort
[Counting Sort]: https://en.wikipedia.org/wiki/Counting_sort
[Cubesort]: https://en.wikipedia.org/wiki/Cubesort
[Data Structures in geeksforgeeks]: https://www.geeksforgeeks.org/data-structures/
[Growth Rates Review]: https://opendsa-server.cs.vt.edu/ODSA/Books/Everything/html/GrowthRate.html
[complexity growth rates]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9zMi5heDF4LmNvbS8yMDE5LzExLzIyL003dUZacS5wbmc?x-oss-process=image/format,png
[Know Thy Complexities]: https://www.bigocheatsheet.com/