1

アルゴリズムの複雑さは、その時点でO（n ^ 2）とO（n logn）にある可能性がありますか？私はこれについて確信しています。しかし、Ω（n ^ 2）とO（n logn）、またΘ（n ^ 2）とΩ（nlogn）ではどうでしょうか。ありがとう

4

1 に答える 1

5

  1. Big-O表記は、上限のみを指します。したがって、にある場合は、O(n log n)必然的にになりますO(n^2)（n^2より速く成長するためn log n）。

  2. Ω(n^2)いいえ、との両方に含めることはできませんO(n log n)。これは、「上限n log nと下限」を意味しますがn^2、これは不可能です。

  3. Θ(n^2)は、上と下の両方がによって制限されていることを意味します。n^2これは、必然的に、下がによって制限されていることを意味しますΩ(n log n)。

于 2012-12-25T17:43:29.820 に答える