漸近記法に関する多くの講義、ビデオ、ソースを調べました。O、Omega、Thetaが何であるかを理解しました。しかし、アルゴリズムでは、なぜ常に Big Oh 表記のみを使用し、なぜシータとオメガを使用しないのですか (それは愚かに聞こえることはわかっていますが、これについて私を助けてください)。アルゴリズムに従って、この上限と下限は正確には何ですか?
私の次の質問は、アルゴリズムから複雑さをどのように見つけるかです。アルゴリズムがあるとします。再帰関係 T(N) を見つけて、そこから複雑さを計算するにはどうすればよいでしょうか。これらの方程式をどのように形成するのですか? 再帰的な方法を使用した線形検索の場合と同様に、T(n)=T(N-1) + 1 です。
誰かが私を初心者だと思って説明してくれたら、もっとよく理解できると思います. 私はいくつかの答えを見つけましたが、StackOverFlow では十分に説得力がありませんでした。
ありがとうございました。
シータやオメガと比較してビッグオーを頻繁に使用する理由:これは技術的なものではなく、部分的に文化的なものです。Theta の方が実際にはより適切な場合に、人々がビッグオーと言うのは非常に一般的です。オメガは実際にはあまり使用されません。これは、下限よりも上限に関心があることが多いためです。また、自明でない下限は証明するのがはるかに難しいことが多いためです。(些細な下限は通常、「すべての入力を調べる必要があるため、実行時間は少なくとも入力のサイズに等しい」というようなものです。)
もちろん、シータには上限と下限の両方が含まれるため、下限に関するこれらのコメントもシータを部分的に説明しています。
再帰関係を考え出す:すべてのケースに対処する簡単なレシピはありません。ここでは、比較的単純な再帰アルゴリズムについて説明します。
N を初期入力のサイズとします。再帰関数に R 再帰呼び出しがあるとします。(例: マージソートの場合、R は 2 になります。) さらに、すべての再帰呼び出しが初期入力のサイズを N から M に同じ量だけ減らすとします。 (例: マージソートの場合、M は N/2 になります。)そして最後に、再帰関数が再帰呼び出しの外で W を実行するとします。 (例: マージソートの場合、W はマージの N になります。)
次に、再帰関係は T(N) = R*T(M) + W になります (例: マージソートの場合、これは T(N) = 2*T(N/2) + N になります)。
アルゴリズムを作成するときは、常に最速にするためであり、すべてのケースを考慮する必要があります。これが、複雑さを優先し、アルゴリズムがこれを決して追い越さないことを確認したいため、O を使用する理由です。
複雑さを評価するには、ステップ数を数えなければなりません。方程式 T(n) = T(n-1) + 1 では、T(0) を計算する前に N ステップがあり、複雑さは線形です。（私は時間の複雑さについて話しているのであって、空間の複雑さについて話しているのではありません）。