数据结构与算法分析第3章.ppt

数据结构与算法分析APracticalIntroductiontoDataStructuresandAlgorithmAnalysis陈星第3章算法分析如何检测算法的效率？
实际测量算法的计算机运算时间。
问题：1.需为每种算法都编写程序。
2.代码质量对计算机耗时有影响。
3.测试数据的选择对计算机耗时有影响。
4.需要所有算法都运行一遍。

渐近算法分析（简称算法分析）
估算算法及实现它的程序的效率和开销。计算机的关键资源
时间代价
空间代价（内存和磁盘空间）

分析算法效率的可行方法
可行的方法：
一定规模下，算法所需基本运算的执行次数。
基本运算的选择原则：
1、算法执行的运算总次数与基本运算的次数大体上成比例。
2、基本运算以外的其它运算的运算量可以忽略。影响运行时间的因素
假设在代码质量、编译系统等与算法无关的因素
相同的条件下，影响某算法程序执行时间的因素：
1.问题的规模。
运行时间T可以表示为规模n的函数T(n)。

2.特定的输入。问题规模对运行时间的影响
例1:查找数组元素中的最大值
intlargest(intarray[],intn){
intcurrlarge=0;//Largestvalueseen
for(inti=1;i<n;i++)//Foreachval
if(array[currlarge]<array[i])
currlarge=i;//Rememberpos
returncurrlarge;//Returnlargest
}

问题的规模：数组的大小n
基本操作：整数的比较
设每次整数比较的时间为c，则运行时间
T(n)=cn例2:将数组中第k元素赋给某变量
T(n)=c
常数运行时间：输入规模n对运行时间不产生影响。

例3:
sum=0;
for(i=1;i<=n;i++)
for(j=1;j<n;j++)
sum++;
}

T(n)=cn2

算法的增长率是指当输入的值增长时，算法代价的增长速率。特定输入对运行时间的影响
例1:查找数组元素中的值为x的元素
intSearchX(intarray[],intn){
for(inti=1;i<n;i++){//Foreachval
if(array[i]==x)
returni;
}
return0;
}

算法的最佳情况、最差情况、平均情况。更快的计算机还是更快的算法？
如果计算机的速度增快10倍？渐近分析
当输入规模很大后，我们分析一种算法运行时间增长率时，可以忽略算法运行时间函数的系数。

上限(大O表示法)
描述一种算法消耗某种资源（通常是时间）的最大值。
对非负函数T(n)，若存在两个正常数c和n0，对任意n>n0，有T(n)≤cf(n)，则称T(n)在集合O(f(n))中。

例：某一算法平均情况下T(n)=c1n2+c2n,c1,c2为正整数。若n>1，c1n2+c2n≤c1n2+c2n2。因此取c=c1+c2，n0=1，有T(n)≤cn2。故T(n)在O(n2)中。下限（大Ω表示法）
描述算法消耗某种资源（通常是时间）的最小值。
对非负函数T(n)，若存在两个正常数c和n0，对任意n>n0，有T(n)≥cg(n)，则称T(n)在集合Ω(g(n))中。
例：某一算法平均情况下T(n)=c1n2+c2n,c1,c2为正整数。若n>1，c1n2+c2n≥c1n2。因此取c=c1，n0=1，有T(n)≥cn2。故T(n)在Ω(n2)中。

Θ表示法：如果一种算法既在O(h(n))中，又在Ω(h(n))中，则称其为Θ(h(n))。

化简原则：计算某算法代价的渐近增长率时，忽略所有的常数和低次项。程序运行时间的计算
例3.8a=b;
该赋值语句执行时间为一个常量，因此时间代价为(1).

例3.9sum=0;
for(i=1;i<=n;i++)
sum+=n;

例3.10sum=0;
for(i=1;i<=n;j++)
for(j=1;j<=i;i++)
sum++;
for(k=0;k<n;k++)
A[k]=k;注意！！！
对大多数算法，其上限和下限是相同的。

上限≠最差情况，下限≠最佳情况
上（下）限是用来确定运行时间随输入规模增加的增长率，而不是用来确定运行时间。

规模小≠最佳情况，规模大≠最差情况。多参数问题
数组：count保存像素值（颜色）出现次数。
value保存各像素的值（颜色）
常量：C像素值（颜色）的数量；P像素的数量

for(i=0;i<C;i++)//初始化count
count[i]=0;Θ(c)
for(i=0;i<P;i++)//扫描所有像素
count[value(i)]++;//统计各类像素值的数量Θ(p)
sort(count);//对像素值按数量排序Θ(clogc)
总的时