Find centralized, trusted content and collaborate around the technologies you use most.
Teams
Q&A for work
Connect and share knowledge within a single location that is structured and easy to search.
アルゴリズムの複雑さは、その時点でO(n ^ 2)とO(n logn)にある可能性がありますか?私はこれについて確信しています。しかし、Ω(n ^ 2)とO(n logn)、またΘ(n ^ 2)とΩ(nlogn)ではどうでしょうか。ありがとう
Big-O表記は、上限のみを指します。したがって、にある場合は、O(n log n)必然的にになりますO(n^2)(n^2より速く成長するためn log n)。
O(n log n)
O(n^2)
n^2
n log n
Ω(n^2)いいえ、との両方に含めることはできませんO(n log n)。これは、「上限n log nと下限」を意味しますがn^2、これは不可能です。
Ω(n^2)
Θ(n^2)は、上と下の両方がによって制限されていることを意味します。n^2これは、必然的に、下がによって制限されていることを意味しますΩ(n log n)。
Θ(n^2)
Ω(n log n)