9

我在试图掌握大 O 表示法的概念时遇到了一些问题。因此，根据定义，大 O 如下，T(n) ∈ O(G(n)) if T(n) <= G(n) * C。

由于常数“C”可以是任何大于 0 的整数，所以下面的例子不也是真的吗？

例子：

n log n ∈ O(log n)
n log n <= log n * c

其中 C 等于 n 的值。

我知道答案是这样，n log n ∉ O(log n)但我不明白为什么 C 可以是任何常数。

提前感谢您的帮助：D

4

8 回答 8

11

c is just that, a constant. This means that you can't say "let c be the value of n", because you must choose some c first and then allow the comparison to hold for all n.

In other words, in order for some T(n) to be O(G(n)), there must exist no constant c such that G(n)*c is greater than T(n) for all n.

Thus n log n is not O(log n) because, no matter what constant you choose, n > c will cause n log n to be greater than c log n.

于 2010-07-27T19:28:16.500 回答
4

Let me repeat your words.

c can be any constant.

This means that c can not depend on n.

于 2010-07-27T19:28:40.983 回答
4

the idea is that the inequality holds for any n and a fixed c. so while you might find a certain c such that n log n < c log n, (namely any c>n), you can easily find other n' for which it doesn't hold (namely n'>c).

于 2010-07-27T19:28:45.360 回答
2

首先，如果 n=C 则 C 不是常数。在大多数现实世界的算法中，C 很小，因此对于 n 的典型值，大 O 部分通常占主导地位。

但是大 O 复杂度与算法的效率有关，对于大 n，尤其是当 n 接近无穷大时。换句话说，它告诉您算法的可扩展性：给定算法处理非常大或加倍的工作负载的能力。

如果您知道 n总是很小，那么大 O 复杂度就不是那么重要，而是您应该关注算法所需的挂钟时间。此外，如果您在具有相同大 O 复杂度（例如 O(n log n)）的两种算法之间进行选择，通常其中一种比另一种更好（例如，随机枢轴快速排序通常优于二进制堆排序）。

于 2010-07-27T19:35:52.160 回答
1

每当我被困在 big-oh 上时，我发现将其视为一场比赛很有用：我选择一个 big-oh 函数（因此，在你的情况下，logn）和一个常数 (c)。重要的是我必须选择一个真正的价值。我通常选择一千，只是因为。然后我必须让我的死对头选择他选择的任何 n。他通常选择十亿。

然后我进行比较。

为了完成这个例子，现在 10^9*(log(10^9)) 显然比 1000log(10^9) 大得多。因此，我知道大哦不会工作。

于 2010-07-27T20:41:09.437 回答
1

In the definition you should determine C just by the T and G themselves. This is what a constant C means. So C should not depend on the input of them. So you can not consider C = n

于 2010-07-27T19:29:05.240 回答
1

in the expression n log n, you can't compare the outside n to C, like you are doing. That would be like taking the algrebraic expression x(x+1) and replacing one of the x's with a constant.

In n log n, n is a variable. In the big O expresion, C is a constant.

于 2010-07-27T19:29:58.993 回答
1

n 的值取决于输入集，C 的值是固定的。

所以是的，如果 n = 16 和 C = 256，对于一个小的输入集，它看起来像 n^2 * lg(n)。现在将输入集增加到 100,000,000；C 的值保持在 256，你现在有 256 * lg (100,000,000)

于 2010-07-27T19:33:32.323 回答