数据结构教程第四课算法效率的度量和存储空间需求

本课主题:衡量存储空之间的算法效率和要求

教学目的:掌握算法的渐近时间复杂度和空之间复杂度的意义和作用。

教学重点:渐近时间复杂度的意义、作用和计算方法

教学难点:渐近时间复杂性的意义

教学内容:

第一，算法效率的衡量

算法的执行时间是算法优缺点和问题规模的函数。评价一个算法的优劣，可以通过考察算法在同一尺度上的执行时间来判断。而程序的执行时间通常有两种方法:

1.事后统计的方法。

缺点:不利于大范围的算法比较。(不同的地方，不同的时间，不同的地方)

2.先验分析和估计方法。

影响程序在计算机上运行所需时间的因素
算法本身选择的策略
问题规模越大，所需时间越多
编写程序所用的语言越高，所需时间越多
编译生成的机器代码质量
机器执行指令的速度。

综上所述，为了比较算法本身的优劣，要排除其他影响算法效率的因素。

从算法中选择一个原始操作，该原始操作是针对所研究问题的基本操作，并且该基本操作的重复次数被用作算法的时间度量。(原操作在这个问题的所有算法中都是一样的)

T(n)=O(f(n))

上图显示，随着问题规模n的增加，算法执行时间的增长率与f(n)相同，称为算法的渐近时间复杂度。

求4*4个矩阵元素的和，T(4)=O(f(4))

f = n * n
sum(int num[4][4])

{ int i,j,r=0;
for(i=0;i