O、Ω、Θの違いで苦労していますか？

Question

私は現在、データ構造とアルゴリズムについての論文を取っています。私は最終的な試験に近づいており、さまざまな並べ替えと検索アルゴリズムの最悪の場合の時間の複雑さに関する質問があることを知っています。

O、Ω、Θの一般的な考え方を理解していると思います。 Oは上限を示し、Ωは上限と下限を示し、Θは下限を示します。

したがって、以下の例の質問（b）を考えてみると、自分の答えがO（n log n）かΘ（n log n）かどうか混乱していますか？

当初、Θはもっとも最悪の時間の複雑さだと思っていましたが、私もOを使って最悪の場合の時間の複雑さを参照しています。

Answer 1

オーケーあなたが後方いくつかを持って、 ので、ランダウの記号は、最悪の場合を示し、は、UpperBoundです。

Big Thetaは、タイトな漸近的な境界を示します。つまり、同じ関数に沿って最悪の場合と最良の場合があります。本質的に、Big OとBig Omegaが私たちに同じ境界を与えるとき、Big Thetaを使用します。

ビッグオメガは、最良の場合、下限を示します。

一般的に、最悪の場合はBig Oを使用し、最悪の場合と最良の場合は大きなシータを使用します。 Big OとBig Omegaだけを使用すると、客観的に正確になります