第1章_ 算法引论2014冯.pdf

第第1 1章章 算法绪论算法绪论 AlgorithmAlgorithmI Introductionntroduction 算法设计与分析算法设计与分析算法设计与分析算法设计与分析 本科生课程本科生课程本科生课程本科生课程 Design and Analysis of AlgorithmDesign and Analysis of Algorithm 冯思玲冯思玲 海南大学信息科学技术学院海南大学信息科学技术学院 College of Information Science and College of Information Science and Technology Hainan UniversityTechnology Hainan University lily85161 lily85161 第第1 1章章算法引论 算法引论 3 3学时 学时 第第第第2 2章章章章 常用数学工具常用数学工具 常用数学工具常用数学工具 3 3学时学时 学时学时 第第3 3章章 NPNP完全性理论完全性理论 3 3学时学时 学时学时 第第4 4章章 蛮力法蛮力法 3 3学时学时 学时学时 第第5 5章章 递归与分治策略递归与分治策略 3 3学时学时 学时学时 第第6 6章章 减冶法 减冶法 3 3学时 学时 课程目录课程目录 2014 9 62014 9 6Algorithm IntroductionAlgorithm Introduction2 2 第第6 6章章 减冶法 减冶法 3 3学时 学时 第第7 7章章 动态规划 动态规划 6 6学时 学时 第第8 8章章 贪心算法贪心算法 6 6 学时学时 学时学时 第第9 9章章 回溯法回溯法 6 6学时学时 学时学时 第第1010章章 分支限界法分支限界法 3 3学时学时 学时学时 第第1111章章 概率算法概率算法 3 3学时学时 学时学时 第第1212章章 近似算法近似算法 3 3学时学时 学时学时 总复习总复习总复习总复习 3 3学时学时 学时学时 第第1 1章章 算法绪论算法绪论 算法理论的两大论题 1 算法设计 2 算法分析 本章主要知识点 2014 9 62014 9 6Algorithm IntroductionAlgorithm Introduction3 3 1 11 1算法的基本概念算法的基本概念 1 21 2算法分析算法分析 1 3 1 3 实验一实验一 本章主要知识点 1 11 1算法的基本概念算法的基本概念 为什么要学习算法为什么要学习算法 算法及其重要特性算法及其重要特性 算法的描述方法算法的描述方法 2014 9 62014 9 6Algorithm IntroductionAlgorithm Introduction4 4 算法设计的一般过程算法设计的一般过程 重要的问题类型重要的问题类型 为什么要学习算法为什么要学习算法 理由理由1 算法算法 程序的灵魂程序的灵魂 问题的求解过程问题的求解过程 分析问题分析问题 设计算法设计算法 编写程序编写程序 整理结果整理结果 程序设计研究的四个层次程序设计研究的四个层次 算法算法 方法学方法学 语言语言 工具工具 2014 9 62014 9 6Algorithm IntroductionAlgorithm Introduction5 5 算法算法 方法学方法学 语言语言 工具工具 例例 Hash算法算法 50年代年代 快速排序算法快速排序算法 60年代年代 理由理由2 提高分析问题的能力提高分析问题的能力 算法的形式化算法的形式化 思维的逻辑性思维的逻辑性 条理性条理性 至今仍被广泛使用至今仍被广泛使用 1 11 1算法的基本概念算法的基本概念 为什么要学习算法为什么要学习算法 算法及其重要特性算法及其重要特性 算法的描述方法算法的描述方法 2014 9 62014 9 6Algorithm IntroductionAlgorithm Introduction6 6 算法设计的一般过程算法设计的一般过程 重要的问题类型重要的问题类型 算法及其重要特性算法及其重要特性 例 欧几里德定理例 欧几里德定理 gcd a b gcd b b mod a b为最大公约数为最大公约数当当 b mod a 0时时 求解最大公约数的算法 求解最大公约数的算法 2014 9 62014 9 6Algorithm IntroductionAlgorithm Introduction7 7 例如例如1 1 gcd 55 22 gcd 22 55 mod 22 gcd 55 22 gcd 22 55 mod 22 gcd 22 11 gcd 11 22 mod 11 gcd 22 11 gcd 11 22 mod 11 gcd 11 0 11 gcd 11 0 11 算法及其重要特性算法及其重要特性 例如例如2 2 gcd 18 12 gcd 12 18 mod 12 gcd 18 12 gcd 12 18 mod 12 gcd 12 6 gcd 6 12 mod 6 gcd 12 6 gcd 6 12 mod 6 gcd 6 0 6 gcd 6 0 6 2014 9 62014 9 6Algorithm IntroductionAlgorithm Introduction8 8 例如例如3 3 gcd 11 10 gcd 10 11 mod 10 gcd 11 10 gcd 10 11 mod 10 gcd 10 1 gcd 1 10 mod 1 gcd 10 1 gcd 1 10 mod 1 gcd 1 0 1 gcd 1 0 1 算法及其重要特性算法及其重要特性 算法算法算法算法实现实现 实现实现 欧几里德算法欧几里德算法 输入输入 输入输入 正整数正整数m nm n 输出输出 输出输出 m nm n的最大公因子的最大公因子 1 int euclid int m int n 1 int euclid int m int n 2 2 3 int r 3 int r 2014 9 62014 9 6Algorithm IntroductionAlgorithm Introduction9 9 3 int r 3 int r 4 do 4 do 5 r m n 5 r m n 6 m n 6 m n 7 n r 7 n r 8 while r 8 while r 9 return m 9 return m 10 10 算法及其重要特性算法及其重要特性 算法算法 Algorithm 定义定义1 1 算法是解某一特定问题的一组有穷规则的集合算法是解某一特定问题的一组有穷规则的集合 即即 对特定问题求解步骤的一种描述对特定问题求解步骤的一种描述 是指令的有限序是指令的有限序 列列 有以下五大特性有以下五大特性 输输入入 一个算法有零个或多个外部量作为算法的输入一个算法有零个或多个外部量作为算法的输入 2014 9 62014 9 6Algorithm IntroductionAlgorithm Introduction1010 输输入入 一个算法有零个或多个外部量作为算法的输入一个算法有零个或多个外部量作为算法的输入 输输出出 一个算法会产生至少一个量作为输出一个算法会产生至少一个量作为输出 有穷性有穷性 一个算法必须总是在执行有穷步之后结束一个算法必须总是在执行有穷步之后结束 且每一步且每一步 都在有穷时间内完成都在有穷时间内完成 确定性确定性 算法中的每一条指令必须有确切的含义算法中的每一条指令必须有确切的含义 对于相同的对于相同的 输入只能得到相同的输出输入只能得到相同的输出 可行性可行性 算法描述的操作可以通过已经实现的基本操作执行有算法描述的操作可以通过已经实现的基本操作执行有 限次来实现限次来实现 算法及其重要特性算法及其重要特性 程序 是算法用某种程序设计语言的具体实现 程序 可以不满足算法的性质 3 即有穷性有穷性 例例 欧几里德算法欧几里德算法 辗转相除法求两个辗转相除法求两个 自然数自然数m和和n的最大公约数的最大公约数 2014 9 62014 9 6Algorithm IntroductionAlgorithm Introduction1111 自然数自然数m和和n的最大公约数的最大公约数 欧几里德算法欧几里德算法 m n M r 0 1 11 1算法的基本概念算法的基本概念 为什么要学习算法为什么要学习算法 算法及其重要特性算法及其重要特性 算法的描述方法算法的描述方法 2014 9 62014 9 6Algorithm IntroductionAlgorithm Introduction1212 算法设计的一般过程算法设计的一般过程 重要的问题类型重要的问题类型 自然语言 优点 容易理解 缺点 冗长 二义性 算法的描述方法算法的描述方法 2014 9 62014 9 6Algorithm IntroductionAlgorithm Introduction1313 缺点 冗长 二义性 使用方法 粗线条描述算法思想粗线条描述算法思想 注意事项 避免写成自然段 输入输入m 和和n 求求m除以除以n的余数的余数r 欧几里德算法欧几里德算法 自然语言描述自然语言描述 算法的描述方法算法的描述方法 2014 9 62014 9 6Algorithm IntroductionAlgorithm Introduction1414 若若r等于等于0 0 则则n为最大公约数为最大公约数 算法结束算法结束 否则执行第否则执行第 步步 将将n的值放在的值放在m中中 将将r的值放在的值放在n中中 重新执行第重新执行第 步步 流程图流程图 优点优点 流程直观流程直观 缺点缺点 缺少严密性缺少严密性 灵活性灵活性 算法的描述方法算法的描述方法 2014 9 62014 9 6Algorithm IntroductionAlgorithm Introduction1515 缺点缺点 缺少严密性缺少严密性 灵活性灵活性 使用方法使用方法 描述简单算法描述简单算法 注意事项注意事项 注意抽象层次注意抽象层次 开始 输入m和n r m n Y 欧欧 几几 里里 德德 算算 算法的描述方法算法的描述方法 2014 9 62014 9 6Algorithm IntroductionAlgorithm Introduction1616 N r 0 m n n r 输出m 结束 Y 算算 法法 流流 程程 图图 程序设计语言程序设计语言 优点优点 能由计算机执行能由计算机执行 缺点缺点 抽象性差抽象性差 对语言要求高对语言要求高 算法的描述方法算法的描述方法 2014 9 62014 9 6Algorithm IntroductionAlgorithm Introduction1717 缺点缺点 抽象性差抽象性差 对语言要求高对语言要求高 使用方法使用方法 算法需要验证算法需要验证 注意事项注意事项 将算法写成子函数将算法写成子函数 include int CommonFactor int m int n int r m n while r 0 欧几里德算法 算法的描述方法算法的描述方法 2014 9 62014 9 6Algorithm IntroductionAlgorithm Introduction1818 m n n r r m n return m void main cout CommonFactor 63 54 endl 欧几里德算法 伪代码伪代码 算法语言算法语言 伪代码伪代码 Pseudocode 介于自然语言和介于自然语言和 程序设计语言之间的方法程序设计语言之间的方法 它采用某一程序它采用某一程序 设计语言的基本语法设计语言的基本语法 操作指令操作指令 再结合自再结合自 算法的描述方法算法的描述方法 2014 9 62014 9 6Algorithm IntroductionAlgorithm Introduction1919 设计语言的基本语法设计语言的基本语法 操作指令操作指令 再结合自再结合自 然语言来设计然语言来设计 优点优点 表达能力强表达能力强 抽象性强抽象性强 容易理解容易理解 使用方法使用方法 7 2 欧几里德算法欧几里德算法 C 语法的伪代码表达语法的伪代码表达 算法的描述方法算法的描述方法 1 r m n 2 循环直到 r 等于0 2014 9 62014 9 6Algorithm IntroductionAlgorithm Introduction2020 2 1 m n 2 2 n r 2 3 r m n 3 输出 n 1 11 1算法的基本概念算法的基本概念 为什么要学习算法为什么要学习算法 算法及其重要特性算法及其重要特性 算法的描述方法算法的描述方法 2014 9 62014 9 6Algorithm IntroductionAlgorithm Introduction2121 算法设计的一般过程算法设计的一般过程 重要的问题类型重要的问题类型 1 1 理解问题理解问题 2 2 预测所有可能的输入预测所有可能的输入 确定了求解问题的一个实例确定了求解问题的一个实例 3 3 在精确解和近似解间做选择在精确解和近似解间做选择 4 4 确定适当的数据结构确定适当的数据结构 算法设计的一般过程算法设计的一般过程 2014 9 62014 9 6Algorithm IntroductionAlgorithm Introduction2222 5 5 算法设计技术算法设计技术 算法设计算法设计 6 6 描述算法描述算法 7 7 跟踪算法跟踪算法 8 8 分析算法的效率分析算法的效率 算法分析算法分析 9 9 根据算法编写代码根据算法编写代码 实现算法实现算法 1 11 1算法的基本概念算法的基本概念 为什么要学习算法为什么要学习算法 算法及其重要特性算法及其重要特性 算法的描述方法算法的描述方法 2014 9 62014 9 6Algorithm IntroductionAlgorithm Introduction2323 算法设计的一般过程算法设计的一般过程 重要的问题类型重要的问题类型 重要的问题类型重要的问题类型 1 查找问题查找问题 2 排序问题排序问题 3 图问题图问题 2014 9 62014 9 6Algorithm IntroductionAlgorithm Introduction2424 3 图问题图问题 4 组合问题组合问题 5 几何问题几何问题 第第1 1章章 算法绪论算法绪论 本章主要知识点本章主要知识点 算法理论的两大论题 1 算法设计 2 算法分析 2014 9 62014 9 6Algorithm IntroductionAlgorithm Introduction2525 本章主要知识点本章主要知识点 1 11 1算法的基本概念算法的基本概念 1 21 2算法分析算法分析 1 3 1 3 实验一实验一 1 2 算法分析算法分析 算法分析概念算法分析概念 渐进符号渐进符号 最好最好 最坏最坏 与与 平均情况平均情况 非递归算法的分析非递归算法的分析 2014 9 62014 9 6Algorithm IntroductionAlgorithm Introduction2626 非递归算法的分析非递归算法的分析 递归算法的分析递归算法的分析 算法分析概念算法分析概念 算法分析算法分析 Algorithm Analysis 算法复杂性算法复杂性 Algorithm Complexity 算法复杂性的高低体现在运行该算法所需计算机资源的多少算法复杂性的高低体现在运行该算法所需计算机资源的多少 计算机中最重要的两种资源是计算机中最重要的两种资源是时间时间和和空间资源空间资源 更确切地说更确切地说 2014 9 62014 9 6Algorithm IntroductionAlgorithm Introduction2727 计算机中最重要的两种资源是计算机中最重要的两种资源是时间时间和和空间资源空间资源 更确切地说更确切地说 算法的复杂性是算法运行所需要的计算机资源的量算法的复杂性是算法运行所需要的计算机资源的量 需要的需要的 时间资源的量称为时间复杂性时间资源的量称为时间复杂性 需要的空间资源的量称为空需要的空间资源的量称为空 间复杂性间复杂性 如下如下 时间复杂性时间复杂性 Time Complexity 空间复杂性空间复杂性 Space Complexity 算法分析概念算法分析概念 算法复杂性的表达算法复杂性的表达 这个量依赖于算法要解问题的规模这个量依赖于算法要解问题的规模N 算法的输入算法的输入I及算法及算法A 本身本身 即这个算法复杂性即这个算法复杂性C可表达为如下的三元函数可表达为如下的三元函数 C F N I A 如果分开讨论时间与空间复杂性如果分开讨论时间与空间复杂性 则可表达如下则可表达如下 T TN I Aor T TN I 2014 9 62014 9 6Algorithm IntroductionAlgorithm Introduction2828 T T N I A or T T N I S S N I A or S S N I 算法分析的目的算法分析的目的 设计算法设计算法 设计出复杂性尽可能低的算法设计出复杂性尽可能低的算法 选择算法的准则选择算法的准则 在多种算法中选择其中复杂性最低者在多种算法中选择其中复杂性最低者 算法分析概念算法分析概念 复杂性的计算复杂性的计算 根据根据T N I 的概念的概念 它应该是算法在一台抽象的计算机它应该是算法在一台抽象的计算机 上运行所需要的时间总和上运行所需要的时间总和 即可表达如下即可表达如下 INetINT 2014 9 62014 9 6Algorithm IntroductionAlgorithm Introduction2929 INetINT ii kiti 2 1 其中其中 是与是与N与与I无关的常数无关的常数 是为运算计算机是为运算计算机 所提供的所提供的k种元运算操作种元运算操作O1 O2 Ok所需的时间所需的时间 是经统计用到元运算是经统计用到元运算Oi的次数的次数 kiINe i 2 1 算法设计的例子算法设计的例子 穷举法穷举法 穷举法穷举法 是从有限集合中是从有限集合中 逐一列举集合的所有元素逐一列举集合的所有元素 对每一个元素逐一判断和处理对每一个元素逐一判断和处理 从而找出问题的解从而找出问题的解 例例例例 百鸡问题 百鸡问题 鸡翁一 值钱五 鸡母一 值钱三 鸡雏三 值钱鸡翁一 值钱五 鸡母一 值钱三 鸡雏三 值钱 算法分析概念算法分析概念 2014 9 62014 9 6Algorithm IntroductionAlgorithm Introduction3030 鸡翁一 值钱五 鸡母一 值钱三 鸡雏三 值钱鸡翁一 值钱五 鸡母一 值钱三 鸡雏三 值钱 一 百钱买百鸡 问鸡翁 母 雏各几何 一 百钱买百鸡 问鸡翁 母 雏各几何 a a 公鸡只数 公鸡只数 b b 母鸡只数 母鸡只数 c c 小鸡只数 小鸡只数 约束方程约束方程 约束方程约束方程 a b c 100 1 a b c 100 1 5a 3b c 3 100 2 5a 3b c 3 100 2 C 3 0 3 C 3 0 3 解法解法1 1 a a b b c c的可能取值范围 的可能取值范围 0 1000 100 对在此范围内的 对在此范围内的 a a b b c c的所有组合进行测试 凡是满足上述三个约束的所有组合进行测试 凡是满足上述三个约束 方程的组合 都是问题的解 方程的组合 都是问题的解 把问题转化为用把问题转化为用n n元钱买元钱买n n只鸡 只鸡 n n为任意正整数 则方为任意正整数 则方 程 程 1 1 与 与 2 2 转换为 转换为 算法分析概念算法分析概念 2014 9 62014 9 6Algorithm IntroductionAlgorithm Introduction3131 输入输入 输入输入 所购买的三种鸡的总数目所购买的三种鸡的总数目n n 输出输出 输出输出 满足问题的解的数目满足问题的解的数目k k 公鸡公鸡 母鸡母鸡 小鸡的只数小鸡的只数 g m s g m s a b c n 4 a b c n 4 5a 3b c 3 n 5 5a 3b c 3 n 5 1 1 void chicken question int n int 3 int a b c 4 k 0 4 k 0 5 for a 0 a n a 5 for a 0 a n a 6 for b 0 b n b 6 for b 0 b n b 7 for c 0 c n c 7 for c 0 c n c 8 8 if a b c n 9 g k a 10 m k b 10 m k b 11 s k c 11 s k c 12 k 12 k 13 13 14 14 17 17 执行时间 执行时间 外循环 外循环 n 1 n 1 次 次 中间循环 中间循环 n 1 n 1 n 1 n 1 次 次 内循环 内循环 n 1 n 1 n 1 n 1 n 1 n 1 次 次 当时当时n 100n 100 内循环的循环体执行次数大于 内循环的循环体执行次数大于100100 算法分析概念算法分析概念 2014 9 62014 9 6Algorithm IntroductionAlgorithm Introduction3333 当时当时n 100n 100 内循环的循环体执行次数大于 内循环的循环体执行次数大于100100 万次 万次 算法算法2 2 改进的百鸡问题 改进的百鸡问题 公鸡只数公鸡只数 公鸡只数公鸡只数 0 n 5 0 n 5 母鸡只数母鸡只数 母鸡只数母鸡只数 0 n 3 0 n 3 小鸡只数小鸡只数 小鸡只数小鸡只数 c nc n a a b b 算法分析概念算法分析概念 2014 9 62014 9 6Algorithm IntroductionAlgorithm Introduction3434 输入输入 输入输入 所购买的三种鸡的总数目所购买的三种鸡的总数目n n 输出输出 输出输出 满足问题的解的数目满足问题的解的数目k k 公鸡公鸡 母鸡母鸡 小鸡的小鸡的 只数只数g m s g m s 1 1 void chicken problem int n int i j a b c 4 k 0 4 k 0 5 i n 5 5 i n 5 6 j n 3 6 j n 3 7 for a 0 a i a 7 for a 0 a i a 8 for b 0 b j b 8 for b 0 b j b 算法分析概念算法分析概念 2014 9 62014 9 6Algorithm IntroductionAlgorithm Introduction3535 8 for b 0 b j b 8 for b 0 b j b 9 c n 9 c n a a b b 10 10 if 5 a 3 b c 3 n 11 g k a 12 m k b 12 m k b 13 s k c 13 s k c 14 k 14 k 15 15 18 18 执行时间 执行时间 外循环 外循环 n 5 1n 5 1 内循环 内循环 n 5 1 n 3 1 n 5 1 n 3 1 当时当时n 100n 100 内循环的循环体的执行次数为 内循环的循环体的执行次数为 算法分析概念算法分析概念 2014 9 62014 9 6Algorithm IntroductionAlgorithm Introduction3636 次次 21 34 714 21 34 714次 次 对某类特定问题 在规模较小的情况下 穷举法往往是一对某类特定问题 在规模较小的情况下 穷举法往往是一 个简单有效的方法 个简单有效的方法 用算法的复杂性来衡量算法的效率 时间复杂性和空间复杂性 用算法的复杂性来衡量算法的效率 时间复杂性和空间复杂性 算法的时间复杂性越高 算法的执行时间越长 反之 执行时间算法的时间复杂性越高 算法的执行时间越长 反之 执行时间 越短 算法的空间复杂性越高 算法所需的存储空间越多 反之越短 算法的空间复杂性越高 算法所需的存储空间越多 反之 越少 越少 算法的输入规模和运行时间的关系算法的输入规模和运行时间的关系 设百鸡问题的两个算法中其最内部的循环体每执行设百鸡问题的两个算法中其最内部的循环体每执行设百鸡问题的两个算法中其最内部的循环体每执行设百鸡问题的两个算法中其最内部的循环体每执行 一次一次 需需一次一次 需需1 s1 s时间时间 时间时间 算法算法N 100N 100时间时间N 10000N 10000时间时间 算法分析概念算法分析概念 2014 9 62014 9 6Algorithm IntroductionAlgorithm Introduction3737 算法算法1 1 算法算法2 2 100100万次万次 714714次次 1s1s 714us714us 10000 310000 3 10000 5 1 10000 3 1 10000 5 1 10000 3 1 1111天天1313小时小时 6 76 7秒秒 上表就是算法的执行时间随问题规模的增大而增长的情况上表就是算法的执行时间随问题规模的增大而增长的情况 算法分析的任务算法分析的任务 对设计出的每一个具体的算法 利用数学工具利用数学工具 讨论其复 杂度 与算法执行时间相关的因素与算法执行时间相关的因素 1 问题中数据存储的数据结构数据结构 算法分析概念算法分析概念 2014 9 62014 9 6Algorithm IntroductionAlgorithm Introduction3838 1 问题中数据存储的数据结构数据结构 2 算法采用的数学模型数学模型 3 算法设计的策略算法设计的策略 4 问题的规模问题的规模 5 实现算法的程序设计语言实现算法的程序设计语言 6 编译算法产生的机器代码的质量 7 计算机执行指令的速度 时间复杂性分析的关键时间复杂性分析的关键时间复杂性分析的关键时间复杂性分析的关键 问题规模问题规模 输入量的多少输入量的多少 问题规模问题规模 输入量的多少输入量的多少 基本语句基本语句 基本语句基本语句 执行次数与整个算法的执行时间执行次数与整个算法的执行时间执行次数与整个算法的执行时间执行次数与整个算法的执行时间 成正比的语句成正比的语句成正比的语句成正比的语句 算法分析概念算法分析概念 2014 9 62014 9 6Algorithm IntroductionAlgorithm Introduction3939 成正比的语句成正比的语句成正比的语句成正比的语句 for i 1 i n i for i 1 i n i for j 1 j n j for j 1 j n j x x 问题规模问题规模 问题规模问题规模 n n 基本语句基本语句 基本语句基本语句 x x 算法效率的衡量方法算法效率的衡量方法 通常有两种衡量算法效率衡量算法效率的方法 1 事后统计法事后统计法 有缺点有缺点 较少使用较少使用 2 事前分析估算法事前分析估算法 算法分析概念算法分析概念 2014 9 62014 9 6Algorithm IntroductionAlgorithm Introduction4040 2 事前分析估算法事前分析估算法 算法的时间效率是问题规模的函数问题规模的函数 假如 随着问 题规模n的增长 算法执行时间的增长率和f n 的增 长率相同 则可记作 T n f n 称T n 为算法 的渐近时间复杂度渐近时间复杂度 Asymptotic Time Complexity 简称时间复杂度时间复杂度 是数量级的符号 时间复杂度估算时间复杂度估算 因为因为 算法算法 控制结构控制结构 原操作原操作 固有数据类型的操作固有数据类型的操作 所以所以 算法的执行时间算法的执行时间 原操作的执行次数原操作的执行次数 原操作原操作 算法分析概念 2014 9 62014 9 6Algorithm IntroductionAlgorithm Introduction4141 算法的执行时间算法的执行时间 原操作的执行次数原操作的执行次数 原操作原操作 语句的频度语句的频度指的是该语句重复执行的次数指的是该语句重复执行的次数 一个算法转换为算法后所耗费的时间一个算法转换为算法后所耗费的时间 除了与所用的计除了与所用的计 算软算软 硬件环境有关外硬件环境有关外 主要取决于算法中指令重复主要取决于算法中指令重复 执行的次数执行的次数 即即与语句的使用频度相关与语句的使用频度相关 一个算法中所有语句的频度之和所有语句的频度之和构成了该算法的运行 时间 例如 for j for j 1 1 j nj n j j for k for k 1 1 k nk n k k 算法分析概念算法分析概念 2014 9 62014 9 6Algorithm IntroductionAlgorithm Introduction4242 for k for k 1 1 k nk n k k x x 语句 x k n k 的频度是n n2 2 语句 j 1 的频度是1 1 语句 j n j k 1 的频度是n n 算法运行时间为 3 3 n n 2 2 3 3n n 1 1 对较复杂的算法计算的运行时间 常从算法中选取一种对 于所研究的问题来说是基本基本 或者说是主要或者说是主要 的原操作原操作 以该基基 本操作本操作在算法中重复执行的次数作为算法运行时间的衡量准则 这个原操作原操作 多数情况下是最深层次循环体内的语句中的原操最深层次循环体内的语句中的原操 作作 算法分析概念算法分析概念 2014 9 62014 9 6Algorithm IntroductionAlgorithm Introduction4343 例如例如 for i for i 1 1 i ni n i i for j for j 1 1 j nj n j j c i j c i j 0 0 for k for k 0 0 k nk0 则有则有T n O nm 且且T n n m 因此因此 有有T n n m 渐进符号渐进符号 15 2014 9 62014 9 6Algorithm IntroductionAlgorithm Introduction5656 举例举例举例举例 例例例例4 4 指数函数指数函数指数函数指数函数 令令令令n0 0 n n0时时 有有时时 有有c1 1 5 5 g n 2 n 使使 渐进符号渐进符号 16 2 25 nnT n 25 1 ngcnT n 2 n ngnT 2014 9 62014 9 6Algorithm IntroductionAlgorithm Introduction5757 25 1 ngcnT 2 n OnfOnT 26225 2 nfcnT nnn 2 ngnT 21 nfcnTngc 2 n nT 令令令令n0 4 n n0时时 有有时时 有有c2 2 6 6 f n 2 2 n 使得使得 同时同时 有有 同时同时 有有 算法 渐进渐进 时间复杂度 一般均表示为以下几种数量 级的形式 n为问题的规模 c为一常量 1 1 称为常数级称为常数级 logn logn 称为对数级称为对数级 n n 称为线性级称为线性级 渐进符号渐进符号 16 2014 9 62014 9 6Algorithm IntroductionAlgorithm Introduction5858 n n 称为线性级称为线性级 n nc c 称为多项式级称为多项式级 c n c n 称为指数级称为指数级 n n 称为阶乘级称为阶乘级 下表时间复杂性的阶为下表时间复杂性的阶为log n n nlog n n 2 n 3 2 n log n n nlog n n 2 n 3 2 n 当当n 2 3 2 4 n 2 3 2 4 2 16 2 16时时 算法的渐近运行时间算法的渐近运行时间 假定假定 每个操作是每个操作是1ns1ns nn n 83 n8 n24 n64 n512 n256 n 164 n16 n64 n256 n4 096 65 536 325 n32 n160 n1 024 32 768 4294 967 ms 646 n64 n384 n4 096 262 144 5 85 c 1287 n128 n896 n16 384 1997 152 c nlognnlog 2 n 3 n n 2 渐进符号渐进符号 17 表表1 不同时间复杂性下不同输入规模的运行时间不同时间复杂性下不同输入规模的运行时间 2014 9 62014 9 6Algorithm IntroductionAlgorithm Introduction5959 2568 n256 n2 048 65 536 16 777 msc 5129 n512 n4 608 262 144 134 218 msc 102410 n1 024 10 24 1048 576 1073 742 msc 204811 n2 048 22 528 4194 304 8589 935 msc 409612 n4 096 49 152 16 777 ms68 719 sc 819213 n8 196 106 548 67 174 ms549 752 sc 1638414 n16 384 229 376 268 435 ms1 222 hc 3276815 n32 768 491 52 1073 742 ms9 773 hc 6553616 n65 536 1048 576 4294 967 ms78 187 hc n 纳秒纳秒 微秒微秒ms 毫秒毫秒s 秒秒h 小时小时d 天天y 年年c 世纪世纪 以上时间复杂度级别是由低到高排列的以上时间复杂度级别是由低到高排列的 其随规模其随规模n n的增的增 长率长率 由下图可见一斑由下图可见一斑 渐进符号渐进符号 18 2014 9 62014 9 6Algorithm IntroductionAlgorithm Introduction6060 图 T n 与规模n的函数关系 一般来说如果选用了阶乘级的算法阶乘级的算法 则当问题规模等于或 者大于10时就要认真考虑算法的适用性问题算法的适用性问题 所以 原则上一 个算法的时间复杂度 最好不要采用指数级和阶乘级的算法最好不要采用指数级和阶乘级的算法 而应尽可能选用多项式级或线性级等时间复杂度级别较小的算 法 渐进符号渐进符号 19 2014 9 62014 9 6Algorithm IntroductionAlgorithm Introduction6161 对于较复杂的算法复杂的算法 可将它分解成容易估算的几个部分 然后再利用 O 的求和原则得到整个算法的时间复杂度 例 若算法的两个部分的时间复杂度分别为 T1 n O f n 和T2 n O g n 则总的时间复杂度为 T n TT n T1 1 n T n T2 2 n O max f n g n n O max f n g n 渐近符号定义及举例渐近符号定义及举例 1 1 g logn 1 2 ngnfnnf nngnf 证例 2014 9 62014 9 6Algorithm IntroductionAlgorithm Introduction6262 2 nnlognnlogn 渐近符号定义及举例渐近符号定义及举例 2 2 log loglog log log2 1 nnnj nnj nn n j 解 求例 2014 9 62014 9 6Algorithm IntroductionAlgorithm Introduction6363 log 2 log 2 2 log log log loglog 1 2 1 11 nnnnnj nnnj n j n j jj 解 渐近符号定义及举例渐近符号定义及举例 3 3 2 log 2 23 2 n nn nnn n 由于 对不等式两边取对数即解 求例 2014 9 62014 9 6Algorithm IntroductionAlgorithm Introduction6464 2 2 2 log log log log 2 1 nn j n nnn nnjn 即 所以 由于 渐近符号定义及举例渐近符号定义及举例 4 4 log 1ln 1 1 4 1 1 1 1 nn x dx j j n n j n j 解 提示利用积分的定义求例 2014 9 62014 9 6Algorithm IntroductionAlgorithm Introduction6565 log 1 log ln1 1 1 1 1 1 1 21 1 1 n j nn x dx jj xj n j n n j n j j 1 2 算法分析算法分析 算法分析概念算法分析概念 渐进符号渐进符号 最好最好 最坏和平均情况最坏和平均情况 非递归算法的分析非递归算法的分析 2014 9 62014 9 6Algorithm IntroductionAlgorithm Introduction6666 非递归算法的分析非递归算法的分析 递归算法的分析递归算法的分析 算法的后验分析算法的后验分析 最好情况下最好情况下的时间复杂度 时间复杂度下界 一般记为Tmin 最坏情况下最坏情况下的时间复杂度 时间复杂度上界 一般记为Tmax 最好最好 最坏和平均情况最坏和平均情况 2014 9 62014 9 6Algorithm IntroductionAlgorithm Introduction6767 Tmax 平均情况下平均情况下的时间复杂度 一般记为Tavg 以上三种情况下的时间复杂性以上三种情况下的时间复杂性 各从某一个角各从某一个角 度来反映算法的效率度来反映算法的效率 各有各的用处各有各的用处 也各有各也各有各 的局限性的局限性 但实践表明可操作性最好的但实践表明可操作性最好的 且且最有最有 实际价值的实际价值的 是是最坏情况下的时间复杂性最坏情况下的时间复杂性Tmax 一般来说一般来说 最好情况最好情况和和最坏情况的时间复杂性最坏情况的时间复杂性 最好最好 最坏和平均情况最坏和平均情况 2014 9 62014 9 6Algorithm IntroductionAlgorithm Introduction6868 一般来说一般来说 最好情况最好情况和和最坏情况的时间复杂性最坏情况的时间复杂性 是很难计量的是很难计量的 有时也按平均情况计量时间复有时也按平均情况计量时间复 杂性杂性 但要对输入不同数据的概率做人为的假但要对输入不同数据的概率做人为的假 设设 一般是假设等概率一般是假设等概率 之后才能进行之后才能进行 所做的所做的 假设缺乏必要的根据假设缺乏必要的根据 因此因此 在最好情况和平在最好情况和平 均情况下的时间复杂性分析还均情况下的时间复杂性分析还仅仅是停留在理仅仅是停留在理 论上论上 例例1 1 在一维整型数组在一维整型数组A n 中中顺序查找顺序查找与给定值与给定值k相相 等的元素等的元素 假设该数组中有且仅有一个元素值为假设该数组中有且仅有一个元素值为k int Find int A int n 最好最好 最坏和平均情况最坏和平均情况 基基 本本 语语 句句 2014 9 62014 9 6Algorithm IntroductionAlgorithm Introduction6969 for i 0 i n i if A i k break return i 最好情况最好情况 数组中第一元素就是数组中第一元素就是K 最坏情况最坏情况 数组中最后元素就是数组中最后元素就是K 平均情况平均情况 平均比较平均比较n 2个元素个元素 句句 最好情况最好情况 出现概率较大时应该分析最好情况出现概率较大时应该分析最好情况 结论结论 如果问题规模相同如果问题规模相同 时间代价与输入数时间代价与输入数 据有关据有关 则需要分析则需要分析最好情况最好情况 最坏情况最坏情况 平平 均情况均情况 最好最好 最坏和平均情况最坏和平均情况 2014 9 62014 9 6Algorithm IntroductionAlgorithm Introduction7070 最好情况最好情况 出现概率较大时应该分析最好情况出现概率较大时应该分析最好情况 最差情况最差情况 在实时系统中很重要在实时系统中很重要 平均情况平均情况 要求要求 已知输入数据是如何分布已知输入数据是如何分布 的的 通常假设等概率分布通常假设等概率分布 1 2 算法分析算法分析 算法分析概念算法分析概念 渐进符号渐进符号 最好最好 最坏和平均情况最坏和平均情况 非递归算法的分析非递归算法的分析 2014 9 62014 9 6Algorithm IntroductionAlgorithm Introduction7171 非递归算法的分析非递归算法的分析 递归算法的分析递归算法的分析 非递归算法分析的一般步骤非递归算法分析的一般步骤 1 决定用哪个决定用哪个 或哪些或哪些 参数作为算法问题规模的度量参数作为算法问题规模的度量 2 找出算法中的基本语句找出算法中的基本语句 3 检查基本语句的执行次数是否只依赖于问题规模检查基本语句的执行次数是否只依赖于问题规模 非递归算法的分析非递归算法的分析 2014 9 62014 9 6Algorithm IntroductionAlgorithm Introduction7272 3 检查基本语句的执行次数是否只依赖于问题规模检查基本语句的执行次数是否只依赖于问题规模 4 建立基本语句执行次数的求和表达式建立基本语句执行次数的求和表达式 5 用渐进符号表示这个求和表达式用渐进符号表示这个求和表达式 关键关键 建立一个代表算法运行时间的建立一个代表算法运行时间的求和表达式求和表达式 然后然后 用渐进符号表示用渐进符号表示这个求和表达式这个求和表达式 非递归算法的分析非递归算法的分析 非递归算法非递归算法Non RecursiveAlgorithm 例例 求数组最小值算法求数组最小值算法 int ArrayMin int a int n 基基 本本 语语 2014 9 62014 9 6Algorithm IntroductionAlgorithm Introduction7373 min a 0 for i 1 i n i if a i min min a i return min 语语 句句 该该 语语 句句 有有 时时 不不 执执 行行 1 1 1 n i noninT 算法分析算法分析算法分析算法分析 三种方法三种方法三种方法三种方法 1 1 计算基本运算的频度计算基本运算的频度计算基本运算的频度计算基本运算的频度 2 2 计算迭代次数计算迭代次数计算迭代次数计算迭代次数 运算时间常常与运算时间常常与运算时间常常与运算时间常常与whilewhile循环及类似结构的执循环及类似结构的