漸近解析問題 - アルゴリズム、漸近 - 複雑さ、ビッグ - シータ、ビッグオー

geeksforgeeks.orgで、理解できないような質問がいくつかありました（＃1と＃3）。誰かが私のために答えを明確にできることを願っていました。

true / validかfalseかを明確にする

1. QuickSortの複雑さはΘ（n ^ 2）

私は真実と答えたが、それは偽です、なぜですか？ クイックソートの時間計算量がO（n ^ 2）で、Θ（g（n））= {f（n）の場合、c1 * g（n）<= f（n）<= c2 * g（n）となります。そして、n> = n0}は、上限であるc2 * g（n）がf（n）と等しくなり得るので、それが真実であることを証明しない。

2. QuickSortの複雑さはO（n ^ 2） - 真

3.すべてのコンピュータアルゴリズムの時間の複雑さはΩ（1）と書くことができます。

これは本当ですが、私はなぜ理解していませんこれは本当です。検索アルゴリズムは、最初の要素で探しているものが見つかったと仮定してΩ（1）の下限を持つことができますが、最悪の場合がO（n ^ 2）である挿入ソートアルゴリズムなどのすべてのコンピュータアルゴリズムに当てはまります。 ）？

リンク： http://www.geeksforgeeks.org/analysis-of-algorithms-set-3asymptotic-notations/

回答：

QuickSortの時間計算量はΘ（n ^ 2）----です。これは、nの値ごとに、アルゴリズムが出力を生成するのにかかる時間がであることを意味します。 に等しい f（n）= n ^ 2の関数しかし、これはクイックソートには当てはまらないことがわかっています。これは、入力によってはクイックソートの実行時間がg（n）= nlognの関数に等しい場合があるためです。そのため、最悪、最善、または平均のどちらのケースであるかを指定する必要があります。

"QuickSortの時間計算量はO（n ^ 2）" ---これはnの各入力値に対して、アルゴリズムの実行時間は せいぜい f（n）= n ^ 2の関数これは、アルゴリズムの実行時間がf（n）= n ^ 2より短い入力が存在することを意味します。クイックソートの時間の複雑さは、g（n）= nlognおよびg（n）< f（n）。この記述はすべての場合を網羅しているので、その記述は真実です。

同様に、 "クイックソートの時間の複雑さはΩ（nlogn）"と言うのは正しいです。これは、アルゴリズムの実行時間が 少なくとも nlogn、およびn ^ 2> nlogn。

「すべてのコンピュータアルゴリズムの複雑な時間は、ここで、1は定時間関数を表します。上記のことは、任意のコンピュータアルゴリズムを実行するには、最小定時間が必要であることを意味します。

QuickSortの最悪のシナリオは O(n^2)。しかし、あなたはそれが実行されることを期待しています O(n log n) 時間。したがって、アルゴリズムの実行時間はケースごとに異なり、シータシンボルを使用してアルゴリズムの一般的な実行時間を指定することはできません。

そしてもちろん、アルゴリズムの実行時間の下限は一定時間です（Ω(1)）この下限に達する必要はありませんが、アルゴリズムを実行し、少なくとも1つの操作を行う必要があります。