主讲人: 吕敏 Email: { lvmin05@ustc.edu.cn } Spring 2016,USTC 算法基础 主讲人: 吕敏 Email: { lvmin05@ustc.edu.cn } Spring 2016,USTC.

Slides:



Advertisements
Similar presentations
Chapter 2 Combinatorial Analysis 主講人 : 虞台文. Content Basic Procedure for Probability Calculation Counting – Ordered Samples with Replacement – Ordered.
Advertisements

乌鲁木齐市高级中学 杨帆 2.2 用样本估计总体 2.2.1 用样本的频率分布估计总体分布 第一课时.
Course 1 演算法: 效率、分析與量級 Algorithms: Efficiency, Analysis, and Order
基本概論 Basic concepts.
第八讲 静态代码质量分析技术.
第十二章 小组评估 本章重点问题: 评估的设计 测量工具的选择和资料的收集 与分析.
数据结构 杨鹏宇 QQ: 版权所有,转载或翻印必究
第一章 資料結構導論 1-1 資料結構簡介 1-2 認識程式設計 1-3 演算法效能分析 1-4 物件導向程式設計與Java.
十五條佛規 後學:張慈幸
算法设计与分析 李清勇 教授 办公室:第九教学楼北201.
武进区三河口中学欢迎您.
算法设计与分析 Algorithm Design and Analysis
Performance Evaluation
国家和我省禽业发展政策 和扶持项目解读 安徽省畜牧兽医局
Recurrences 給定T(n)=T(n/2) + O(n) 我們該如何得到 T(n) = O(nlogn)?
-Artificial Neural Network- Hopfield Neural Network(HNN) 朝陽科技大學 資訊管理系 李麗華 教授.
第三章 隨機變數.
Chapter 8 Liner Regression and Correlation 第八章 直线回归和相关
XI. Hilbert Huang Transform (HHT)
Euler’s method of construction of the Exponential function
CH1 Number Systems and Conversion
期末考的範圍遠遠多於期中考,要了解的定理和觀念也非常多
Population proportion and sample proportion
模式识别 Pattern Recognition
计算机问题求解 – 论题 算法的效率 2018年03月14日.
Differential Equations (DE)
生活中的數列 ==費氏數列==.
Hui-Ju Chuang University of Hawaii-Manoa
Chapter 4 歸納(Induction)與遞迴(Recursion)
微積分網路教學課程 應用統計學系 周 章.
期末考的範圍遠遠多於期中考,要了解的定理和觀念也非常多
第 1 章 演算法分析.
Properties of Continuous probability distributions
Sampling Theory and Some Important Sampling Distributions
Draft Amendment to STANDARD FOR Information Technology -Telecommunications and Information Exchange Between Systems - LAN/: R: Fast BSS.
计算复杂性和算法分析 计算机科学导论第六讲
Short Version : 6. Work, Energy & Power 短版: 6. 功,能和功率
主讲人: 吕敏 { } Spring 2012,USTC 算法基础 主讲人: 吕敏 { } Spring 2012,USTC.
本章大綱 2.1 The Limit of a Function函數的極限 2.2 Limit Laws極限的性質
主讲人: 吕敏 } Spring 2012 ,USTC 算法基础 主讲人: 吕敏 } Spring 2012 ,USTC.
计算机问题求解 – 论题 有限与无限 2017年12月14日.
Interval Estimation區間估計
消費者偏好與效用概念.
校園網路架構介紹與資源利用 主講人:趙志宏 圖書資訊館網路通訊組.
4-5 数论基础.
算法的复杂度的渐近表示方法 Big O Notation and More 吕云哲.
句子成分的省略(1).
Chp.4 The Discount Factor
教專評轉型規劃草案說明 臺中市教專中心秘書 張素女
在Microsoft Access 下 建立資料庫
Chp.4 The Discount Factor
Chp.4 The Discount Factor
講師:郭育倫 第2章 效能分析 講師:郭育倫
資料結構簡介 綠園.
演算法的效率分析.
演算法分析 (Analyzing Algorithms)
Nucleon EM form factors in a quark-gluon core model
Chapter 7 Relations (關係)
赵才荣 同济大学,电子与信息工程学院,智信馆410室
计算机问题求解 – 论题 图的连通度 2018年11月13日.
Open topic2: 大O( Θ ,Ω)和小o( θ ,ω)有什么区别? 3/19/18 黄秉焜
动词不定式(6).
5. Combinational Logic Analysis
簡單迴歸分析與相關分析 莊文忠 副教授 世新大學行政管理學系 計量分析一(莊文忠副教授) 2019/8/3.
Principle and application of optical information technology
Significant Figures 有效數字
Gaussian Process Ruohua Shi Meeting
计算机问题求解---论题3-12 图中的匹配与因子分解
Presentation transcript:

