4. if i ＜ n return i
T(n) ：算法的运行时间 问题规模n的函数
输入分布：最坏情况、 最好情况、平均情况
Tmax(n), Tmin(n), Tavg(n)
算法运行时间
假设每条语句的执行 时间均为单位时间。
=
全部语句的执行时间之和
算法运行中主要影响运行 时间的语句是基本操作， 即占有最多比例的语句。
算法设计
丘奇-图灵论点：凡是可计算的函数都是一般递归函数 （或图灵机可计算函数） • 凡是可以从某些初始符号开始，而在有 限步骤内计算的函数都是递归函数。 • 计算机只能计算一般递归函数。 • 算法设计就是根据某个算法设计策略写 出递归函数或递归算法。
算法的描述方法
• 可以用自然语言、伪代码(pseudocode)或计 算机程序语言来描述算法，必须精确地描 述计算过程。
算法设计与分析
Algorithm Design And Analysis
东北大学 信息学院 计算机应用技术研究所 郭楠
2015版
教学目标及内容
• 教学内容
– 王晓东，《计算机算法设计与分析》，1~6章
• 教学目标
– 通过对典型算法的分类介绍，掌握算法设计的主要策 略以及对算法性能正确分析的能力。 策略 算法设计
– 用有限的指令和有限的存储空间可算尽一切可算之物 – 凡是可计算的过程都可用图灵机实现 – 机器能思考吗？
程序 内部状态
纸带
Here is an implementation of a Turing machine
控制器
一台图灵机是一个七元组M = (Q, Σ, Γ, Δ, q0, B, F)
– – – – Q是内部状态的有穷集合； Σ是输入符号集，其中不包含特殊的空白符； Γ是允许使用的纸带符号的有穷集合； Δ是转移函数（即程序），根据当前状态及当前输入 符号确定下一状态及读写头的动作，包括对输入符 号的运算以及读写头的移动（左移L或右移R）；
问题 计算的过程就是 执行算法的过程 输出
问题实例 输入
算法
计算模型
图灵机(Turing Machine)
• Alan M. Turing (1912-1954) • 1936年，一种在理论计算机科学中广泛采用的抽 象计算机。它是通用数字计算机的理论原型。 • 可制造出一种十分简单但计算能力极强的计算机 装置。
– 伪代码：自然语言和计算机程序语言的混合体。
算法的正确性
• 若一个算法对于每个合理的输入实例均能终止并 给出正确的结果，则称该算法是正确的。 • 一个不正确的算法是指对某些合理的输入实例不 终止，或者虽然终止但给出的结果不是所期望得 到的答案。
An algorithm is said to be correct if, for every input instance, it halts with the correct output. An incorrect algorithm might not halt at all on some input instances, or it might halt with an incorrect answer.
平均情况性能
• The average-case efficiency
算法设计与分析
算法分析
实例 性能
what are algorithms?
• Informally, an algorithm is any well-defined computational procedure that takes some value, or set of values, as input and produces some value, or set of values, as output. • We can also view an algorithm as a tool for solving a well-defined computational problem.
初始 状态 读入 第1个数值 读入 第2个数值
当前状态 0 0 1 1 10 10 11 11
输入符号 0 1 1 0 1 0 0 1
下一状态 0 1 1 10 10 11 0
输出符号 0 1 1 1 1 0 0
读写头移动 右移 右移 右移 右移 右移 左移 错误 停机
读入完毕
程序Δ 0,0 → 0,0R 0,1 → 1,1R 1,1 → 1,1R 1,0 → 10,1R 10,1 → 10,1R 10,0 → 11,0L 11,0 → E 11,1 → 0,0S
– 时间复杂性：需要时间资源的量 – 空间复杂性：需要空间资源的量
Different algorithms devised to solve the same problem often differ dramatically in their efficiency.
算法复杂性分析
• 算法复杂性C采用一种与算法外部因素无关的测 量方法，只依赖于问题规模N、输入I以及算法A 本身的函数。分别用T和S来表示时间复杂性和空 间复杂性。
← 全部语句的执行次数之和 （问题规模n的运行时间函数） ← 基本操作的执行次数 ← （渐近）阶
为了简化算法分析过程， 并易于对不同算法的运行 时间进行对比，只考虑问 题规模充分大时的情况。
← 算法的时间复杂性
最坏情况性能
• The worst-case efficiency
– 最坏情况的输入对应最多的基本操作执行次数 – Tmax(n) = max{T(n)} – 意义：界定运行时间的上界，即对于任何输入， 运行时间不会超过Tmax(n) – 实践表明可操作性最好且最有实际价值的是最 坏情况下的时间复杂性。
如何证明 一个算法 是正确的？
算法正确性证明
• 找反例：能够使算法运行失败的输入实例。 • 数学归纳法：对于任意输入实例
– 证明：(i)算法的第1步是正确的；(ii)假设算法 的第n步是正确的，那么算法的第n+1步也是正 确的。
证明：Insertion Sort算法是正确的。
算法分析
• 算法复杂性(Complexity)：算法运行所需要 的计算机资源的量。
T = T(N, I, A) 通常，A隐含在复杂性函数名当中，因此可简化为： T = T(N, I) 只考虑某类有代表性的输入实例，因此可进一步简化为： 最好情况下Tmin(n)，最坏情况下Tmax(n)，平均情况下Tavg(n) 如果算法的时间复杂性不依赖输入实例，则简化为T(n)
such instructions like arithmetic, data movement, and control takes a constant amount of time. 该算法的 问题规模 运行时间？ 算法：顺序查找 输入：数组A[0...n-1]，数值K 输出：第一个与K相同的元素的下标，否则输出-1 t c11=1 1. i = 0
程序和算法
• 程序是算法用某种程序设计语言的具体实现。 • 程序可以不满足算法的有限性。
– 例如，操作系统是一个在无限循环中执行的程序，因 而不是一个算法。
(数据结构) 用料
(算法) 做法
(语言工具 和环境) 工具
…
(程序设计 方法) 厨艺
问题求解过程
判定性问题 构造性问题 计数问题 最优化问题
一个问题是不是 可计算的？是 “易”计算的还 是“难”计算的？
什么是计算？
计算模型
对于同一个问题 的不同算法，如 何知道哪个算法 更有效？
如何说明 一个算法 是有效的？
计算模型
• 计算模型（抽象计算机、数学模型）
–如果应用某个计算模型能够建立一个算法来求解这个问 题（即算法可停机），那么这个问题就是可计算的。 –问题的计算复杂性可以通过解决该问题所需计算量的多 少来衡量。
最好情况性能
• The best-case efficiency
– 最好情况的输入对应最少的基本操作执行次数 – Tmin(n) = min{T(n)} – 意义：虽然期望得到最好情况的输入是没有意 义的，但是对于一些算法，一个好的Tmin(n)可 以扩展到一些有用的次好输入类型。另外，如 果一个算法的Tmin(n)不令人满意，那么我们可 以立刻放弃它。
: Q Q L, R
q0 Q – q0是初始状态， {B} – B是空白符， – F是终止状态， F Q
• 设一个图灵机M = (Q, Σ, Γ, Δ, q0, B, F)
– 状态集合Q={0,1,10,11}，输入符号集Σ={1}，允许使用 的纸带符号集Γ={0,1}，空白符B=0，初始状态q0=0，程 序Δ是一个以1的个数表示数值的加法运算。 – 如果纸带上的数据0000001110110000代表3+2，那么输 出是什么？ 0000001111100000
t c2 2
t c3 3
2. while i ＜ n and A[i] ≠ K do 3. i=i+1 基本操作 该算法的运行时间 T(n)依赖输入实例： 最坏情况Tmax(n) =? 最好情况Tmin(n) =? 平均情况Tavg(n) =?
c =1t5 t4 4或 + 或c5=1 5. else return -1
问题规模
理解问题 确定计算模型、 数据结构及 算法设计策略
输入 约束条件
输出 目标函数
设计算法
证明正确性 分析算法
问题建模
• 确定问题的数学模型
– 问题类型：计数问题、判定性问题、构造性问 题、最优化问题 – 输入：给定问题实例、规模 – 输出：定义解空间，给出问题的解 – 约束和目标：定义函数 – 问题的计算复杂度：不依赖特定算法
算法
• 算法是指解决问题的方法或过程，是若干指令的 有穷序列。solution to a problem