大O小抄

翻译自Big-O Cheat Sheet

嗨,您好!该网页涵盖了计算机科学中常用算法的时空Big-O复杂性。过去在准备技术面试时,我发现自己花了数小时在互联网上搜寻和整理搜索算法和排序算法的最佳,平均和最坏情况,以免被问到这些问题时感到困惑。在过去的几年中,我采访了多家硅谷初创公司以及一些较大的公司,例如Google,Facebook,Yahoo,LinkedIn和Uber,每次我准备接受采访时,我都在想:有人创造了不错的Big-O备忘单吗?”。因此,为了节省大家很多时间,我创建了一个。请享用!-埃里克

复杂度通常会使用大-O 记号来表示,比如快速排序的平均时间复杂度是 。虽然我是「理解派」,但是虽然每个算法/数据结构都理解了,不时仍有可能忘记具体某个算法/数据结构的复杂度(特别是在最好、最坏和平均情形下的复杂度)。因此制作一个速查表是蛮有必要的。

图例
糟糕不好一般最佳

通用数据结构操作

数据结构事件复杂度空间复杂度
平均最差最差
访问查询插入删除访问查询插入删除
数组Θ(1)Θ(n)Θ(n)Θ(n)O(1)O(n)O(n)O(n)O(n)
Θ(n)Θ(n)Θ(1)Θ(1)O(n)O(n)O(1)O(1)O(n)
队列Θ(n)Θ(n)Θ(1)Θ(1)O(n)O(n)O(1)O(1)O(n)
单链表Θ(n)Θ(n)Θ(1)Θ(1)O(n)O(n)O(1)O(1)O(n)
双链表Θ(n)Θ(n)Θ(1)Θ(1)O(n)O(n)O(1)O(1)O(n)
跳表Θ(log(n))Θ(log(n))Θ(log(n))Θ(log(n))O(n)O(n)O(n)O(n)O(n log(n))
哈希表N/AΘ(1)Θ(1)Θ(1)N/AO(n)O(n)O(n)O(n)
二叉搜索树Θ(log(n))Θ(log(n))Θ(log(n))Θ(log(n))O(n)O(n)O(n)O(n)O(n)
笛卡尔树N/AΘ(log(n))Θ(log(n))Θ(log(n))N/AO(n)O(n)O(n)O(n)
B-数Θ(log(n))Θ(log(n))Θ(log(n))O(log(n))O(log(n))O(log(n))O(log(n))O(log(n))O(n)
红黑树Θ(log(n))Θ(log(n))Θ(log(n))Θ(log(n))O(log(n))O(log(n))O(log(n))O(log(n))O(n)
伸展树N/AΘ(log(n))Θ(log(n))Θ(log(n))N/AO(log(n))O(log(n))O(log(n))O(n)
AVL树Θ(log(n))Θ(log(n))Θ(log(n))Θ(log(n))O(log(n))O(log(n))O(log(n))O(log(n))O(n)
KD树Θ(log(n))Θ(log(n))Θ(log(n))Θ(log(n))O(n)O(n)O(n)O(n)O(n)

数组排序算法

算法时间复杂度空间复杂度
最优平均最差最差
快速排序Ω(n log(n))O(n log(n))O(n^2)O(log(n))
归并排序Ω(n log(n))O(n log(n))O(n log(n))O(n)
TimsortΩ(n)O(n log(n))O(n log(n))O(n)
堆排序Ω(n log(n))O(n log(n))O(n log(n))O(1)
冒泡排序Ω(n)O(n^2)O(n^2)O(1)
插入排序Ω(n)O(n^2)O(n^2)O(1)
选择排序Ω(n^2)O(n^2)O(n^2)O(1)
树排序Ω(n log(n))O(n log(n))O(n^2)O(n)
希尔排序Ω(n log(n))O(n(log(n))^2)O(n(log(n))^2)O(1)
桶排序Ω(n+k)O(n+k)O(n^2)O(n)
基数排序Ω(nk)O(nk)O(nk)O(n+k)
计数排序Ω(n+k)O(n+k)O(n+k)O(k)
立方体排序Ω(n)O(n log(n))O(n log(n))O(n)

更多

破解编码面试:150个编程问题和解决方案
算法简介,第3版
Java中的数据结构和算法(第二版)
高性能JavaScript(构建更快的Web应用程序界面)

写于 2020年06月15日185

如非特别注明,文章皆为原创。

转载请注明出处: https://www.liayal.com/article/5ee781217ff0f07e0ea449b5

记小栈小程序上线啦~搜索【记小栈】【点击扫码】体验

你不想说点啥么?
😀😃😄😁😆😅😂🤣☺️😊😇🙂🙃😉😌😍😘😗😙😚😋😜😝😛🤑🤗🤓😎🤡🤠😏😒😞😔😟😕🙁☹️😣😖😫😩😤😠😡😶😐😑😯😦😧😮😲😵😳😱😨😰😢😥🤤😭😓😪😴🙄🤔🤥😬🤐🤢🤧😷🤒🤕😈👿👹👺💩👻💀☠️👽👾🤖🎃😺😸😹😻😼😽🙀😿😾👐👐🏻👐🏼👐🏽👐🏾👐🏿🙌🙌🏻🙌🏼🙌🏽🙌🏾🙌🏿👏👏🏻👏🏼👏🏽👏🏾👏🏿🙏🙏🏻🙏🏼🙏🏽🙏🏾🙏🏿🤝👍👍🏻👍🏼👍🏽👍🏾👍🏿👎👎🏻👎🏼👎🏽👎🏾👎🏿👊👊🏻👊🏼👊🏽👊🏾👊🏿✊🏻✊🏼✊🏽✊🏾✊🏿

评论

~ 评论还没有,沙发可以有 O(∩_∩)O~