《计算机程序算法分析之算法概述》由会员分享，可在线阅读，更多相关《计算机程序算法分析之算法概述（42页珍藏版）》请在金锄头文库上搜索。
1、计算机算法设计与分析,关于学习与研究,Research (研究）Arch Search Research 算法寻找解的过程search递归反复的寻找最优解research,课程内容,传统算法（硬计算方法）设计与分析： 动态规划，贪心算法，回溯，分枝界限等现代智能算法（软计算方法）设计与分析：计算智能（神经网络，演化计算，群体智能等）,参考书,1.王晓东 计算机算法设计与分析 电子工业出版社 2.郑宗汉等 算法设计与分析 清华大学出版社 3.Thomas H. Cormen et al.Introduction to algorithms (Second Edition) Higher Educ
2、ation Press & The MIT Press 4.王凌 智能优化算法及其应用 清华大学出版社,第1章 算法概述,学习要点: 理解算法的概念。 程序与算法的区别和内在联系。 掌握算法的计算复杂性概念。 掌握算法渐近复杂性的数学表述。,算法(Algorithm),算法是指解决问题的一种方法或一个过程。 算法是若干指令的有穷序列，满足性质： (1)输入：有外部提供的量作为算法的输入。 (2)输出：算法产生至少一个量作为输出。 (3)确定性：组成算法的每条指令是清晰，无歧义的。 (4)有限性：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的。,程序(Program),程序是算法
3、用某种程序设计语言的具体实现。 程序可以不满足算法的性质(4)。 例如操作系统，是一个在无限循环中执行的程序，因而不是一个算法。 操作系统的各种任务可看成是单独的问题，每一个问题由操作系统中的一个子程序通过特定的算法来实现。该子程序得到输出结果后便终止。,问题求解(Problem Solving),理解问题,精确解或近似解 选择数据结构 算法设计策略,设计算法,算法复杂性分析,算法复杂性 = 算法所需要的计算机资源 算法的时间复杂性T(n)； 算法的空间复杂性S(n)。 其中n是问题的规模（输入大小）。,算法的时间复杂性,（1）最坏情况下的时间复杂性Tmax(n) = max T(I) | s
4、ize(I)=n （2）最好情况下的时间复杂性Tmin(n) = min T(I) | size(I)=n （3）平均情况下的时间复杂性Tavg(n) =其中I是问题的规模为n的实例，p(I)是实 例I出现的概率。,算法渐近复杂性,T(n) , as n ; (T(n) - t(n) )/ T(n) 0 ，as n; t(n)是T(n)的渐近性态，为算法的渐近复杂性。 在数学上， t(n)是T(n)的渐近表达式，是T(n)略去低阶项留下的主项。它比T(n) 简单。,渐近分析的记号,在下面的讨论中，对所有n，f(n) 0，g(n) 0。 （1）渐近上界记号O O(g(n) = f(n) | 存在
5、正常数c和n0使得对所有n n0有：0 f(n) cg(n) （2）渐近下界记号 (g(n) = f(n) | 存在正常数c和n0使得对所有n n0有：0 cg(n) f(n) ,（3）非紧上界记号o o(g(n) = f(n) | 对于任何正常数c0，存在正数和n0 0使得对所有n n0有：0 f(n)0，存在正数和n0 0使得对所有n n0有：0 cg(n) 0;p(n) = (nd);f(n) = O(nk) f(n)多项式有界；f(n) = O(1) f(n) c;k d p(n) = O(nk) ; k d p(n) = (nk) ; k d p(n) = o(nk) ; k 0:a
6、0=1;a1=a ;a-1=1/a ;(am)n = amn ; (am)n = (an)m ; aman = am+n ;a1 an为单调递增函数;a1 nb = o(an),ex 1+x; |x| 1 1+x ex 1+x+x2 ;ex = 1+x+ (x2), as x0;,（5）对数函数log n = log2n;lg n = log10n;ln n = logen;logkn = (log n)kl;log log n = log(log n);for a0,b0,c0,|x| 1 for x -1,for any a 0, , logbn = o(na),（6）阶层函数Stirli
7、ngs approximation,算法分析中常见的复杂性函数,小规模数据,中等规模数据,执行时间随n的增长而增长的情况,1.多项式时间复杂度算法 p类问题 2.指数时间复杂度算法 n! 或者2exp(n)NP类问题,算法分析方法,例：顺序搜索算法,template int seqSearch(Type *a, int n, Type k) for(int i=0;in;i+)if (ai=k) return i;return -1; ,（1）Tmax(n) = max T(I) | size(I)=n =O(n) （2）Tmin(n) = min T(I) | size(I)=n =O(1)
8、 （3）在平均情况下，假设：(a) 搜索成功的概率为p ( 0 p 1 )；(b) 在数组的每个位置i ( 0 i n )搜索成功的概率相同，均为 p/n。,算法分析的基本法则,非递归算法： （1）for / while 循环 循环体内计算时间*循环次数； （2）嵌套循环 循环体内计算时间*所有循环次数； （3）顺序语句 各语句计算时间相加； （4）if-else语句 if语句计算时间和else语句计算时间的较大者。,template void insertion_sort(Type *a, int n) Type key; / cost timesfor (int i = 1; i =0 /
9、 c7 n-1 ,在最好情况下，ti=1, for 1 i n;在最坏情况下，ti i+1, for 1 i n;,对于输入数据ai=n-i,i=0,1,n-1，算法insertion_sort 达到其最坏情形。因此，由此可见，Tmax(n)= (n2),最优算法,问题的计算时间下界为(f(n)，则计算时间复杂性为O(f(n)的算法是最优算法。 例如，排序问题的计算时间下界为(nlogn)，计算时间复杂性为O(nlogn)的排序算法是最优算法。 堆排序算法是最优算法。,,递归算法复杂性分析,int factorial(int n)if (n = 0) return 1; return n*factorial(n-1);,
