DEV Community
·
大O符号速查表
💡
原文英文，约300词，阅读约需1分钟。
📝
内容提要
本文总结了常见数据结构和算法的时间复杂度，包括数组、链表、栈、队列、哈希表、二叉搜索树等的操作复杂度，以及各种排序算法的复杂度。
🎯
关键要点
- 本文总结了常见数据结构和算法的时间复杂度。
- 常见的时间复杂度包括O(1)、O(log n)、O(n)、O(n log n)、O(n²)、O(2ⁿ)和O(n!)。
- 数组的操作复杂度：访问O(1)，搜索O(n)，插入/删除O(n)。
- 链表的操作复杂度：访问/搜索O(n)，插入/删除O(1)（在头部/尾部）。
- 栈和队列的操作复杂度：推入/弹出O(1)，入队/出队O(1)。
- 哈希表的平均和最坏情况复杂度：搜索O(1)（最坏O(n)），插入/删除O(1)（最坏O(n)）。
- 二叉搜索树的平均和最坏情况复杂度：搜索/插入/删除O(log n)（最坏O(n)）。
- 平衡二叉搜索树（AVL、红黑树）的操作复杂度：搜索/插入/删除O(log n)。
- 堆的操作复杂度：插入O(log n)，删除最小/最大O(log n)，查找最小/最大O(1)。
- 图的操作复杂度：添加顶点O(1)，添加边O(1)，搜索（DFS/BFS）O(V + E)。
- 排序算法的复杂度包括冒泡排序、插入排序、选择排序、归并排序、快速排序、堆排序和基数排序等。
❓
延伸问答
什么是大O符号？
大O符号用于描述算法的时间复杂度，表示算法在最坏情况下的运行时间增长率。
数组的操作复杂度是什么？
数组的访问复杂度为O(1)，搜索为O(n)，插入和删除为O(n)。
链表的插入和删除复杂度如何？
链表在头部或尾部插入和删除的复杂度为O(1)，而访问和搜索的复杂度为O(n)。
哈希表的搜索复杂度是什么？
哈希表的平均搜索复杂度为O(1)，最坏情况下为O(n)。
二叉搜索树的复杂度如何？
二叉搜索树的平均搜索、插入和删除复杂度为O(log n)，最坏情况下为O(n)。
常见的排序算法复杂度有哪些？
常见排序算法的复杂度包括冒泡排序O(n²)、插入排序O(n²)、归并排序O(n log n)、快速排序O(n log n)等。
➡️
