记号
定义
对一个给定的函数 g(n),用 (g(n))来表示函数集合: = {:存在正常量 和 使得对所有 ,有 }。
解释
对任一个函数 f(n),若存在正常数 ,,使当 n 充分大时,f(n) 能被夹在 和 中间,则 f(n) 属于集合 。因为 是一个集合,可以写成 “”,表示 f(n) 是 的元素。不过,通常写成 “”来表示相同的意思。
上图给出函数 f(n) 与 g(n) 的直观图示,其中 f(n) = 。对于所有位于 右边的 n 值,f(n) 的值落在 和 之间,换句话说,对所有的 n≥,f(n) 在一个常因子范围内与 g(n) 相等。我们说 g(n) 是 f(n) 的一个渐近确界。
的定义需要每个成员 都是渐近非负,也就是说当 n 足够大时 f(n) 是非负值(渐近正函数则是当 n 足够大时总为正值)。这就要求函数 g(n) 本身也必须是渐近非负的,否则集合 就是空集。因此,假定 记号中用到的每个函数都是渐近非负的。
例子:
例 1:证明 。
首先要确定常数 , 和 ,使得对所有的 n≥,即
成立,用 除不等式得
右边的不等式在 时对所有的 成立。同样,左边的不等式可以让 时对所有的 成立。这样,通过选择 ,,以及 ,可以证明 。当然,还存在其他的常数选择,而重要的是确实存在某个选择。需要注意的是,这些常数依赖于函数 ,中不同的函数通常需要不同的常数。
例 2: 证明 ≠。
使用反证法进行证明,假设存在常数 和 ,使对所有的 ,有 ;这样就有 ,这对于任意大的 n 是不可能成立的,因为 是常数。
例 3: 任意的二次函数 ,其中 a,b 和 c 都是常数,且 。
舍掉低阶项并忽略常数项得出 。可以发现,当常数 , 且 ,时,对于所有的 ,满足 。
O 记号
定义:
记号渐近地给出了一个函数的上界和下界。当只有一个渐近上界时,使用 O 记号。对于给定函数 g(n),用 O(g(n))(读作“大 Og(n)”,有时仅读作”Og(n)”)来表示以下函数的集合:O(g(n))={f(n): 存在正常量 c 和 ,使得对所有 n≥,有 0≤f(n)≤cg(n)}
解释
上图说明了 O 记号的直观意义,对位于 右边的 n 值,函数 f(n) 的值在 g(n) 之下。
利用 O 记号,我们常常能通过查看算法的总体结构来描述算法的运行时间。例如,插入排序算法中的二重循环结构立即能引出其最坏情况运行的上界 ,内循环每一轮迭代的代价以 (常量 )为上界,下标 i 和 j 最大可以取到 n,对于 个 i 值和 j 值对中的每一对,内循环至多执行一次。
记号
定义
正如 O 记号提供了一个函数的渐近上界, 记号提供了渐近下界。对于给定的函数 g(n),用 (读作“大 ”,有时仅读作“”)来表示以下函数的集合: = {f(n):存在正常量 c 和 ,使得对所有 n≥,有 0≤cg(n)≤f(n)}
解释
上图说明了 记号的直观意义,对所有在 右边的 n 值,函数 f(n) 的数值等于或大于 cg(n)。
o 记号
O 记号与 o 记号的定义是类似的,主要区别在于对 f(n)=O(g(n)),界 0≤ f(n)≤ cg(n) 对某个常数 c>0 成立,但对 f(n)=o(g(n)),界 0≤ f(n)≤ cg(n) 对所有常数 c>0 成立。从直觉上看,在 o 表示中当 n 趋于无穷时,函数 f(n) 相对于 g(n) 来说就不重要了,即
记号
定义
表示非渐近紧确的下界,它的一种定义为 ,当且仅当 。 的形式定义为集合 ,对任意正常数 c>0,存在常数 ,有 。
例如:,但 ≠。关系 f(n)= 意味着
如何这个极限存在。也就是说当 n 趋于无穷时,f(n) 相对 g(n) 来说变得任意大了。
一个例子
设 为一个 n 的 d 次多项式,其中 ,令 k 为一个常数。利用渐近记号的定义来证明如下性质:
1. 若 k≥d,则 。
2. 若 k≤d,则 。
3. 若 k=d,则 。
4. 若 k>d,则 。
5. 若 k<d,则 。
解:该公式可以改写为:
对于性质 1
使
得到
进一步化简得到
使 ,则
此时对于 n>时,,性质 1 得到证明。
同理,当 时,可以证明性质 2 。
其余性质的证明方式类似。
网友评论