算法导论3.14证明题

 &＃61; O()成立吗&＃xff1f;&＃61;O()成立吗&＃xff1f;

解答&＃xff1a;

O的形式化定义如下:

O(g(n)) &＃61; { f(n): 存在正常量和c&＃xff0c;使得对所有n&＃xff0c;有0f(n)cg(n) } 。

一、 &＃61; O()成立吗&＃xff1f;

要证明 &＃61; O()&＃xff0c;我们把它们代入O的形式化定义中&＃xff0c;即

O() &＃61; { : 存在正常量和c&＃xff0c;使得对所有n&＃xff0c;有0c } 。

由于 等价于*2 &＃xff0c;那么我们只要取c&＃61;2&＃xff0c;&＃61;0&＃xff0c;即可证明该等式。

二、&＃61;O()成立吗&＃xff1f;

要证明 &＃61; O()&＃xff0c;我们把它们代入O的形式化定义中&＃xff0c;即

O() &＃61; { : 存在正常量和c&＃xff0c;使得对所有n&＃xff0c;有0c } 。

等价于*&＃xff0c;也就是说&＃xff0c;我们必须证明

*c&＃xff0c;不等式两边除以&＃xff0c;可得

c&＃xff0c;该不等式可以改为

&＃xff0c;对不等式左边进行简化&＃xff0c;可得

 。

我们知道&＃xff0c;当n足够大时&＃xff0c;必然存在 &＃xff0c;故该证明不可能成立。