[collect]常见算法的时空复杂度备忘清单

本文最后更新于2016年8月6日,已超过 1 年没有更新,如果文章内容失效,还请反馈给我,谢谢!

=Start=

缘由:

了解常见算法的时间复杂度和空间复杂度对于一名程序员来说是大有裨益的——不论是准备考试、面试,还是方便自己学习、识记。

以往我在参加面试前,经常需要花费很多时间从互联网上查找各种搜索和排序算法的优劣,以便我在面试时不会被问住。也有针对性做了一些笔记,但时间一长,之前做的一些记录就都不知道放在哪去了,但现在我们可以通过 Eric 创建的 BigOCheatSheet 快速的了解常见算法的时空复杂度,省时省力,实乃居家旅行必备神器。

正文:
数据结构操作
数据结构 时间复杂度 空间复杂度
平均 最差 最差
访问 搜索 插入 删除 访问 搜索 插入 删除
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)
大O复杂度图表

bigOcomplexity

参考链接:

=END=

声明: 除非注明,ixyzero.com文章均为原创,转载请以链接形式标明本文地址,谢谢!
https://ixyzero.com/blog/archives/2794.html

《[collect]常见算法的时空复杂度备忘清单》上有8条评论

  1. 如何在最短的时间内搞定数据结构和算法,应付面试?
    https://www.zhihu.com/question/28580777

    # 什么是数据结构?
    简单说,数据结构就是一个容器,以某种特定的布局存储数据。这个“布局”使得数据结构在某些操作上非常高效,在另一些操作上则不那么高效。你的目标就是理解数据结构,这样就能为手头的问题选择最优的数据结构。

    # 为什么我们需要数据结构?
    由于数据结构用来以有组织的形式存储数据,而且数据是计算机科学中最重要的实体,因此数据结构的真正价值显而易见。
    无论你解决什么问题,你都必须以这种或那种方式处理数据——员工的工资,股票价格,购物清单,甚至简单的电话簿等等。
    根据不同的场景,数据需要以特定格式存储。目前有一些数据结构可以满足我们以不同格式存储数据的需求。

    # 常用的数据结构
    我们首先列出最常用的数据结构,然后再按个讲解:
    数组
    堆栈
    队列
    链表


    字典树(Tries,这是一种高效的树,有必要单独列出来)
    哈希表

a-z进行回复 取消回复

电子邮件地址不会被公开。 必填项已用*标注