主讲人: 吕敏 Email: { lvmin05@ustc.edu.cn } Spring 2016,USTC 算法基础 主讲人: 吕敏 Email: { lvmin05@ustc.edu.cn } Spring 2016,USTC

渐近分析 忽略那些依赖于机器的常量 关注运行时间T(n)的增长(当n → ∞) 不关注实际的运行时间 渐近符号能一举满足相对和绝对速度双重比较的要求 无论在什么计算平台上都能实现,不同计算平台相差一个有关运行时间的机器相关的常数因子 当n → ∞时,渐近结果不变 。 渐近分析是算法界的Big idea 2018/12/4

第二讲 函数增长 内容提要: 渐进记号 定义:O, Ω, Θ, o, ω 证明例子 常用函数 级数求和 2018/12/4 第二讲 函数增长 内容提要: 渐进记号 定义:O, Ω, Θ, o, ω 证明例子 常用函数 级数求和 从数学角度介绍渐近符号及递归解法. 2018/12/4

Asymptotic notation(渐近记号) 表示渐近运行时间的记号用定义域为自然数集的函数定义。 为了方便,可以将定义域扩充至实数域或缩小到自然数集 的某个受限子集上。 注意:要清楚这些表示法的准确含义 2018/12/4

O-notation: asymptotic upper bound(渐近上界) O(g(n)) = {f(n): 存在正常数c , n0 使得 0≤f(n)≤c g(n), for all n≥n0}. 小于或等于g(n),即以g(n)为上界。 一些文献中用 O-notation 来表示一致紧界。为表示f(n)属于集合O(g(n)),通常可以记为f(n)=O(g(n))。如果f(n)=theta(g(n)),则也蕴含着f(n)=O(g(n)),因为theta记号比O记号来得强。按照集合论中的写法,theta(g(n))属于O(g(n))。 5

O-notation:渐近上界 O – notation: O(g(n)) = {f(n): 存在正常数c , n0 使得 0≤f(n)≤c g(n), for all n≥n0}. Example: 2n2 = O(n3), with c=1 and n0=2 Example of functions in O(n2) 一些文献中用 O-notation 来表示渐近确界,但是本课程利用theta记号来表示。O记号表示的是渐近上界,并没有不反映该上界是如何接近。 6

O-notation:渐近上界 O – notation: O(g(n)) = {f(n): 存在正常数c , n0 使得 0≤f(n)≤c g(n), for all n≥n0}. O(g(n)) :函数集合 f(n)=O(g(n)):f(n)属于集合O(g(n)) 此处”=”不对称 7

O-notation:渐近上界 O – notation 的其它用法: 出现在等式右边:表示该集合中的某个函数 Eg: f(n)=n3+O(n2) : O(n2) 此处表示了一个误差界限。 存在h(n) ∊ O(n2) , f(n)=n3+h(n) 出现在等式左边: Eg:n2+O(n)= O(n2) “=” 表示“is” 任意n2+O(n)都是O(n2) 即,对任意的f(n) ∊ O(n) , 都存在函数h(n) ∊ O(n2) , 使得 n2+f(n)= h(n) 若有这种形式的 “…=…” 等式关系链,则等式可以通过链从前往后传递下去。 表示:f(n)主要是n3 ,但还有一些低阶项 则第一个等于最后一个或以最后一个为上界 等式链传递 不能反过来,从后往前 8

Ω-notation: asymptotic lower bound(渐近下界) Ω(g(n)) = {f(n):存在正常数c , n0使得 0≤c g(n)≤f(n) for all n≥n0}. 大于或等于g(n),即以g(n)为下界。 Ω记号给出了一个函数的渐近下届,图(c)说明了Ω记号的直观意义。对所有在n0右边的n值,函数f(n)的数值等于或者大于cg(n)。 9

Ω-notation: 渐近下界 Ω – notation: Ω(g(n)) = {f(n):存在正常数c , n0使得 0≤c g(n)≤f(n) for all n≥n0}. Example of functions in Ω(n2) 10

