0

big-O 表記法は、アルゴリズムの最良、最悪、および平均的なケース分析を行うためのツールですか? それとも、big-O は上限関数であるため、最悪の場合の分析のみに使用されますか?

4

2 に答える 2

1

桁数は O(n)、O(logN) などのように表されるため、Big O です。

アルゴリズムの最良、最悪、平均のケースはすべて Big O 表記で表現できます。

これをソート アルゴリズムに適用した例については、次を参照してください。

http://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_of_algorithms

アルゴリズムは、メモリの使用や CPU の使用など、複数の独立した基準に従って分類できることに注意してください。多くの場合、2 つ以上の基準の間でトレードオフが発生します (たとえば、CPU をほとんど使用しないアルゴリズムは、大量のメモリを使用する場合があります)。

于 2013-01-09T18:09:05.923 に答える
1

Big "O" は、漸近的複雑度の尺度です。つまり、N が非常に大きくなるにつれて、アルゴリズムがどのようにスケーリングするかを大まかに表したものです。

最善と最悪が同じ漸近的複雑度に収束する場合は、単一の値を使用するか、個別に計算することができます (たとえば、一部の並べ替えアルゴリズムは、並べ替えられたデータまたはほぼ並べ替えられたデータと、並べ替えられていないデータではまったく異なる特性を持っています)。 .

ただし、表記法自体はこれを伝えませんが、使用方法は伝えます。

...または、最悪の場合の分析のみのビッグオーです...

アルゴリズムの漸近的複雑度を 1 つだけ指定すると、最良のケースと最悪のケースが平均と異なるかどうか (またはどのように異なるか) を読者に伝えません。

最良のケースと最悪のケースの複雑さを示すと、それらの違いが読者に伝わります。

デフォルトでは、単一の値がリストされている場合、それはおそらく最悪のケースに収束する (または収束しない) 平均的な複雑さです。

于 2013-01-09T18:13:02.590 に答える