FC:1
FC:n
FC:n2
计算时间的渐进估计表示
定义1.1 如果存在两个正常数c和n0，对于所有 的n≥n0，有 |f(n)|≤c|g(n)| 则记作：f(n)=O(g(n)) 因此，当说一个算法具有O(g(n))的计算时间 时，指的就是如果此算法用n值不变的同一类数 据在某台机器上运行时，所用的时间总是小于 |g(n)|的一个常数倍。 g(n)是计算时间f(n)的一个上界函数，f(n)的 数量级就是g(n)

算法分析是对一个算法需要多少计算时间和存储 空间作定量的分析。 算法分析步骤： 首先确定使用那些运算以及执行这些运算所用 的时间。(运算包括基本数值运算和一些更基 本的任意长序列的运算) 其次是要确定出能反映算法在各种情况下工作 的数据集。（即要求我们编造出能产生最好、 最坏和有代表性情况的数据配置，通过使用这 些数据来运行算法，以更了解算法的性能）
例1 求两个正整数m,n的最大公因子
算法1-1 欧几里得算法
输入：正整数m和n 输出：m和n的最大公因子 第一步：求余数。rm%n 第二步：判断r=0?，若是，终止(n为 答案)，否则，转第三步。 第三步：互换,mn,nr,返回第一 步。
Begin
Rm%n
Y
r=0？ N
Swap(m.n)
End

授课教材
选用教材： 《计算机算法基础》（第二版） 余祥宣，崔国华，邹海明 华中科技大学 出版社 参考书目： 《算法引论》 张益新，沈雁 国防科技大 学出版社 《算法设计与分析》 周培德 机械工业出 版社

第一章 导引
---计算机算法分析与设计是面向设计的、处于核心地 位的教育课程 ---计算机算法是计算机科学和计算机应用的核心。
1.什么是算法？ 2.如何分析算法？ 3.如何表示算法？ 4.基本数据结构
1.什么是算法
数值计算方法（求解数值问题，插 值计算、数值积分等）
算法
非数值计算方法（求解非数值问题， 主要进行判断比较） 算法笼统的定义：求解一确定类问题的任意一种 特殊方法。 非形式描述：算法就是一组有穷的规则，它规定 了解决某一特定类型问题的一系列运算。
学习目标
掌握算法分析与设计的基本理论 掌握进行算法分析与设计的基本方法 （时间、空间复杂度分析，算法正确性 的证明） 掌握计算机领域中常用的非数值计算方 法，并学会用这些算法解决实际问题

课程要求
教学方式：理论(32学时)，实践(16 学时) 考核方式：考试(80%)+实验作业 (20%) 课程学分：3 先修课程：《离散数学》《数据结构》 《数值分析》《C语言程序设计》

收集此算法的实际执行时间和占用空间的统计 资料
例3： 频率计数例子

Байду номын сангаас
考虑语句xx+y在下面三个程序段中的频率计数
begin xx+y end
begin for i1 to n do xx+y repeat End
begin for i1 to n do for j1 to n do xx+y repeat Repeat End
全面分析一个算法的两个阶段

事前分析(a priori analysis)
求出该算法的一个时间限界函数(一些关于参 数的函数) 事前分析只限于每条语句的频率计数 (frequency count，该语句的执行次数， 与所用的机器无关，且独立于程序设计语言， 可由算法直接确定)


事后测试(a posteriori testing)

算法学习的五个内容

如何设计算法
运用一些基本设计策略规划算法
如何表示算法
用恰当的方式表示算法
如何确认算法
算法正确性的证明(算法确认algorithm validation)
如何分析算法
通过时间和空间复杂度的分析，确定算法的优劣
如何测试程序
测试程序是否会产生错误的结果
2.如何分析算法

时间的渐进估计表示
定理1.1 若A(n)=amnm+…+a1n+a0是 一个m次多项式，则A(n)=O(nm)。 证明：取n0=1，当n≥n0时利用A(n)的定义 和一个简单的不等式，有 |A(n)| ≤ |am|nm+…+|a1 | n+|a0 | ≤ (|am|+|am-1|/n …+|a0 |/nm ) nm ≤ (|am|+|am-1|…+|a0 |) nm 取c= |am|+|am-1|…+|a0 |，定理得证。

算法的分类

从计算时间上可把算法分为两类
多项式时间算法(polynomial
time algorithm):可用多项式来对其计算时间 限界的算法。以下六种计算时间的多项式时 间算法是最为常见的

时间的渐进估计表示
定理表明，变量n的固定阶数为m的任一多 项式，与此多项式的最高阶nm同阶。因此， 一个计算时间为m阶多项式的算法，其时 间都可以用O(nm)来表示。 例如，一个算法的数量级为 c1nm1,c2nm2,…cknmk的k个语句，则算 法的数量级及计算时间就是 c1nm1+c2nm2+…+cknmk=O(nm) 其中m=max{mi|1≤ i≤ k}
算法的五个重要特性


确定性
每一种运算必须要有确切的定义，无二义性
可行性
运算都是基本运算，原理上能在有限时间内完成
输入
有 1个或多个输入
输出
一个或多个输出
有穷性
在执行了有穷步运算后终止
算法的特性
凡是算法，都必须满足以上五条特性。 只满足前四条特性的一组规则不能称之为 算法，只能叫做计算过程。 操作系统就是计算过程的一个典型例子。 设计操作系统的目的是为了控制作业的运 行，当没有作业时，这一计算过程并不终 止，而是处于等待状态，一直等到一个新 的作业的进入。
例1 求两个正整数最大公因子的一个实例
假设 m=21 和 n=45，求21和45的最大公因子 第一步：r=m%n=21%45=21； 第二步：r 不等于0，转入第三步； 第三步：互换，m=n=45, n=r=21，返回第一步。 第一步：r=m%n=45%21=3； 第二步：r 不等于0，转入第三步； 第三步：互换，m=n=21, n=r=3，返回第一步。 第一步：r=m%n=21%3=0； 第二步：r 等于0，算法结束，3即为21和45的最大 公因子。