2

O(5n) = 5*O(n) ですか? 私が理解していることから、O(5n) == O(n)。したがって、それらは等しくありませんか？間違っている場合は修正してください。

4

6 に答える 6

7

You only care the asymptotic behavior of the function and if f(x)/g(x) converges to a constant the two functions are defined to belong to the same big-O class. So as 5*n / n is always 5. So O(n) = O(5*n).

As for your question: O(f(x)) is defined as the set of functions having the same asymptotic behavior as f(x) and thus 5*O(N) is not defined. There is no such thing.

于 2013-02-27T16:20:42.197 に答える
2

あなたは正しいです、O(5n)確かに に等しいO(n)です。5*O(n) は意味をなさない、O結果を返さない、それは記法です。したがって、それを数で掛けることはできません。

エラー用語など、数式内で Big O が使用される定義がいくつかありますが。ただし、事前にこのように定義する必要があります。

ここにを説明するウィキペディアのリンクO(c*n) = O(n)があります。

于 2013-02-27T16:22:14.313 に答える
1

O(5n) = 5*O(n)

前述のとおり、これは定義されていません。

少なくともこの件に関するウィキペディアの記事を (再) 読むことをお勧めします。

「f(x) = O(g(x)) as x ->∞」は、(非公式の直感的な定義) を意味します。正式な定義については、上記の記事を参照してください。

O(5n) == O(n)。

これはより正しいと思います (「as x -> 無限」が暗示されています): f(x) = O(x) <=> f(x) = O(5x)

乾杯！

于 2013-02-27T16:46:48.977 に答える
0

数学的にはO（5N）！= O（N）ですが、アルゴリズムに関しては、効率、つまりアルゴリズムの複雑さを重視するため、変数Nを重視するため、O（5N）== O（N）同様に効率的（または複雑）の場合と同様です。

于 2013-02-27T16:29:28.693 に答える
0

what matters in variables growth rates. Adding, Substracting, Multiplying or divising by any Constant number doent change them.

Thus any constant is insignificant and can be ommited without losing accuracy.

Regarding your question - O(5n) = O(n) = 5*O(n)

于 2013-02-27T16:20:50.717 に答える
0

とは5 * { Droider }?

operator *forセット(または少なくともビッグ O 記法)の特別な定義がなければ、2 つの質問 (あなたと私のもの) はどちらも意味をなさない。
もちろん、 を定義することはできますg(n)*O(f(n)) = O(f(n) * g(n))。そうすれば完全に理にかなっていますが、最初に定義する必要があります。
私の知る限り、この操作の標準的な定義はありません。

上記の定義により、 が得られ5*O(n) = O(5*n) = O(n)、あなたの仮定は正しいです。

于 2013-02-27T16:26:55.673 に答える