算法设计与分析第1章算法引论

《算法设计与分析第1章算法引论》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第1章算法引论主要内容一、算法及其特性  二、算法的时间空间复杂度  三、算法分析(AlgorithmAnalysis)    1.分析算法时间复杂度的基本步骤2.算法时间复杂度的有关概念3.分析、求解算法复杂度的方法四、迭代法、递归1.1算法1.2算法描述1.3算法分析的基础1.4基本数据结构1.5迭代法1.6递归和消除递归学习要求掌握算法复杂度的基本概念熟悉算法复杂度分析的基本方法1.1算法一、算法(algorighm)算法就是一组有穷的规则，它们规定了解决某一特定类型问题的一系列运算Gcd(inta,intb)1ifa

2、>05do{ab;6bn;7a%b;}8returnb;1.1算法二、算法的特点1.有穷性2.确定性3.输入4.输出5.能行性程序是算法用某种程序设计语言的具体实现。程序可以不满足算法的性质(1)。例如操作系统，是一个在无限循环中执行的程序，因而不是一个算法。操作系统的各种任务可看成是单独的问题，每一个问题由操作系统中的一个子程序通过特定的算法来实现。该子程序得到输出结果后便终止。1.2算法的描述自然语言流程图PAD图盒图伪代码计算机程序设计语言1.2.1算法描述约定基本数据类型:vartypevar;赋值语句：逻辑运算：and,or,not关系运

3、算<,<=,=,<>,>=,>等数组描述：vartypearrayname[n]三种基本的控制结构1.顺序结构2.选择结构3.循环结构动态空间申请函数malloc(size)模块描述其他细节说明1.2.1一个简单问题的求解过程1.问题分析：对问题进行准确的理解和描述从而确认问题以及问题的基本运算，并明确求解问题2.算法分析：根据确定的问题，找出问题的解决方法或数学模型，对处理功能求解，并用算法语言进行描述3.算法设计：对确定的算法，选择数据结构对分析得到的算法进行设计4.算法实现：利用程序设计和软件开发方法通过程序编辑、编译、运行于调试实现算法，对问题进行计算机求解。1.3算法分析的基础1

4、.3.1算法分析的评估体系算法分析主要分析算法在运行时占用的计算机资源是多少，既算法运行时的时间和空间效率好的算法在完成功能的前提先占用空间少且执行时间短对算法的分析和评价，一般应考虑正确性、可维护性、时间效率及占用存储空间等诸多因素。其中评价算法的三条主要标准是：1、算法实现所耗费的时间2、算法实现所耗费的存储空间3、算法应易于理解、易于编码、易于调试。算法复杂性=算法所需要的计算机资源算法的时间复杂性T(n)；算法的空间复杂性S(n)。其中n是问题的规模（输入大小）。1.3.2算法的时间复杂度一、影响算法执行时间的因素1.问题中数据存储的数据结构2.算法中采用的数学模型3.算法设计的策

5、略4.问题规模5.实现算法的程序执行语言6.编译算法产生的机器代码的质量7.计算机执行指令的速度分析算法的时间复杂度常用的两种方法：事后测试(PosteriorTest)方法事前分析(PrioriAnalysis)方法二、时间复杂度定义1-1在问题规模为n的算法中，如果存在两个正常数C和n0，对任意n≥n0,都有

6、g(n)

7、≤C

8、f(n)

9、则记作

10、g(n)

11、=O(f(n))。其中，O为数量级，即阶数。因此，但说一个算法具有O(g(n))的计算时间时，指的如果此算法用n值不变的同一类数据在某台机器上运行时，所用时间总是小于

12、f(n)

13、的常数倍。所以f(n)是计算时间g(n)的一个上界函数，g

14、(n)的数量级为f(n).定义1-2算法中基本操作重复执行的次数是问题规模n的某个函数f(n)，算法的时间度量记作T(n)=O(f(n))随着问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐进时间复杂度，简称时间复杂度。三、时间复杂度估算假设在程序中有语句xx+y,这条语句的时间总量=该语句执行的次数×每执行一次该语句所需要的时间；例1for1tondo{for1jtondo{xx+1;}}语句的最大频度为n2,所以其时间复杂度可表示为O(n2).算法中对所研究的问题最重要的操作作为原操作，已原操作在算法中重复执行的次数作为算法运行时间的衡量准则。例2ab

15、cxx+yfor1itonfor1itondoxx+ydo{for1jtondo{xx+y;}}1nn2O(1)O(n)O(n2)定理1-1若A(n)=amnm+…+a1n+a0是一个m次多项式，则A(n)=O(nm)证明：取n0=1,当n>n0时有

16、A(n)

17、≤

18、am

19、nm+

20、am-1

21、nm-1+…+

22、a1

23、n+

24、a0

25、≤(

26、am

27、+

28、am-1

29、1/n+…+

30、a0

31、1/nm)nm≤(

32、am

33、+

34、am-1

35、+