Ω-notation: 渐近下界 因为Ω记号描述了渐近下界,当它用来对一个算法最佳情况运行时间限界时,也隐含给出了在任意输入下运行时间的界。 插入排序的最佳情况运行时间是Ω(n),这隐含着该算法的运行时间是Ω(n)。 我们不能说插入排序算法的运行时间为Ω( )。这是因为存在一个输入(也就是已经排好序情况下),插入排序时间为Θ(n)。但是,可以说该算法的最坏运行时间为Ω( )。 当我们说一个”算法的运行时间为Ω(g(n))”时,我们是指对足够大的n值,对输入规模为n的任意输入,其运行时间至少是g(n)的一个常数倍。 因为Ω记号描述了渐近下界,当它用来对一个算法最佳情况运行时间限界时,也隐含给出了在任意输入下运行时间的界。 例如,插入排序的最佳情况运行时间是Ω(n),这隐含着该算法的运行时间是Ω(n)。 同样地,我们不能说插入排序算法的运行时间为Ω(n2)。这是因为存在一个输入(也就是已经排好序情况下),插入排序时间为Θ(n)。但是,可以说该算法的最坏运行时间为Ω(n2)。 当我们说一个”算法的运行时间为Ω(g(n))”时,我们是指对足够大的n值,对输入规模为n的任意输入,其运行时间至少是g(n)的一个常数倍。 11

Θ-notation: asymptotically tight bound(渐近紧界) Θ(g(n)) = {f(n):存在正常数c1, c2 , 和 n0 使得 0≤c1g(n)≤f(n)≤c2g(n) for all n≥n0}. “f(n)=Θ(g(n))” 即“f(n)∈Θ(g(n))” 2018/12/4

Θ-notation: asymptotically tight bound(渐近紧界) Θ(g(n)) = { f(n): 存在正常数c1, c2 , 和 n0 使得 such that 0≤c1g(n)≤f(n)≤c2g(n) for all n≥n0 }. 本章假 设所有的渐近符号为渐近非负。 Example1. 证明 n2/2-3n=Θ(n2) 只需确定正常数 c1, c2, 和 n0 使得 取c1 =1/14, c2=1/2, and n0=7, 验证得到 n2/2-3n=Θ(n2) 可能有多个值,只要存在某个值即可。 2018/12/4

Θ-notation: asymptotically tight bound(渐近紧界) Example 2. 证明 (反证法) 假设存在 c2 和 n0 使得当 时, 有 。 则 这与n任意大矛盾。 2018/12/4

Θ-notation: 渐近紧界 Theorem 3.1 For any two functions f(n) and g(n), we have f(n)=Θ(g(n)) if and only if f(n)=O(g(n)) and f(n) =Ω(g(n)). Prove: 根据到目前为止我们所见过的各渐近记号的定义,容易证明下面重要定理。 15

Θ-notation: 渐近紧界 Theorem 3.1 For any two functions f(n) and g(n), we have f(n)=Θ(g(n)) if and only if f(n)=O(g(n)) and f(n) =Ω(g(n)). In practice, rather than using the theorem to obtain asymptotic upper and lower bounds from asymptotically tight bounds, we usually use it to prove asymptotically tight bounds from asymptotic upper and tower bounds. (定理作用:实际中,通常根据渐近上界和渐近下界来证明渐近紧界,而不是根据渐近紧界来得到渐近上界和渐近下界。) 这里我们是利用渐近确界导出渐近上界和渐近下界,但是实际应用中一般都是用渐近上界和渐近下届来证明出渐近确界。 16

o-notation: (渐近非紧上界) 大O记号所提供的渐近上界可能是、也可能不是渐近紧确的。 例如, 2n2=O(n2)是渐近紧确的, 但 2n=O(n2) 却不是. 我们利用小o记号来表示非渐近紧确的上界,其定义如下 (渐近非紧上界) o(g(n)) = {f(n): for any positive constants c>0, there exits a constant n0>0 such that 0≤f(n)<c g(n) for all n≥n0}. For example, 2n=o(n2), but 2n2≠o(n2). 大O记号所提供的渐近上界可能是、也可能不是渐近紧确的。 如2n2=O(n2)是渐近紧确的,而2n=O(n2)却不是。 我们利用小o记号来表示非渐近紧确的上界,其定义如下: 17

ω-notation —渐近非紧下界 ω-notation is to Ω-notation as o-notation is to O-notation. The ω-notation denotes an lower bound that is not asymptotically tight. Formally, define ω(g(n)) as the set ω(g(n)) = { f(n): for any positive constants c>0, there exits a constant n0>0 such that 0≤c g(n)<f(n) for all n≥n0}. One way to define it is by f(n)∈ω(g(n)) if and only if g(n)∈o(f(n)) For example, n2/2=ω(n), but n2/2≠ω(n2). The relation f(n)=ω(g(n)) implies that 1)小ω记号与Ω记号的关系就好像小o和大O记号的关系一样。 2)小ω记号表示非渐近紧确下界,其形式化定义为: 也可以利用小o记号来定义。 3)同样地小ω记号也表示了一种极限关系,relation f(n)=ω(g(n))表示当n趋于无穷时,f(n)相对g(n)来说变得任意大了。 18

