算法评价标准

性能指标

第一点,算法的运行时间。根据输入数据的规模n评价算法的性能:

  1. 常数级 O( 1 )
  2. 对数级 O( logn ),EX: 二分查找
  3. 次线性级 O( n^d ), d<1
  4. 线性级 O( n )
  5. nlog(n)级 O( nlogn ),EX: 分治法,把n分成n/2的子问题,再合并子问题,t(n)=2*t(n/2)+O(n)
  6. 平方级 O( n^2 ), EX: 特征是循环结构
  7. 指数级 O( n^k), k>2

第二点,算法消耗的内存或存储空间。

发表评论