算法复杂度分析图-白红宇

发现自己写个小程序 - 文本存储二叉结构的hashMap。那个费劲！痛下决心仔细学习算法。

（如果大家有兴趣就跟我一起 -

《算法导论》

，也望大家监督我能每天拿出一小时和大家分享算法,算法代码我会尽量使用 py 和解决一些分析日志的应用上靠（其实，上面费劲的

二叉hash

是为了分析日志中 - 希望能实现多个大文件不需要合并就能根据某列排序输出! 目前的解决办法 find .. -exec cat {} \; | perl |sort 的笨方法）

1. 算法在计算中的作用（笔记） :

算法(algorithm):就是定义良好的计算过程，它取一个或一组作为输出，并产生一个或一组自作为输出。

一些函数运行级别 # http://www.wolframalpha.com/ 函数都可在网站里运行

这里 n=一亿条数据 :

log_2(n) 30

n^0.5 31622

n 10^9

n*log_2(n) 2.9^10

n^2 10^18

n^3 10^27

2^n 无穷

n! 10^362880

需要知道的复杂度 - 在某一个临界点后合并会别插入要快的

插入排序复杂度 n^2 http://www.wolframalpha.com/input/?i=n^2

合并排序复杂度 n*log_2(n) http://www.wolframalpha.com/input/?i=n*log_2%28n%29+

网上的查找到的一些名称：参考 http://www.51testing.com/?uid-130868-action-viewspace-itemid-66729

1.1

稳定排序非稳定排序 -

稳定排序是所有相等的数经过某种排序方法后，仍能保持它们在排序之前的相对次序，。反之，就是非稳定的排序。

1.2

内排序外排序

在排序过程中，所有需要排序的数都在内存，并在内存中调整它们的存储顺序，称为内排序；在排序过程中，只有部分数被调入内存，并借助内存调整数在外存中的存放顺序排序方法称为外排序。

1.3

算法的时间复杂度空间复杂度

所谓算法的时间复杂度，是指执行算法所需要的计算工作量。一个算法的空间复杂度，一般是指执行这个算法所需要的内存空间。

几种常见的算法复杂度：

2.1冒泡排序（Bubble Sort） O(n^2)

2.2选择排序（Selection Sort） O(n^2 )

2.3插入排序（Insertion Sort） O(n^2)

2.4堆排序 O( nlog(n) )

2.5归并排序 O( nlog_2(n) )

2.6快速排序最好 O( nlog_2(n) ) 最坏 O(n^2)

wiki 参考：http://zh.wikipedia.org/wiki/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95

穩定的

（bubble sort） — O(n²)

(Cocktail sort, 雙向的冒泡排序) — O(n²)

（insertion sort）— O(n²)

（bucket sort）— O(n); 需要 O(k) 額外空間

(counting sort) — O(n+k); 需要 O(n+k) 額外空間

（merge sort）— O(n log n); 需要 O(n) 額外空間

原地 — O(n²)

排序（Binary tree sort） — O(n log n)期望時間; O(n²)最壞時間; 需要 O(n) 額外空間

(Pigeonhole sort) — O(n+k); 需要 O(k) 額外空間

（radix sort）— O(n·k); 需要 O(n) 額外空間

— O(n²)

— O(n log n) with high probability, 需要 (1+ε)n 額外空間

[] 不穩定

（selection sort）— O(n²)

（shell sort）— O(n log n) 如果使用最佳的現在版本

— O(n log n)

（heapsort）— O(n log n)

— O(n log n)

（quicksort）— O(n log n) 期望時間, O(n²) 最壞情況; 對於大的、亂數串列一般相信是最快的已知排序

— O(n log n)

— O(n log n + k) 最壞情況時間，需要額外的 O(n + k) 空間，也需要找到（longest increasing subsequence）

[] 不實用的排序演算法

— O(n × n!) 期望時間，無窮的最壞情況。

— O(n³); 遞迴版本需要 O(n²) 額外記憶體

— O(n) or O(√n), 但需要特別的硬體

— O(n), 但需要特別的硬體

本文转自博客园刘凯毅的博客，原文链接：

，如需转载请自行联系原博主。