这一讲介绍函数的渐近的界。
这些个函数都是时间复杂度表示的时候所需要的一些重要函数。
首先我们先定义大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符号，
小ω符号和θ符号，这几个符号的定义是什么。
然后我们怎么用这个定义来证明函数的阶。
这是课程的主要内容。
Wanling QuProfessor
