武汉理工大学期末考试算法试卷复习课_52178.pptVIP

算法设计与分析 复习课 考试题型 填空题 15分 判断题 10分 简答题 25分 计算题 20分 算法设计题 30分 第一章 主要内容 算法的概念 什么是算法？ 算法的特征？ 程序与算法的区别？ 算法分析 算法的评价优劣 算法的时间复杂度分析 频率计数 计算时间的渐近表示：上界函数、下界函数、平均界函数 第一章 主要内容 什么是算法？ 它是一组有穷规则的集合，它规定了解决某一特定类型问题的一系列运算。 算法的5个特征 确定性;能行性;输入;输出;有穷性。 第一章 主要内容 算法与程序的区别 程序： 与某种语言有关，能直接在机器上运行。 只满足确定性、能行性、输入、输出四个特性但不一定能终止的一组规则。 算法： 与特定的语言无关，可用任何语言实现 ，甚至可以用自然语言实现。 算法是“可以终止的计算过程”。 算法的时效性：只能把在相当有穷步内终止的算法投入到计算机上运行。 第一章 主要内容 算法优劣的评价标准 时间复杂度：最好情况时间复杂度、最坏情况时间复杂度、平均情况时间复杂度 空间复杂度 算法的时间复杂度概念 频率计数：一条语句或一种运算在算法（或程序）体中的执行次数。 计算时间的渐近表示 上界函数 下界函数 平均界函数 第一章 主要内容 计算时间的渐近表示：假设算法的计算时间为f(n)，数量级限界函数为g(n) n是输入或输出规模的某种测度。 f(n)表示算法“实际”执行时间—与机器及语言有关。 g(n)是形式简单的函数，如nm，logn，2n，n!等。是事前分析中通过对计算时间或频率计数统计分析所得的、与机器及语言无关的函数。 第一章 主要内容 上界函数 定义1 如果存在两个正常数c和n0，对于所有的n≥n0，有 |f(n)| ≤ c|g(n)| 则记作f(n) = Ο(g(n)) 含义： 如果算法用n值不变的同一类数据在某台机器上运行时，所用的时间总是小于|g(n)|的一个常数倍。所以g(n)是计算时间f(n)的一个上界函数。 f(n) 数量级是g(n)。 试图求出最小的g(n)，使得f(n) = Ο(g(n))。 第一章 主要内容 下界函数 定义2 如果存在两个正常数c和n0，对于所有的n≥n0，有 |f(n)| ≥ c|g(n)| 则记作f(n) = Ω(g(n)) 含义： 如果算法用n值不变的同一类数据在某台机器上运行时，所用的时间总是不小于|g(n)|的一个常数倍。所以g(n)是计算时间f(n)的一个下界函数。 试图求出“最大”的g(n)，使得f(n) = Ω(g(n))。 第一章 主要内容 平均界函数 定义3 如果存在正常数c1，c2和n0，对于所有的 n≥n0，有 c1|g(n)| ≤|f(n)| ≤ c2|g(n)| 则记作 含义：算法在最好和最坏情况下的计算时间就一个常数因子范围内而言是相同的。有f(n)=Ω(g(n))，又有f(n)=Ο(g(n)) 第一章 主要内容 给定f(n)= amnm+…+a1n+a0，求f(n)的上界函数、下界函数、平均界函数 给定f(n)=logn2,求f(n)的上界函数、下界函数、平均界函数 第二章主要内容 分治法的基本思想、求解流程、适用条件 二分检索算法，时间复杂度分析 找最大最小值算法，时间复杂度分析 第二章主要内容 分治法的基本思想 在问题输入规模很大时，无法直接求解，则将整个问题分成若干个小问题后分而治之。 分治法的求解流程 分解：将原问题分析为若干个相互独立，与原问题形式相同的子问题。 求解：若子问题易解，则直接求解；否则继续分解，直至子问题易解。 合并：合并已求解的子问题的解，得到原问题的解。 分治法的适用条件 原问题可以分解为若干个子问题，子问题与原问题结构相似，由子问题的解能够快速求出原问题的解 第二章主要内容 二分检索算法：递归形式的算法 int binarySearch( a, low, high, e) int mid ; if(low high) { mid = (low + high)/2; if(a[mid] == e) return mid+1; else if (a[mid] e) binarySearch(a,mid+1, high, e); else binarySearch(a,low, mid-1, e); } return -1; 第二章主要内容 二分检索算法时间复杂度分析 成功/不成功检索的最好情况 成功/不