1-2算法和复杂度

数据结构与算法For软件学院09级本科生2010-2011秋1.3-1.4算法和算法分析算法和复杂度2/24算法:是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。一个算法通常具有五个重要特性:•有穷性有限步结束•确定性唯一执行路径（无歧义）•可行性可以通过基本运算实现（理论上能够由人用纸和笔完成）•输入零个或多个输入•输出一个或多个输出AlKhwarizmi（阿勒.霍瓦里松）首次提出算法概念，十分强调求解问题有条理的步骤。这是算法亘古不变的核心。1.3.1算法的概念算法和复杂度3/24算法和数据结构是两个不可分割的统一体程序=数据结构+算法数据结构通过算法实现操作算法根据数据结构设计程序注意：不要把算法和计算机程序等同起来，后者只是描述前者的手段之一，我们还可以用流程图、形式语言与自动机甚至自然语言描述一个算法。算法和复杂度4/24算法设计的要求:正确性正确反映需求(通过测试)可读性有助于理解、调试和维护健壮性完备的异常和出错处理高效率与低存储的需求时间、空间的要求算法和复杂度5/241.3.2算法设计算法设计与分析是计算机科学的核心问题。常用的算法设计方法有：•穷举法将问题空间中的所有求解对象一一列举出来，逐一分析、处理，并验证结果是否满足给定的条件。（例：C++switch语句）•回溯法将问题的候选解按某种顺序逐一枚举和检验，来寻找一个满足预定条件的解。当发现当前候选解不可能是解时，就退回到上一步重新选择下一个候选解（回溯）。（例：八皇后、迷宫、深度优先搜索）算法和复杂度6/24•分治法和递归法遇到一个难以直接解决的大问题时，将其分割成一些规模较小的子问题，以便各个击破，分而治之，然后把各个子问题的解合并起来，得出整个问题的解。（例：快速排序、归并排序、二分检索等）•贪心法和动态规划法贪心法的基本思想是从问题的初始状态出发，依据某种贪心标准，通过若干次的贪心选择而得出局部最优解，寄希望于局部的最优解构建最终的全局最优解。（Prim和Kruskal算法、Dijkstra算法）动态规划是一种将问题实例分解为更小的、相似的子问题，并存储子问题的解而避免计算重复的子问题，以解决最优化问题的算法策略。动态规划法和分治法相似？区别？（例：Floyd算法、矩阵连乘积）算法和复杂度7/241.4算法分析算法效率的衡量方法1•事后统计–利用计算机内记时功能。–缺点：必须先运行依据算法编制的程序；所得时间统计量依赖于硬件、软件等环境因素，掩盖算法本身的优劣算法和复杂度8/241.4算法分析•算法效率的衡量方法2•事前分析估计–一个高级语言程序在计算机上运行所消耗的时间取决于：依据的算法选用何种策略问题的规模程序语言编译程序产生机器代码质量机器执行指令速度–时间复杂度和空间复杂度算法和复杂度9/24算法的时间度量•从算法中选取一种对于研究的问题来说是基本操作的原操作，以该基本操作重复执行的次数作为算法执行的时间度量。例，for(j=1；j=n；j++)X=X+1；for(i=1；i=n；i++)(c)for(i=1；i=n；i++)X=X+1；(b)X=X+1；(a)基本操作重复执行的次数分别为1，n，n2算法和复杂度10/24算法复杂度•问题的规模(n)：或大小。如：矩阵的阶数、图的结点个数、被分类序列的正整数个数……•时间复杂度：算法的所需的时间和问题规模的函数。记为T(n)。当n-∞时的时间复杂性，被称之为渐进时间复杂度。•空间复杂度：算法的所需的空间和问题规模的函数。记为S(n)。当n-∞时的时间复杂性，被称之为渐进空间复杂度。算法和复杂度11/24•给定两个正值函数f和g，考虑以下定义：定义1：如果存在正数c和N，对于所有的n≥N，有f(n)≤cg(n),则f(n)=O(g(n))。上述定义表明，如果对于足够大的n，或大于某自然数N的n，存在正数c，使f不大于cg，则f是g的大O符号。大O符号算法和复杂度12/24例如：f(n)=2n2+3n+1=O(n2)在这里，g(n)=n2，c和N的可选值如表所示：表对于函数f(n)=2n2+3n+1=O(n2)，根据大O定义计算得到的c和N的不同值N12345…∞c≥6≥≥≥≥…4339131613225162大O符号算法和复杂度13/24•算法分析中常见的复杂度O(1)O(lgn)O(n)O(nlgn)O(n2)O(n3)O(2n)O(n!)O(nn)常数对数多项式指数复杂度举例算法和复杂度14/24InputSize(n)O(nx)O(n)O(1)O(lgn)O(an)复杂度举例算法的重要性：·计算机不是万能的，并非所有的算法，计算机都能够计算出有用的结果。差的算法不一定有实际意义。举一个例子加以说明。假定时间复杂性函数的时间单位为us。函数n=20n=50n=100n=5001000n.02s.05s.15s.5s1000nlogn.09s.3s.6s4.5s100n2.04s.25s1s25s10n3.02s1s10s21分nlogn.4s1.1小时220天5×108世纪2n/3.0001s0.1s2.7小时5×108世纪2n1s35年3×104世纪3n58分2×109世纪易性算法顽性算法算法和复杂度16/24•在大多数的情况下，我们只对时间复杂度感兴趣，它通常计算程序执行过程中赋值和比较操作的次数。例1：for(i=sum=0;in;i++)Sum+=a[i];赋值2+2n次，渐近复杂度O(n)。确定渐近复杂度算法和复杂度17/24确定渐近复杂度•例2：for(i=0;in;i++){for(j=1,sum=a[0];j=i;j++)sum+=a[j];cout“sumforsubarray0through”i“is”sumendl;})()()()1(31)1321(2312312211nOnOnOnnnnninni算法和复杂度18/24Θ符号•Θ符号–如果存在正数c1,c2及N，对于所有的n≥N，有c1g(n))≤f(n)≤c2g(n),则f(n)=Θ(g(n))。算法和复杂度19/24最好、平均和最坏情况有时，算法中基本操作重复执行的次数随问题的输入不同而不同。例，顺序查找算法Statussearch(inta[]，intn，inte){}for(i=0；i=n-1；++i)if(e==a[i])returnTRUE；比较次数的复杂度是多少？returnFALSE；算法和复杂度20/24最好、平均和最坏情况•最好情况：算法需要的最少步骤•最坏情况：算法需要的最多步骤•平均复杂度：将处理每个输入所执行的步骤数与该输入出现的概率相乘，然后将所有相乘的结果相加。()()avgiiiCpinputstepsinput()()avgiiiCpinputstepsinput算法和复杂度21/24最好、平均和最坏情况有时，算法中基本操作重复执行的次数随问题的输入不同而不同。例，顺序查找算法Statusserch(inta[]，intn，inte){}for(i=0；i=n-1；++i)if(e==a[i])returnTRUE；最好1次比较，最坏n次比较，平均(n+1)/2次比较。returnFALSE；算法和复杂度22/24数据结构的选择•分析问题•在算法设计之前初步设计数据结构•注意可扩展性•比较时空开销的优劣算法和复杂度23/24小结和后续内容•算法特性•算法复杂度分析–渐进复杂度–最好、最坏、平均时间复杂度•后续内容：线性表算法和复杂度24/24作业•预习、复习教材•书面作业：23页4，6，7（下周一交作业）•复习C++相关内容，准备上机