表明一个函数是 O(something)（大 O 符号）

Question

我在理解如何求解大 O 符号方程时遇到问题，例如这个：

f(n) = 10n + 5 and g(n) = n
Show that f(n) is O(g(n))

取自此处：http://web.eecs.utk.edu/~booth/311-01/notes/bigOex.html

那里说 To show f(n) is O(g(n)) we must show constants c and k such that f(n) <= cg(n) for all n >=k

我明白了：从 k 开始，f(n) 的增长速度不会快于 g(n) 乘以任意常数。

我不明白的是：

We are allowed to choose c and k to be integers we want as long as they 
are positive.  They can be as big as we want, but they can't be functions
of n.

所以为了解那些方程，我可以一直选择c和k只要满足那些要求？但如果我可以选择 k，那他们为什么要在那个网站上计算 k？

Try c = 15.  Then we need to show: 10n + 5 <= 15n.
             Solving for n we get: 5 <= 5n  or 1 <= n.
So f(n) = 10+5 <= 15g(n) for all n >= 1.  (c = 15, k = 1)

Answer 1

基本上，他们想表明，超过给定的 n 值，c * g(n) 总是 >= f(n)。因此，如果将 k 设置为该值，则不等式成立。没有必要显示 精确地 超过它所持有的点（即给定任意 c 的 k 的最小有效值）——它恰好在解决不等式时变得明显。

只要你能证明存在 some c, k 成立，你可以说 f(n) 是 O(g(n)).

表明一个函数是 O(something)（大 O 符号）

showing that a function is O(something) (big O notation)

algorithm

big-o