数据结构2第1章幻灯片.pptVIP

算法（algorithm）—解决某一特定问题的具体步骤的描述，是指令的有限序列。 算法需要用一种语言来描述，同时，算法可有各种描述方法以满足不同的需求。例如，一个需要在计算机上运行的程序（程序也是算法）必须是按照语法用机器语言或汇编语言或高级程序语言编写，而一个为了便于人们阅读和交流的算法可以用伪码语言或框图等其他形式来描述。 算法特性 输入 有0个或多个输入 输出 有一个或多个输出(处理结果) 确定性 每步定义都是确切、无歧义的 有穷性 算法应在执行有穷步后结束 有效性 每一条运算应足够基本 1.3算法和算法的时间复杂度 算法的评价 衡量算法优劣的标准 正确性(correctness) 可读性(readability) 健壮性(robustness) 效率与低存储量 算法效率---用依据该算法编制的程序在计算机上执行  所消耗的时间来度量 1.事后统计——利用计算机内记时功能，不同算法的程序可以用一组或多组相同的统计数据区分 缺点：?必须先运行依据算法编制的程序 ?所得时间统计量依赖于硬件、软件等环境因素，掩盖算法本身的优劣 2.事前分析估计——一个高级语言程序在计算机上运行所消耗的时间取决于： ?依据的算法选用何种策略 ?问题的规模 ?程序语言 ?编译程序产生机器代码质量 ?机器执行指令速度 同一个算法用不同的语言、不同的编译程序、在不同的计算机上运行，效率均不同，———所以使用绝对时间单位衡量算法效率不合适 分析评价算法时应考虑的因素： 1、正确性 在给定有效的输入数据后，算法经过有穷时间的计算能给出正确的答案。 2、复杂度 时间复杂度 3、简单性 易于理解，易于编程 4、最优性 算法A是最优的是指：在给定问题的所有算法中，A执行的进步运算次数最少 5、可读性 要求算法易于理解，便于分析 6、可修改可扩展性 如果问题P 的一个算法是A，为了解答一个与P类似的问题，希望对A稍做改动就可正确运行，如算法A满足这一点，则说A的可修改性好。 与算法效率有关的因素 程序设计语言 编译的代码质量 机器执行指令的速度 问题的规模 一个算法所耗费的时间，应该是该算法中每条语句的执行时间之和，而每条语句的执行时间又是该语句的执行次数（频度）与该语句执行一次所需时间的乘积。 我们假定，每条语句一次执行的时间都是相同的，为单位时间。这样我们对时间的分析就可以独立于软硬件系统。 时间复杂度 我们将算法求解问题的输入量称为问题的规模，用一个整数来表示，一个算法的时间复杂度是该算法的时间耗费，一般地说，时间复杂度是问题规模的函数 － T( n )。 当问题的规模n 趋于无穷大时，把时间复杂度T( n )的数量级（阶）称为算法的渐进时间复杂度（有时简称为时间复杂度）。 严格的数学定义为：若T( n ) 和 f( n ) 是定义在正整数集合上的两个函数，当存在两个正的乘数C和n0时，使得对所有的 成立，则 都有 这时称T( n )的时间复杂度为f( n )数量级。 算法分析 1、假定每条语句的执行时间为单位时间。算法的时间复杂度是该算法中所有语句的执行频度之和。 例：求两个方阵的乘积 C＝A*B ＃define n 自然数 MATRIXMLT(float A[n][n],float B[n][n],float C[n][n]) { int i,j,k; for(i=0;in;i++) //n+1 for(j=0;jn;j++) //n(n+1) { C[i][j]=0; //n*n for( k=0;kn;k++) //n*n*(n+1) C[i][j]=A[i][k]*B[k][j] //n*n*n } } 2、一般情况下，对步进循环语句只考虑循环体语句的执行次数，而忽略该语句中部长加一、终值判别、循环转移等成份。因此，当有若干个循环语句时，算法的时间复杂度是由嵌套层数最多的循环语句中最内层语句的频度所决定的。 例： x=0;y=0; for (k=1;k=n;k++) x++; for (i=1;i=n;i++) for (j=1;j=n;j++) //n*n