这一讲介绍函数的渐近的界。
这些个函数都是时间复杂度表示的时候所需要的一些重要函数。
首先我们先定义大O符号, 有两个函数f和g,它都是定义域为自然集合的函数。
如果存在着正数c和n0, 使得当n
≥ n0的时候,有下面这个不等式成立。
这个时候就称函数渐近的上界是g(n),用这个大O符号来表示它。
而这里边的关键是什么呢?注意这是存在着正数c和n0,
就是你只要找到一个正数c满足这个不等式就可以了。
另外一个,这个n0是什么意思呢?就是我们关注的是非常大的n满足这个不等式就可以了。
对于前面比n0小的那些个n,它不满足不等式不关注,
所以这是它的一个关键。那么对于这个不等式呢,注意到这地方是≤符号。
这两条呢是大O符号的理解的时候的一个关键。
下边呢,我们来看个例子。这是一个函数n²+n,
这个时候可以表示成f(n) =O(n²),我们只要把c取成2就可以了,因为
n²加上n小于等于2n²,从 1开始这个不等式就成立了。也可以写成f(n)=
O(n³),这个时候取这个c=1, n²+n小于等于n³,在
2以上的n就成立了。所以可以写这样的表示。
那么这里边注意,这个是阶,就是f(n)它不超过g(n)的阶,
就是用大O符号来表示。它的阶不高于它,也可以跟它是同阶的。
第二个呢,这个c的存在可能是多个, 我们只要指出其中的一个就可以了。第三个
前面有限多个值可以不满足这个不等式, 关注大于等于n0的情况就可以了。
最后一个对于常函数,也可以写作O(1)。
这是关于O符号的一些例子和它应该注意的问题。
下边第二个符号是大Ω符号, 这个定义和大O符号很类似,只不过把这个
不等式是f(n)大于等于c倍个g(n),
刚才那个大O符号是小于等于。所以这里表示的是下界,就是g(n)是f(n)的一个渐近- 的下界。
那么这里边关注的也是刚才同样的问题,一个是这个c和n0是存在,
只要有这样的c和n0,找到了就可以。
另外一个呢,这个地方是一个小于等于的符号,注意这个符号,
那么下界怎么表示呢,就是f(n)它的下界是g(n), 用这个大Ω符号来表示这个下界。
这是关于第二个符号。下面看一些例子,
还是刚才那个f函数,它是n²+n这个函数,可以写成n²+n
等于Ω(n²),因为把c取成1就可以了,
n²+n正好大于等于n²了,这个是可以的。从第一项
n1,n0=1就可以成立了。那么也可以写这个公式,
以100n做它的下界也可以。这个时候我们把c取得小一点,1/100
这样就可以成立,n²+n 大于等于100n乘以1/100这是成立的。
所以从第一项n0=1就可以成立了。
那么这里边也同样有几个注意的问题, 第一个是说这是一个下界公式,就是说
g(n)的阶它不超,它是比f(n)的阶可能低,也可能是同阶的,
这是一个下阶公式。另外这个c的存在可以有多个, 在证明的时候指出其中的一个就可以了。另外就是说,
对前面有限多个n可以不管,只要对充分大的n,这个不等式成立就可以了。
下面介绍第三个符号,这个小o符号。
小o符号f,g函数跟刚才是一样的, 是对于任意的正数c
都存在着n0,使得当n≥n0的时候,有下面这个不等式成立。
那我们观察一下,这个关键在什么地方呢?一个是,这是任意的正数c, 就是随便给一个c,这个不等式都得对,
而不是说某一个c存在就可以了,是对所有的正数c。
另外呢,这个地方存在n0和刚才大O的符号定义是类似的。
第二个不同的地方,这个地方是一个大于符号, 就是说f(n)小于
cg(n),就是g(n),cg(n)大于它,f(n)小于它。
那这个地方不是小于等于,而是小于。
所以这里边我们注意到这个是说
g(n)真的要比f(n)增长的要快,才可以用这个符号。
所以这个小o的含义呢和大O是不一样的,注意这一点。
下边我们看一个例子,还是刚才那个函数。它可以写成o(n³)。
当c≥1的时候,这个是显然成立的。
因为n²+n小于,这个c要大于等于1的话,它至少小于n³,
我们只要n0取2,大于等于2的时候,n大于等于2的时候,这个不等式显然是成立的。
所以对c≥1这个不等式是没有问题的。
下边当c<1的情况会是什么样呢?这个时候我们的n0就和c相关了。
n0呢取大于2/c上取整,
因为根据这个公式呢,我们可以推出c倍的n0大于2
有这个结果,当c倍的n0大于2的时候,我们可以看到 n²+n<2n²
而cn要大于2,2n²一定小于cn³。
所以在满足这样的n0条件下,当n大于等于n0的时候 就有这个不等式成立了,这就是
刚才那个小o符号的定义所要求的。
那么同样的对于小o符号也有下面一些需要注意的地方。
一个是这里边的小o符号, 这个g(n),是真的这个g(n)要比这个f(n)要高,
这f(n)的阶要真的低,这个时候才可以用小o符号, 如果它们同阶的话,只能用大O符号不能用小o符号。
这里边这个正数必须c是所有可能的正数都要成立, 那么当c不同的时候,这个n0可能不一样。
那么当c越小的时候,这个n0就需要越大, 所以它是针对给定的c你来找n0。
同样地,我们也不关注前面有限个n的情况。
第四个符号是小ω符号,
这是一个下界的符号。那么它是说对任意的
c都存在n0,使得当n≥n0时候,有这个不等式成立。
这个不等式成立呢,我们看到g(n)是f(n)的一个下界。
它真的这是一个小于符号,它比f(n)要低。这个时候表达成下界符号,可以这样写。
那在这里边同样地,和小o符号类似,
这个c是任意的正数,对于不同的c可能存在不同的n0,
另外也注意,这个地方是一个小于符号,这也和
小o符号类似的,它没有这个等于的概念在里面。
这就是下界的表示,小ω。
那我们来看一个例子,还是刚才这个n²+n的函数,
它可以写成ω(n),它比n的阶高。
这个是对于任意的n²+n都会 大于n,只要n大于0就可以。
那么但是我们不能写f(n)=ω(n²),就是说这个函数和n²
可以满足大Ω符号,但是不满足小ω符号。
为什么呢?我们看到当c=2的时候,
就不存在着n0使得对一切n≥n0有下面这个公式成立。
因为这个c要是等于2的时候,这时候2n²
2n²对于充分大的n是不可能小于n²+n的。
所以这个时候不能写小ω符号。
这是它的出错的地方。
下面我们就可以看到,对于这个符号也会有几点 注意的地方,一个是这是一个下界符号,
小ω,就是f(n)的阶要真的比g(n)的阶要高,
另外对于不同的c,n0的值是不一样的,c越大,n0可能越大。
对前面有限个n的值可以不满足这个不等式。
最后一个重要的符号就是这个θ符号。
θ符号表示的是阶相等,
f(n)的阶和g(n)的阶不但满足大O符号,也满足Ω的时候,这个时候
它们的阶相等,可以记作θ符号。
那这是一个例子,n²+n这是100n²,它们是等阶的。
它表示的含义 θ符号就是表示这两个函数等阶。
我们关注的也是充分大的n的情况,对前面有限个n可以不管它。
下面看一个素数测试的例子,
这个是一个测试的维码,先对n要给定的是一个n,
我们要知道n是不是素数,如果是的话回答true,否则的话回答false。
先对n开根, 计算一下求整,这个s,计算出来以后,如果n不是素数,
它一定会有一个因子,在2到s之间,
因此我就对2到s每一个数都来尝试用它来整除n, 如果除的尽的话,n就不是素数,
除不尽的话,都除不尽那么n就是素数。这是这个维码。
下面我们来提个问题,假定开根计算,可以在常数时间完成。
基本运算呢就是整除,这除一次就算一次基本运算。
下面我们看到这两个表达式对不对?一个是 大O符号,一个是θ符号。
第一个式子是对的,因为我们看到这个j它的for循环
恰恰好最多是要运行s次,s正好是n的下区域,开根 下取整。所以这个是对的。
但是这个θ符号怎么样呢?这个θ符号不对。
为什么不对呢?大家可以思考一下,根据θ符号的定义,
如果你能证明了它的函数的渐进的下界, 也是根号n的话就对了。但是对于这个维玛,
它不能做到这一点。
这次的课程主要介绍了五个主要的符号。
包括大O符号,Ω符号,小o符号,
小ω符号和θ符号,这几个符号的定义是什么。
然后我们怎么用这个定义来证明函数的阶。
这是课程的主要内容。