算法性能分析和量度

/*
Gama的算法和数据结构学习笔记
*/

算法性能分析和量度

o. 算法效率量度有两种方法：前期估计和后期测试。

o. 算法效率的后期测试
  *. 算法效率的后期测试指的是通过在算法中的某些部位插入取时间的函数，来测定算法完成某一规定功能所消耗的时间。
  *. 如果时间函数的精度不够，就需要让这个待测定算法重复若干次，取得总的时间，再除以重复的次数，进而得到算法的平均一次执行时间。
  *. 使用后期测试方法量度一个算法的效率，有一个问题在于：同样的算法在不同的硬件配置，使用不同的编译器，不同的编译策略（debug/release），都会造成测试时间的不同。因此，量度算法效率的更好的方法是通过比较算法的复杂性，即前期估计算法复杂度的方法，来比较算法的优劣。前期复杂度估计可以避免由于不同的运行环境，编译器而造成的差异。

o. 算法效率的前期估计
  *. 算法复杂性的量度取决于计算时间和存储需求，因此分为时间复杂度估计和空间复杂度估计。
  *. ...
  *. ...

o. 算法的时间复杂度
  *. 时间复杂度量度的单位是语法意义上的一个程序步。规定：
     注释语句：程序步数为0；
     声明语句：程序步数为0；（包括：定义常量变量，结构定义，函数特征声明，权限声明等）
     不含函数的表达式：程序步数为1；
     赋值语句：<变量>=<表达式>；赋值语句的步数取决于表达式的步数，如果表达式不包含函数调用，则步数为1，如果包含函数，则为函数调用的总步数。如果赋值语句的变量为数组，则赋值语句的步数为变量的大小+表达式步数；
     循环语句：仅考虑循环控制语句的步数。对于“while<表达式>{...}”语句，循环控制步数为表达式步数；对于“for(<初始化语句>;<表达式1>;<表达式2>){...}”，第一次程序步数等于<初始化语句>+<表达式1>的步数之和，第二次及以后之后程序步数等于<表达式1>+<表达式2>的步数之和；
     switch语句：执行步数等于switch条件中表达式的步数+某个条件满足的程序步数；
     if语句：取决于满足条件部分语句的步数+辨别表达式的步数；
     函数执行语句：一般步数为1；如果函数为递归调用，还要考虑函数中的局部变量；
     new/delete/sizeof语句：步数为1；还要分析构造函数和析构函数的步数；
     转移语句return,continue,break,goto：步数为1
  *. 确定程序步数有两种方法：
     一是可以设置一个全局的count变量，在每一个执行语句的附近改变count的值；
     二是可以建立一个表，先列出每个语句执行一次的步数，再列出每个语句执行的次数，最后相乘得到各个语句的步数，加总即为总的程序步数。
  *. 要确定一个程序的精确程序步数非常困难且不必要，因为程序步数本身就不是一个精确的概念（例如，x=a与x=a+b*c/d-e具有相同的程序步数），并不能确切反映运行时间，所以用准确的程序步数来判别算法的优劣并不是很有价值。因此，我们只需要得到一个数量级的估计值就可以了，也就是需要一个时间复杂度的渐进度量值，我们使用大O表示法：
     T(n)=f(n)=O(n)
    其中,T(n)为算法的时间复杂度，可以由一个函数f(n)来估计，而O()用来取f(n)的量级。大O表示法常用来分析算法在最坏情况下的时间代价，就是说当n充分大的时候，用大O方法来估计时间复杂度。大O方法主要关注关键操作，大部分的关键操作都存在于循环和递归中。
  *. 大O表示法的规则：
    1. 假设n充分大的时候，取最高次幂，eg. f(n)=2nE3+3nE2+4n+1，则T(n)=O(nE3)；
    2. 加法规则：是针对几个并列的程序段，比如两个并列的循环，T1(n)=O(f(n)),T2(m)=O(g(m)),则整个程序段的时间代价为
     T(n,m) = T1(n)+T2(m) = O(max{f(n),g(m)})
     所谓max{f(n),g(n)}指的是，当n,m充分大的时候，f(n),g(m)的最大值，参考如下关系：
     c < log2n < n < nlog2n < nE2 < nE3 < 2En < 3En < n!
     -----------------------  ---------  ----------------
       good efficiency         ok effe    very complicate
    3. 乘法规则：针对多层嵌套的循环，关键操作应该在最内层循环中，应该自外向内层层分析每层循环的渐进时间复杂度，然后利用大O表示法的乘法规则来计算其渐进式间复杂度。比如，两个嵌套的循环，T1(n)=O(f(n)),T2(m)=O(g(m))，则整个程序段的时间代价为
     T(n,m) = T1(n)*T2(m) = O(f(n)*g(m))
     一个特例，如果T1(n)=O(c),T2(m)=O(g(m)),那么：
     T(n,m) = T1(n)*T2(m) = O(c*g(m)) = O(g(m))
     这说明,对任何正常数都属于一个数量级，O(1)。

责任编辑 webmaster

相关链接

字符串匹配算法研究

C编程- 以空间换时间算法集锦

遗传格网障碍算法

蒙特卡罗算法在围棋游戏AI中的...

背包问题的算法集

负载均衡的基本算法

算法—用栈实现递归

QQ程序的加密算法-C#版