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 の典型的な値では Big-O 部分が支配的になります。

しかし、big-O の複雑さは、特に n が無限大に近づくにつれて、大きな n のアルゴリズムの効率に関係します。言い換えれば、アルゴリズムのスケーラビリティ、つまり特定のアルゴリズムが非常に大きなワークロードまたは倍増したワークロードをどれだけうまく処理できるかがわかります。

n が常に小さいことがわかっている場合は、big-O の複雑さはそれほど重要ではなく、アルゴリズムに必要な実時間に注目する必要があります。また、同じ大きな O の複雑さ (O(n log n) など) を持つ 2 つのアルゴリズムから選択する場合、多くの場合、一方が他方よりも優れています (たとえば、ランダム ピボット クイックソートは一般にバイナリ ヒープ ソートよりも優れています)。

于 2010-07-27T19:35:52.160 に答える
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 に答える
1

big-oh に行き詰まったときはいつでも、それを競合と考えると便利です。big-oh 関数 (つまり、あなたの場合は logn) と定数 (c) を選択します。重要なことは、実際の値を選択する必要があるということです。という理由だけで、私は通常千を選びます。それから、宿敵に彼が選んだ n を選ばせなければなりません。彼は通常、10 億を選択します。

それから私は比較をします。

例を終了すると、10^9*(log(10^9)) は 1000log(10^9) よりも明らかに大きくなります。したがって、ビッグオーが機能しないことはわかっています。

于 2010-07-27T20:41:09.437 に答える
1

定義では、T と G 自体だけで C を決定する必要があります。これが定数 C の意味です。したがって、C はそれらの入力に依存するべきではありません。したがって、C = n と見なすことはできません

于 2010-07-27T19:29:05.240 に答える
1

式 n log n では、あなたがやっているように、外側の n を C と比較することはできません。これは、代数式 x(x+1) を取り、x の 1 つを定数に置き換えるようなものです。

n log n では、n は変数です。ビッグ O 式では、C は定数です。

于 2010-07-27T19:29:58.993 に答える