# 算法基础和复杂度

http://blog.csdn.net/pipisorry/article/details/36014835

[算法分析的基础知识ppt讲解]

[All Algorithms implemented in Python (for education)]

Graph of |V| vertices and |E| edges
-
O(|E| + |V|)
O(|V|) 广度优先搜索 (BFS)
Graph of |V| vertices and |E| edges
-
O(|E| + |V|)
O(|V|) 二分查找
Sorted array of n elements
O(log(n))
O(log(n))
O(1) 穷举查找
Array
O(n)
O(n)
O(1) 最短路径-Dijkstra，用小根堆作为优先队列
Graph with |V| vertices and |E| edges
O((|V| + |E|) log |V|)
O((|V| + |E|) log |V|)
O(|V|) 最短路径-Dijkstra，用无序数组作为优先队列
Graph with |V| vertices and |E| edges
O(|V|^2)
O(|V|^2)
O(|V|) 最短路径-Bellman-Ford
Graph with |V| vertices and |E| edges
O(|V||E|)
O(|V||E|)
O(|V|) 排序

O(n log(n))
O(n log(n))
O(n^2)
O(n) 归并排序

O(n log(n))
O(n log(n))
O(n log(n))
O(n) 堆排序

O(n log(n))
O(n log(n))
O(n log(n))
O(1) 冒泡排序

O(n)
O(n^2)
O(n^2)
O(1) 插入排序

O(n)
O(n^2)
O(n^2)
O(1) 选择排序

O(n^2)
O(n^2)
O(n^2)
O(1) 桶排序

O(n+k)
O(n+k)
O(n^2)
O(nk) 基数排序

O(nk)
O(nk)
O(nk)
O(n+k) 数据结构

O(1)
O(n)
-
-
O(1)
O(n)
-
-
O(n) 动态数组
O(1)
O(n)
O(n)
O(n)
O(1)
O(n)
O(n)
O(n)
O(n) 单链表
O(n)
O(n)
O(1)
O(1)
O(n)
O(n)
O(1)
O(1)
O(n) 双链表
O(n)
O(n)
O(1)
O(1)
O(n)
O(n)
O(1)
O(1)
O(n) 跳表
O(log(n))
O(log(n))
O(log(n))
O(log(n))
O(n)
O(n)
O(n)
O(n)
O(n log(n)) 哈希表
-
O(1)
O(1)
O(1)
-
O(n)
O(n)
O(n)
O(n) 二叉搜索树
O(log(n))
O(log(n))
O(log(n))
O(log(n))
O(n)
O(n)
O(n)
O(n)
O(n) 笛卡尔树
-
O(log(n))
O(log(n))
O(log(n))
-
O(n)
O(n)
O(n)
O(n) B-树
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) 红黑树
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) 伸展树
-
O(log(n))
O(log(n))
O(log(n))
-
O(log(n))
O(log(n))
O(log(n))
O(n) AVL 树
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) 堆
Heaps

Increase Key

-
O(1)
O(1)
O(n)
O(n)
O(1)
O(m+n) 链表（未排序）
-
O(n)
O(n)
O(1)
O(1)
O(1)
O(1) 二叉堆
O(n)
O(1)
O(log(n))
O(log(n))
O(log(n))
O(log(n))
O(m+n) 二项堆
-
O(log(n))
O(log(n))
O(log(n))
O(log(n))
O(log(n))
O(log(n)) 斐波那契堆
-
O(1)
O(log(n))*
O(1)*
O(1)
O(log(n))*
O(1) 图节点 / 边 管理
Storage
Remove Vertex
Remove Edge
Query 邻接表
O(|V|+|E|)
O(1)
O(1)
O(|V| + |E|)
O(|E|)
O(|V|) 关联表
O(|V|+|E|)
O(1)
O(1)
O(|E|)
O(|E|)
O(|E|) 邻接矩阵
O(|V|^2)
O(|V|^2)
O(1)
O(|V|^2)
O(1)
O(1) 关联矩阵
O(|V| ⋅ |E|)
O(|V| ⋅ |E|)
O(|V| ⋅ |E|)
O(|V| ⋅ |E|)
O(|V| ⋅ |E|)
O(|E|)

[http://top.jobbole.com/1599/]

from: http://blog.csdn.net/pipisorry/article/details/36014835

ref: