1

我在完全理解如何证明以下某些陈述时遇到问题。

例如我有一个声明：n^2logn = O(n^2). 如果我错了，请纠正我，但这说明n^2是bigO. n^2logn意味着n^2增长速度比n^2logn. 现在我们将如何证明这一点？我假设我需要使用我曾尝试使用但陷入过程中的归纳证明。我可以将此语句重写为n^2logn <= n^2吗？

是否可以使用归纳法来反驳某些东西？例如，反驳n!=O(n^n). 或者通过简单地证明任意值（假设大于 2）不满足该陈述来反驳该陈述是否有效？

最后为了清楚起见，bigTheta 指出方程在正确增长时是等价的？

4

2 回答 2

6

这种说法直观n^2logn地O(n^2)意味着 n^2logn 的增长速度最多与 - 渐近一样快n^2（这种说法是错误的）。

根据定义，这意味着有一些常数 c,N 使得对于每个n>N：c*n^2logn <= n^2

通过矛盾来反驳它非常简单。
假设（错误地）该声明是正确的，并让N,c我们的常数：

c*n^2logn <= n^2
c*logn <= 1
logn <= 1/c

但是c是恒定的，并且有一些n>N这样的logn > 1/c-矛盾。

你可以通过归纳证明其他东西来反驳，例如——如果你通过归纳证明n! < n^n——你实际上反驳了这个主张n! = n^n

关于大 theta，我试图在线程Big Theta Notation 中详细解释这个问题 - big Theta 到底代表什么？

于 2014-02-06T20:52:03.763 回答
0

我现在正在学习算法课程，所以我可以回答其中一些问题，我可以在回家查看笔记时回答其余的问题。

例如我有一个声明：n^2logn = O(n^2)。如果我错了，请纠正我，但这表明 n^2 是 n^2logn 的 bigO。这意味着 n^2 的增长速度比 n^2logn 快。

你是对的。

现在我们将如何证明这一点？我假设我需要使用我曾尝试使用但陷入过程中的归纳证明。我可以将此语句重写为 n^2logn <= n^2 吗？

是否可以使用归纳法来反驳某些东西？例如，反证 n!=O(n^n)。或者通过简单地证明任意值可以说大于 2 不满足该陈述来反驳该陈述是否有效？

我会在几个小时内回复你。

最后为了清楚起见，bigTheta 指出方程在正确增长时是等价的？

这意味着它们仅相差一个常数。换句话说，如果你将它乘以一个常数，它总是低于它所绑定的函数，如果你将它乘以另一个常数，它总是高于它所绑定的函数。

编辑：

要测试大 O，您需要在数学上证明表示算法增长的函数小于或等于常数乘以大 O 函数。

Big Omega 显示算法大于或等于 big Omega 函数。

Big Theta 可以通过两种方式证明：

  1. 证明大 O 和大 Omega。

  2. 假设算法为 f(n)，大 Theta 函数为 g(n)。为了证明大 theta，您必须证明当 n 接近无穷大时 f(n)/g(n) 的极限是某个常数，即它既不是 0 也不是无穷大。

我希望这会有所帮助。如果您有更多问题，请告诉我，我很乐意为您提供帮助。

于 2014-02-06T20:55:04.003 回答