第2章 算法分析基础

第二章 算法分析基础1 2 3 4

算法时间复杂性分析 算法空间复杂性分析 最优算法 小 结

思考如下问题 案例一——百鸡问题公元5世纪末，我国古代数学家张丘建在 他所撰写的《算经》中，提出了这样一个 问题：“鸡翁一，值钱五；鸡母一，值钱 三；鸡雏三，值钱一。百钱买百鸡，问鸡 翁、母、雏各几何？”意思是公鸡每只5 元、母鸡每只3元、小鸡3只1元，用100元 钱买100只鸡，求公鸡、母鸡、小鸡的只 数。

案例一——百鸡问题令a为公鸡只数，b为母鸡只数，c为小鸡只数。 列出约束方程： a+b+c=100 ( 1) 5a+3b+c/3=100 (2) c%3=0 ( 3) 分析: a、b、c的可能取值范围为0~100,对a、 b、c的所有组合进行测试，满足约束方程的组 合是问题的解。把问题转化为用 n 元钱买 n 只 鸡，则上式变为：a+b+c=n 5a+3b+c/3=n ( 1 ') ( 2 ')

算法1 百鸡问题 1. void chicken_question(int n,int &k,int g[],int m[],int s[]) 2. { 3. int a,b,c; 4. k = 0; 5. for (a=0;a<=n;a++){ 6. for (b=0;b<=n;b++){ 7. for (c=0;c<=n;c++) { 8. if ((a+b+c==n)&&(5*a+3*b+c/3==n)&&(c%3==0)) { 9. g[k] = a; 10. m[k] = b; 11. s[k] = c; 12. k++; 13. } 14. } 15. } 16. } 17. }

算法2 改进的百鸡问题 1. void chicken_problem(int n,int &k,int g[],int m[],int s[]) 2. {int i,j,a,b,c; k = 0; i = n/5; j = n/3; 3. for (a=0;a<=i;a++){ 4. for (b=0;b<=j;b++) { 5. c = n–a–b; 6. if ((5*a+3*b+c/3==n)&&(c%3==0)) { 7. g[k] = a; 8. m[k] = b; 9. s[k] = c; 10. k++; 11. } 12. } 13. } 14. }

算法分析——时间复杂性基本概念

算法分析：对算法所需要的两种计算 机资源——时间和空间进行估算。 问题规模：指输入量的多少。运行算 法所需要的时间T是问题规模n的函数， 记作T(n)。 基本语句：执行次数与整个算法的执 行次数成正比的语句。

时间复杂性分析的关键： 问题规模：输入量的多少； 基本语句：执行次数与整个算法的执行时间 成正比的语句

for (i=1; i<=n; i++) for (j=1; j<=n; j++) x++;

问题规模：n 基本语句：x++

渐进符号——运行时间的上界定义： 若存在两个正的常数c和n0,对于任意n≥n0, 都有T(n)≤cf(n),则称T(n)=O(f(n)) 。 大O符号描述增长率的上限，表示T(n)的 增长最多像f(n)增长的那样快，换言之， 当输入规模为n时，算法消耗时间的最大 值，这个上限的阶越低，结果越有价值。 该算法的运行时间至多是O(f(n)) 。

1. 大O符号定义1.1 若存在两个正的常数c和n0,对于任意 n≥n0,都有T(n)≤c×f(n),则称T(n)=O(f(n))执 行 次 数 c×f(n) T(n)

n0 之 前 的 情况无关 紧要n0

问题规模n

渐进符号——运行时间的上界例如： 当有T(n) ≤100n+n 取n0=5,对任意n≥ n0,有： T(n) ≤100n+n=101n 令c=101, f(n)=n,有： T(n) ≤cn=cf(n) 所以T(n)=O(f(n)) =O(n)

练习： 当有T(n) ≤19/15n2+161/15n+28 则T(n)=O( ?)

渐进符号——运行时间的下界定义 若存在两个正的常数c和n0,对于任意n≥n0, 都有T(n)≥cg(n),则称T(n)=Ω(g(n)) 。 大Ω符号用来描述增长率的下限，也就是 说，当输入规模为n时，算法消耗时间的 最小值。与大O符号对称，这个下限的阶 越高，结果就越有价值。

该算法的运行时间至少是Ω(g(n)) 。

2. 大Ω符号定义1.2 若存在两个正的常数c和n0,对于任意 n≥n0,都有T(n)≥c×g(n),则称T(n)=Ω(g(n))执 行 次 数 T(n)

c×g(n)

n0 之 前 的 情况无关 紧要 n0

问题规模n

渐进符号——运行时间的下界例如： 当有T(n) ≥ n2+n ≥ n2 取n0=1,任意n≥ n0,存在常数c=1, f(n)=n2,使得：T(n) ≥ n2= cf(n) 所以, T(n)=Ω(g(n)) 练习： 当有T(n) ≥19/15n2+161/15n+28 则T(n)=Ω( ?)

渐进符号——运行时间的准确界Θ符号(运行时间的准确界) 定义1.3 若存在三个正的常数c1、c2和 n0,对于任意n≥n0,都有 c1f(n)≥T(n)≥c2×f(n),则称 T(n)=Θ(f(n))。 Θ符号意味着T(n)与f(n)同阶，用来表 示算法的精确阶。

3. Θ 符号定义1.3 若存在三个正的常数c1、c2和n0,对于任意n≥n0 都有c1×f(n)≥T(n)≥c2×f(n),则称T(n)=Θ (f(n))执 行 次 数 c1×f(n) T(n) c2×f(n)

n0 之 前 的 情况无关 紧要 n0 问题规模n

渐进符号——运行时间的准确界例1.1 T(n)=3n-1 【解答】 当n≥1时，3n-1≤3n=O(n) 当n≥1时，3n-1≥3n-n=2n=Ω(n) 当n≥1时，3n≥3n-1≥2n,则3n-1=Θ(n) 例1.2 T(n)=5n2+8n+1 【解答】当n≥1时，5n2+8n+1≤5n2+8n+n=5n2+9n≤5n2 +9n2≤14n2=O(n2) 当n≥1时，5n2+8n+1≥5n2=Ω(n2) 当n≥1时，14n2≥5n2+8n+1≥5n2,则5n2+8n+1=Θ(n2)

算法时间复杂度分析——定理练习： 1. T(n)=4096 2. T(n)=5n+2 3. T(n)=8n2+3n+2 4. T(n)=5×2n+n2 5. T(n)=logn2定理1.1 若T(n)=amnm +am-1nm-1 + … +a1n+a0 (am>0),则有T(n)=O(nm),且T(n)=Ω(nm), 因此，有T(n)=Θ(nm)。

2.1.3 最好、最坏和平均情况例： 在一维整型数组A[n]中顺序查找与给定值k相 等的元素(假设该数组中有且仅有一个元素值为k)

int Find(int A[ ], int n) { for (i=0; i<n; i++) if (A[i]= =k) break; return i; }

结论：如果问题规模相同，时间代价与输 入数据有关，则需要分析最好情况、最坏 情况、平均情况。 最好情况：出现概率较大时分析 最差情况：实时系统 平均情况：已知输入数据是如何分布的， 通常假设等概率分布