1

我目前正在上一门课程，该课程包含一个我还没有太多经验的主题 - Big-O。这是我需要回答的问题类型的示例。请注意：这些问题类似于我需要做的家庭作业，但是数字等发生了变化。

我不是在寻找解决方案。我正在寻找有关如何有效编写证明的解释。

问题看起来像这样（第一个方程是 f(n)，第二个方程是 g(n)）：

(a) 5^(log_5(n)) and 3n+2
(b) n^2 and sqrt(3)^(log(n))

我明白，为了有效地写出证明，我必须证明

|f(x)| <= c|g(x)| for all x >= k

（k == n_0 取决于您的教学方式）所以对于第一个问题，我将问题简化为

n is O(3n+2)

我不完全确定如何开始第二个。

从这里，我如何选择值 c 和 k？它们只是使等式成立的任意值，还是我缺少更多的东西？我见过很多例子，但没有一个能解释它们是如何获得 c 和 k 的值的。

谢谢你的帮助！

4

1 回答 1

0

记住 big-O 的目的是什么：你试图证明一个函数在输入足够大的情况下以不比某个其他函数（它的上限）“快”的速度增长。考虑到这一点，k可以是相当任意的，但您可能希望选择不等式成立的k的最小非负值。如果您找不到明确的最小k，请选择一个有效的。此外，由于我们通常在上限的最重要项上“抛出”常数，因此同样地，选择不等式成立的最小正c。同样，如果您无法确定“最小”，只需选择一个有效的。一旦你回忆起k和c表示，不难记住这是对他们的处理。

你的老师/教授可能有不同的想法，所以你可能希望仔细检查，但这几乎就是这个特殊的音乐专业的人从算法课上记住的。

希望有帮助！

于 2011-01-21T23:23:16.080 回答