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