Comparison of functions(函数比较) Many of the relational properties of real number apply to asymptotic comparisons. For the following, Assume that f(n) and g(n) are asymptotically positive. Transitivity(传递性) 实数的许多关系属性可以应用于渐近比较下面假设f(n)和g(n)是渐近正值函数。 19

Comparison of functions(函数比较) Reflexivity(自反性) Symmetry(对称性) Transpose symmetry(反对称性) 20

Comparison of functions(函数比较) An analogy between the asymptotic comparison of two functions and the comparison of two real numbers (函数渐近性比较与实数比较的类比) 因为这些性质对渐近记号也成立,我们可以将两个函数f与g的渐近比较和两个实数a与b的比较作一类比: 如果f(n)=o(g(n)),则f(n)比g(n)渐近较小;如果f(n)=ω(g(n)),则f(n)比g(n)渐近较大。 21

Comparison of functions(函数比较) One property of real numbers, does not carry over to asymptotic notation Trichotomy(三分法): any two real numbers a and b, one of the following must holds: a<b, a=b, or a>b. Not all functions are asymptotically comparable. That is, for two functions f(n) and g(n), it may be the case that neither f(n)=O(g(n)) nor f(n)=Ω(g(n)) holds. For example, the functions n and cannot be compared using asymptotic notation. 虽然很多情况下可以把实数集上的属性类比与渐近记号,但是实数上的“三分性”却不能用到渐近记号上。 三分性(三分法):对于两个实数a和b,下列三种情况恰有一种成立:a<b,a=b,或a>b; 虽然任何两个实数都可以做比较,但并不是所有的函数都是渐近可比较的。也就是说,对于两个函数f(n)和g(n),可能f(n)=O(g(n))和f(n)=Ω(g(n)) 都不成立。比如:n和n^(1+sinn). 22

n →∞, 归并排序Θ(nlgn), 算法性能优于 插入排序Θ(n2) 利用函数增长率来描述算法效率,并可以用来比较各种算法的相对性能; 算法的渐近效率,即极限情况下的函数行为 通常忽略低阶项和常数因子 如何描述算法的运算时间 比较函数大小的方法 2018/12/4

第二讲 函数增长 内容提要: 渐进记号 常用函数 级数求和 2018/12/4

Standard notation and common function Monotonicity(单调性) Floors and ceilings Modular arithmetic (remainder or residue) (模运算) Polynomials(多项式) Exponentials(指数) Logarithms(对数) Factorials(阶乘) 本节我们回顾一些标准的数学函数和记号,并给出他们之间的关系。见书本Page31。 这里需要注意如下几个记号:1)下取整和上取整;2)取模运算;3)对数运算:对数的表示方法。 斯特林近似公式 25

Standard notation and common function Functional iteration(迭代函数) We use the notation f(i)(n) to denote the function f(n) iteratively applied i times to an initial value of n. For non-negative integers i, we recursively define For example, if f(n)=2n, then 迭代函数相对比较新,可以重点了解一下。 26

Standard notation and common function The iterated logarithm function(多重对数函数) We use the notation lg*n to denote the iterated logarithm. Let lg(i)n be iterated function, with f(n)=lgn, that is lg(i)(n)=lg(lg(i-1)(n)) . lg(i)n is defined only if lg(i-1)n>0. Be sure to distinguish lg(i)n from lgin. lg*n is defined as The iterated logarithms is a very slowly growing function: 265536 >>1080. Rarely encounter an input size n such that lg*n>5. Fibonacci numbers 人类能够观测到的宇宙中的原子总数约为1080 27

第二讲 函数增长 内容提要: 渐进记号 常用函数 级数 求和 2018/12/4

级数求和 定义:有限和、无限和、级数收敛、级数发散的、绝对收敛级数 等差级数: 平方和与立方和: 几何级数: 调和级数: 级数的积分和微分: 2018/12/4

确定求和时间的界 数学归纳法 确定级数各项的界 分割求和:可以将级数表示为两个或多个级数,按下标的范围进行划分,然后再对每个级数分别求界。 1)计算级数的准确值 2)计算和式的界,如:证明几何级数 的界是 3)一个容易犯的错误,如:证明 确定级数各项的界 1)一个级数的理想上界可以通过对级数中的每个项求界来获得; 2)一个级数实际上以一个几何级数为界时,可以选择级数的最大项作为每项的界(注意防止犯错!) 分割求和:可以将级数表示为两个或多个级数,按下标的范围进行划分,然后再对每个级数分别求界。 2018/12/4

谢谢! Q & A 作业: 3.2-3 第三章思考题 3-2,3-3 2018/12/4