证明大O符号语句

也许你会困惑于这样一个事实,即你试图证明的语句只使用了一个函数,即 f

也就是说,你试图证明的陈述是 N 不渐进增长 ,这并不奇怪。对于正式证明,让我们 f : N -> N

允许 c := 1 n0 := 0 n 是一个整数,因此 n > n0

f(n) = 1 * f(n) = c * f (n) <= c * f (n)

根据定义,这意味着 f in O(f) ,这是有待证明的论点。

这是通过显式选择 c 和 n0

因为这显然是一个家庭作业问题,我想它是作为一个例子来介绍形式定义和如何使用它,而不是因为声明本身很有趣。