《程序员修炼之道》
第6章当你编码时 32算法速率
O(1) 常量型(访问数组元素,简单语句)
O(log2(n)) 对数型(二分查找)
O(n) 线性型(顺序查找)
O(n*log2(n)) 比线性差,但不会差很多(快速排序、堆排序的平均运行时间)
O(n^2) 平方率型(选择和插入排序)
O(n^3) 立方型(2n*n矩阵相乘)
O(C^n) 指数型(旅行商问题,集合划分)
处理10个数据项需要1分钟的算法,处理100个数据项可能需要一生的时间。
常识估算
~~~~~~~
简单循环:很可能是O(n)
嵌套循环:往往是O(n^2)
二分法:可能是O(log2(n))
分而治之:O(n*log2(n))
组合: