数据结构与算法绪论.ppt

定义抽象数据类型Triangle??第二节算法和算法分析算法的概念在计算机科学与技术领域几乎无处不在算法的设计与实现往往处于核心地位算法的思想是计算机程序的灵魂算法规定的流程决定着程序的执行步骤算法的基本概念算法（Algorithm）概念的出现与计算机及程序设计无关使用辗转相除法求两个正整数最大公因子的欧几里得（Euclid）算法，早在2300多年前就提出了，这是目前已知的最古老的算法算法定义定义1-1算法是一个由若干确定的（无二义性的）、可执行的步骤组成的肯定能够终止的有序步骤集合算法是描述一个问题的求解过程，它由一系列解决问题的清晰指令构成可以使用自然语言表示可以使用计算机程序设计语言表示可以混合使用自然语言与计算机程序设计语言温度转换将摄氏温标值C转换为华氏温标值F已知计算公式为：F=(9/5)C+32转换的过程可以这样描述输入一个摄氏温标值CC乘以常数9/5（或1.8）前一步的乘积与常数32相加，得到F输出结果F，即转换后的华氏温标值温度转换算法的程序算法特性算法必须满足如下的5个重要特性输入：有0或多个输入值输出：有1或多个输出值有穷性：一个算法必须在执行有穷步骤之后结束确定性：算法的每一个步骤必须是有确切含义的可行性：算法中要做的运算都是相当基本的、能够精确进行的算法的评估和复杂性度量算法必须要正确，所以算法的正确性成为评判算法的首要指标还要评判算法的其他方面，包括它的执行效率时间复杂度空间复杂度时间复杂度?计算机中最重要的资源之一是CPU，显然，花费的时间与处理的数据个数有很大的关系，这个数据个数称为问题规模，也称问题大小。执行算法花费的时间表示为问题规模的一个函数统计一个程序执行期间需要执行的语句总数，并且约定，程序设计语言中一条基本语句的执行时间为1个单位时长时间复杂度一个算法的时间效率可以用问题规模及关键的处理步骤的多少来定义将算法的运行效率表示为问题规模n的一个解析式，对于规模为n的问题，解析式计算的值，应该是算法处理的步骤数将关于n的这个解析式称为增长函数，表示为T(n)对于一个具体的算法，其增长函数是一个近似的表达式查找给定数组中的最大值?当数组中元素个数为10n时，执行的语句个数最多为10n+1，即问题规模扩大10倍，所花费的时间也增大约10倍程序段sum=0; //赋初值for(i=0;in;i++) //对每个n for(j=0;jn;j++) //对每个n sum++; //累加returnsum;主体是一个二重循环，外层循环每执行一次，内层循环都执行n次，所以sum++的总执行次数为n2，语句执行的总数是n2+2，即增长函数T(n)=n2+2当问题规模扩大10倍时，所花的时间需要增加约100倍渐近时间复杂度考查增长函数时，只关心增长函数表达式中的主项，并且不再考虑主项的系数表达式的主项使用记号O来表示例1.4中增长函数表示为O(n)例1.5中增长函数表示为O(n2)这称为渐近时间复杂度，也称为算法的阶定义定义1-2称（复杂度）函数T(n)是O(f(n))的，即T(n)=O(f(n))，如果存在常数c0与n0，当nn0时有T(n)≤cf(n)T1(n)=(n+1)/2=O(n2)T2(n)=3n2+4n+5=O(n3)当然T1(n)=O(n2)，T2(n)=O(n3)也是对的，但一般取最低阶表示T(n)=O(f(n))说明T(n)的阶不大于f(n)的阶定义定义1-3称（复杂度）函数T(n)是Ω(f(n))的，即T(n)=Ω(f(n))，如果存在常数c0与n0，当nn0时有T(n)≥cf(n)T1(n)=(n+1)/2=Ω(n)T2(n)=3n2+4n+5=Ω(n2)当然T1(n)=Ω(1)，T2(n)=Ω(n)，T2(n)=Ω(nlogn)也都是对的，同样地，取它们之中的最高阶T(n)=Ω(f(n))说明T(n)的阶不小于f(n)的阶大O表示法和大Ω表示法使我们能够描述某一算法的上限（如果能找到某一类输入下开销最大的函数）和下限（如果能找到某一类输入下开销最小的函数）当上、下限相等时，可用Θ表示法。如果一种算法既是O(f(n))，又是Ω(f(n))，则称其是Θ(f(n))的若增长函数不随算法问题规模变化，则增长函数称为O(1)阶，或称常数复杂度与问题规模成正比的问题求解算法称为线性操作许多算法具有log2n对数复杂度其他的算法有n的某次幂的多项式复杂度，如O(n2)或O(n3)更坏的算法是指数复杂度，n是指数，如O(2n)一些增长函数的渐近时间复杂增长函数阶时间复杂度T(n)=17O(