乐文小说网

手机浏览器扫描二维码访问

英语考试看算法刺激（第2页）

要想f（n）非负，只要g（n）为上界2n^2等于O（n^3）什么意思?

f（n）属于g（n）构成的函数集，O（g（n））是一个函数集，集合内的函数被记做f（n）?

他呆呆的愣了一会，良久问。

“......能百度吗？”

他觉得他应该回炉重修。

“能....”

梦舒鄙视了一下，连数学都不会，还是软件专业的。

大O符号是用另一个（通常更简单的）函数来描述一个函数数量级的渐近上界。

啥玩意？

大O符号有两种使用方式——无穷大渐近与无穷小渐近。

什，什么？

似乎渐进的意思就是省略的意思，随着n的增大，会省略一些低阶项。

无穷大渐进：举个例子，解决一个规模为n的问题所花费的时间（或者所需步骤的数目）可以被求得：T（n）=4n^2-2n+2。

当n增大时，n^2;项将开始占主导地位。

因此在大多数场合下，省略低阶项和函数对表达式的值的影响将是可以忽略不计的。

T（n）=1，000，000n^2;，假定U（n）=n^3;一旦n增长到大于1，000，000，后者就会一直超越前者。

这样，大O符号就记下剩余的部分，写作：T（n）∈O（n^2）

似乎明白了......

所以那个老师的意思大概是：

f（n）=O（g（n））表示if存在适当的常数c>0和n0>0，使得f（n）<=c*g（n），f（n）>0，并且那个n充分大。

n>=n0，因为f（n）大小被g（n）大小影响，所以f（n）以g（n）为上界。

举个例子：2n^2=O（n^3），表示去掉左边的首项系数和低阶项，剩下的小于等于n^3。

这个符号有意思的是这个等号并不对称，上面的等号其实表示属于的意思。

f（n）属于g（n）构成的函数集，f（n）=O（g（n））没错的。

O（g（n）=f（n）是一个函数集，f（n）是函数集，没毛病。

集合内的函数被记做f（n）......O（g（n）=f（n），倒过来似乎...也没毛病。

“我觉得这个妙不可言c和n0.”