每个程序员都应该收藏的算法复杂度速查表

简介:

算法复杂度这件事

这篇文章覆盖了计算机科学里面常见算法的时间和空间的大 OBig-O 复杂度。我之前在参加面试前,经常需要花费很多时间从互联网上查找各种搜索和排序算法的优劣,以便我在面试时不会被问住。最近这几年,我面试了几家硅谷的初创企业和一些更大一些的公司,如 Yahoo、eBay、LinkedIn 和 Google,每次我都需要准备这个,我就在问自己,“为什么没有人创建一个漂亮的大 O 速查表呢?”所以,为了节省大家的时间,我就创建了这个,希望你喜欢!

--- Eric 

图例

绝佳 不错 一般 不佳 糟糕

数据结构操作

数据结构 时间复杂度 空间复杂度
  平均 最差 最差
  访问 搜索 插入 删除 访问 搜索 插入 删除  
Array O(1) O(n) O(n) O(n) O(1) O(n) O(n) O(n) O(n)
Stack O(n) O(n) O(1) O(1) O(n) O(n) O(1) O(1) O(n)
Singly-Linked List O(n) O(n) O(1) O(1) O(n) O(n) O(1) O(1) O(n)
Doubly-Linked List O(n) O(n) O(1) O(1) O(n) O(n) O(1) O(1) O(n)
Skip List O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(n) O(n) O(n) O(n) O(n log(n))
Hash Table - O(1) O(1) O(1) - O(n) O(n) O(n) O(n)
Binary Search Tree O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(n) O(n) O(n) O(n) O(n)
Cartesian Tree - O(log(n)) O(log(n)) O(log(n)) - O(n) O(n) O(n) O(n)
B-Tree O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(n)
Red-Black Tree O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(n)
Splay Tree - O(log(n)) O(log(n)) O(log(n)) - O(log(n)) O(log(n)) O(log(n)) O(n)
AVL Tree O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(n)

数组排序算法

算法 时间复杂度 空间复杂度
  最佳 平均 最差 最差
Quicksort O(n log(n)) O(n log(n)) O(n^2) O(log(n))
Mergesort O(n log(n)) O(n log(n)) O(n log(n)) O(n)
Timsort O(n) O(n log(n)) O(n log(n)) O(n)
Heapsort O(n log(n)) O(n log(n)) O(n log(n)) O(1)
Bubble Sort O(n) O(n^2) O(n^2) O(1)
Insertion Sort O(n) O(n^2) O(n^2) O(1)
Selection Sort O(n^2) O(n^2) O(n^2) O(1)
Shell Sort O(n) O((nlog(n))^2) O((nlog(n))^2) O(1)
Bucket Sort O(n+k) O(n+k) O(n^2) O(n)
Radix Sort O(nk) O(nk) O(nk) O(n+k)

图操作

节点 / 边界管理 存储 增加顶点 增加边界 移除顶点 移除边界 查询
Adjacency list O(|V|+|E|) O(1) O(1) O(|V| + |E|) O(|E|) O(|V|)
Incidence list O(|V|+|E|) O(1) O(1) O(|E|) O(|E|) O(|E|)
Adjacency matrix O(|V|^2) O(|V|^2) O(1) O(|V|^2) O(1) O(1)
Incidence matrix O(|V| ⋅ |E|) O(|V| ⋅ |E|) O(|V| ⋅ |E|) O(|V| ⋅ |E|) O(|V| ⋅ |E|) O(|E|)

堆操作

类型 时间复杂度
  Heapify 查找最大值 分离最大值 提升键 插入 删除 合并
Linked List (sorted) - O(1) O(1) O(n) O(n) O(1) O(m+n)
Linked List (unsorted) - O(n) O(n) O(1) O(1) O(1) O(1)
Binary Heap O(n) O(1) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(m+n)
Binomial Heap - O(1) O(log(n)) O(log(n)) O(1) O(log(n)) O(log(n))
Fibonacci Heap - O(1) O(log(n)) O(1) O(1) O(log(n)) O(1)

大 O 复杂度图表

Big O Complexity Graph

Big O Complexity Graph

原文发布时间为:2016-06-20

本文来自云栖社区合作伙伴“Linux中国”

相关文章
|
20天前
|
人工智能 编解码 算法
DeepSeek加持的通义灵码2.0 AI程序员实战案例:助力嵌入式开发中的算法生成革新
本文介绍了通义灵码2.0 AI程序员在嵌入式开发中的实战应用。通过安装VS Code插件并登录阿里云账号,用户可切换至DeepSeek V3模型,利用其强大的代码生成能力。实战案例中,AI程序员根据自然语言描述快速生成了C语言的base64编解码算法,包括源代码、头文件、测试代码和CMake编译脚本。即使在编译错误和需求迭代的情况下,AI程序员也能迅速分析问题并修复代码,最终成功实现功能。作者认为,通义灵码2.0显著提升了开发效率,打破了编程语言限制,是AI编程从辅助工具向工程级协同开发转变的重要标志,值得开发者广泛使用。
7908 68
DeepSeek加持的通义灵码2.0 AI程序员实战案例:助力嵌入式开发中的算法生成革新
|
5月前
|
负载均衡 监控 算法
每个程序员都应该知道的 6 种负载均衡算法
每个程序员都应该知道的 6 种负载均衡算法
620 2
|
6月前
|
算法 程序员 Python
程序员必看!Python复杂度分析全攻略,让你的算法设计既快又省内存!
在编程领域,Python以简洁的语法和强大的库支持成为众多程序员的首选语言。然而,性能优化仍是挑战。本文将带你深入了解Python算法的复杂度分析,从时间与空间复杂度入手,分享四大最佳实践:选择合适算法、优化实现、利用Python特性减少空间消耗及定期评估调整,助你写出高效且节省内存的代码,轻松应对各种编程挑战。
136 1
|
7月前
|
算法 搜索推荐 程序员
程序员常用算法详细讲解
每一种算法都有其适用场景,了解并熟悉这些常用算法的策略和实现,对于解决实际编程问题具有重要的意义。需要注意的是,理论知识的重要性虽然不言而喻,但真正的理解和掌握,还需要在实践中不断地尝试和错误,以达到深入理解的目的。
71 1
|
7月前
|
机器学习/深度学习 算法 搜索推荐
程序员必须掌握的算法
作为一名程序员,掌握一些重要的算法是必不可少的。算法是解决问题的方法和步骤,对于程序员来说,熟悉和掌握一些常见的算法可以提高编程能力,解决复杂的计算问题。与此同时,算法是计算机科学中的核心概念,对于程序员来说,掌握一些基本的算法是非常重要的。
66 1
|
9月前
|
算法 程序员
程序员必知:XGB算法梳理
程序员必知:XGB算法梳理
53 0
|
9月前
|
算法 JavaScript 程序员
程序员必知:《程序设计与算法(二)算法基础》《第一周枚举》熄灯问题POJ
程序员必知:《程序设计与算法(二)算法基础》《第一周枚举》熄灯问题POJ
49 0
|
10月前
|
机器学习/深度学习 人工智能 算法
每个程序员都应该知道的 40 个算法(四)(3)
每个程序员都应该知道的 40 个算法(四)
63 2
|
10月前
|
分布式计算 并行计算 算法
每个程序员都应该知道的 40 个算法(四)(1)
每个程序员都应该知道的 40 个算法(四)
67 2

热门文章

最新文章