算法设计与分析 课件 1.2.3-算法分析准则 - 时间复杂度 - 渐近分析及符号表示.pptx

算法设计与分析

算法分析-时间复杂度-渐近分析及符号表示

国家级实验教学示范中心计算机学科组规划教材算法设计与分析Python案例详解微课视频版

计数法，即统计算法执行的基本操作次数

步骤：

1.确定基本操作；

2.按相关公式建立关于n的表达式；

3.化简表达式。

什么是渐近分析

渐近分析符号

一

二

算法分析中的Bigidea

渐近分析

在问题规模足够大后，时间复杂度的增长趋势。

主流（忽略细节）+长远（规模足够大）

时间复杂度即渐近时间复杂度(AsymptoticTimeComplexity)

约翰·霍普克罗夫特（JohnEdwardHopcroft）

符号：O

定义：设f(n)和g(n)是定义在自然数集N上的函数，若存在常数C0和正整数n0，使得对所有的nn0，若f(n)≤C*g(n)，则称f(n)的阶不高于g(n)的阶且g(n)是f(n)的一个上界，

记作f(n)=O(g(n))。

即

表明:

f(n)的增长最多像g(n)的增长那样快。

符号：

定义：若f(n)=(g(n))且g(n)=(f(n))，则称f(n)和g(n)是同阶的，且记作：f(n)=(g(n))或g(n)=(f(n))。即，

表明:

f(n)的增长和g(n)的增长同样快，称(g(n))是f(n)的准确界。

符号：

定义：若f(n)≥Cg(n),则称f(n)的阶不低于g(n)的阶，并记作f(n)=(g(n))，即，

表明:

f(n)的增长至少像g(n)那样快，称(g(n))是f(n)的下界。

符号：o

定义：如果对于任意给定的ε≥0，都存在非负整数n0，使得当N≥n0时有f(N)εg(N)，则称函数f(N)当N充分大时，比g(N)低阶，记为f(N)=o(g(N))。o记为紧上界符号。

符号：ω

定义：若g(N)=o(f(N)),即当N充分大时，f(N)的阶比g(N)高，则记f(N)=ω(g(N))。ω记为紧下界符号。

测试

单选题：

在时间复杂度的结果表示中，表示下界的符号为（）；表示同阶的符号为（）；表示上界的符号为（）；表示紧上界的符号为（）；表示紧下界的符号为（）。

A：O B： C： D：o E：ω

函数阶关系证明

证明两个函数满足同阶、低阶或高阶关系，有以下方法：

1.按照阶的定义，找到合适的常数c和n0。

2.使用求极限方法，如洛必达法则。

几点说明

不能写O(g(n))=f(n)或(g(n))=f(n)。

在函数中，低阶项不影响函数的阶。

时间复杂度表达式中选择阶最高的项，去掉系数，加上O，即可得到渐进时间复杂度。

当改进算法时，首先降低算法复杂度的阶，其次再考虑减小项的系数，再减少低阶项。

几个例子