Skynet

---------- ---------- 我的新 blog : liukaiyi.cublog.cn ---------- ----------

  BlogJava :: 首页 :: 联系 :: 聚合  :: 管理
  112 Posts :: 1 Stories :: 49 Comments :: 0 Trackbacks
发现 自己写个小程序 - 文本存储二叉结构的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(n2)
  • 雞尾酒排序 (Cocktail sort, 雙向的冒泡排序) — O(n2)
  • 插入排序 (insertion sort)— O(n2)
  • 桶排序 (bucket sort)— O(n); 需要 O(k) 額外空間
  • 計數排序 (counting sort) — O(n+k); 需要 O(n+k) 額外空間
  • 合併排序 (merge sort)— O(n log n); 需要 O(n) 額外空間
  • 原地合併排序 — O(n2)
  • 二叉排序樹排序 (Binary tree sort) — O(n log n)期望時間; O(n2)最壞時間; 需要 O(n) 額外空間
  • 鴿巢排序 (Pigeonhole sort) — O(n+k); 需要 O(k) 額外空間
  • 基數排序 (radix sort)— O(n·k); 需要 O(n) 額外空間
  • Gnome sort — O(n2)
  • Library sort — O(n log n) with high probability, 需要 (1+ε)n 額外空間

[編輯] 不穩定

[編輯] 不實用的排序演算法

  • Bogo排序 — O(n × n!) 期望時間,無窮的最壞情況。
  • Stupid sort — O(n3); 遞迴版本需要 O(n2) 額外記憶體
  • Bead sort — O(n) or O(√n), 但需要特別的硬體
  • Pancake sorting — O(n), 但需要特別的硬體
















整理 www.blogjava.net/Good-Game
posted on 2009-11-17 23:12 刘凯毅 阅读(2317) 评论(0)  编辑  收藏 所属分类: 算法/函数

只有注册用户登录后才能发表评论。


网站导航: