問題タブ [asymptotic-complexity]

二分探索を例に取りましょう。最良の場合の実行時間は、最初の比較で得られます。

key_to_find == (imin + imax) / 2;

そして、最良の場合の実行時間は O(1) で表されます。私はそれを完全に理解していますが、私を混乱させるのは、O(1) が使用される理由と、なぜ Θ(1) または他の表記法を使用できないのかということです。

すなわち。実行時間を表すためにどの表記法を使用する必要があるかを特定する方法 (最高、平均、または最悪のケース)。

このコードの漸近的な複雑さを教えてください。

私は2つの解決策を考えました。

a)

そして再発を解決します：

b) ただし、n が 950 より大きい場合、アルゴリズムは i が 950 より小さくなるまで f(i) を呼び出し、その後 f(n-2) の呼び出しを続行するため、最後の 2 つのステートメントの複雑さについてはよくわかりません。したがって、他の解決策は次のとおりです。

そして再発を解決します：

実際には2番目が正しいと思いますが、よくわかりません。ご協力いただきありがとうございます。

アルゴリズムが問題を解決するために C(n+r-1, r-1) ステップを必要とする場合 (n は入力数、r は定数)、アルゴリズムのステップは指数関数的成長を考慮しますか?</p>

私はアルゴリズムにかなり慣れていないので、いくつか質問があります。O（n ^ 2）でデータをソートするソートアルゴリズムがあり、実行時間の複雑さがあるとしましょう。これは、たとえば選択ソートである可能性があります。ここで、選択ソートを使用する代わりに、実行時間を O(n) に短縮する HashTable を使用するとします。

• 追加のスペースの複雑さは、実行時間分析に影響しますか?
• 答えを述べるとき、これら 2 つの関係をどのように定義すればよいでしょうか?
• それとも、それらはまったく異なるものですか？

どんな助けでも大歓迎です。

これが私が分析しようとしているアルゴリズムです（以下を参照）。O(n)マージの並べ替えに時間がかかる理由がわかりません O(n logn)。両方とも同じことをしているようです。

次に、両方とも同じ j 時間の複雑さを持ちます。j を行のままにしておくと2^j X c(n/2^j)=cnになり、両方の実行時間はlog nになります。ここで、n は要素の数です。

ありがとう、ダニエル

n 要素配列の並べ替え処理では、次の処理が必要です。
X アルゴリズムでは 10 ^-8 n ²秒、
Y アルゴリズムでは 10 ^-6 n log ₂ n 秒、
Z アルゴリズムでは 10 ^-5秒。

私の質問は、それらをどのように比較するかです。たとえば、y は x に応じて高速に動作します。どの要素数を選択すればよいでしょうか?

クイックソート アルゴリズムの次の最悪のシナリオを証明しようとしていますが、問題が発生しています。最初に、n = ij のサイズ n の配列があります。アイデアは、Quicksort のすべての分割ステップで、1 つはサイズ i で、もう 1 つはサイズ i(j-1) の 2 つのサブ配列になるということです。この場合、i は 0 より大きい整数定数です。いくつかの例の再帰ツリーを引き出して、これが最悪のシナリオであり、実行時間が theta(n^2) になる理由を理解しました。これを証明するために、反復法を使用して再帰方程式を解きました。

したがって、再発は次のようになります。

この時点で、私は何をすべきかについて少し迷っています。最後の合計は、展開すると j^2 になるように見えますが、それが何らかの形で n^2 に等しいことを示す必要があります。これを続行する方法についての説明をいただければ幸いです。

この関数の計算の複雑さはどうなるのだろうと思っていましたか?

2^(ログ(n)-1)

対数は底 2 です。

Big Theta 表記では、 ?の値ごとに定数c1とが異なります。c2n

意味：

次の問題があります。n 個の要素のセット S が与えられた場合、サイズ k=1,2,...,m の順序を無視して、可能な組み合わせをすべて繰り返し生成する必要があります。

例：

考えられるすべての組み合わせは次のとおりです。

明らかに、ステップ k での組み合わせは、k-1 で得られた組み合わせを使用して計算できます。すべての k のすべての組み合わせを取得するための最適なアルゴリズム (疑似コード) とその複雑さは何ですか?