問題タブ [asymptotic-complexity]

次の関数に対して可能な最小の O() 推定値を与えてください。

できれば、私に答えるのではなく、説明してください。このような質問は私の中期にあり、私はこれを理解したいと思っています.

ありがとう

スタックへの各挿入は O(1) なので、「n」個の要素を挿入するのにかかる時間は O(n) ですか? ハッシュテーブルについても同様に話せますか? 平均的な場合、ハッシュ テーブルに「n」個の要素を挿入するのにかかる時間 = O(n) ?

漸近記法についてテストしたところ、次の質問がありました。

次の点を考慮してください。

O(o(f(n)) = o(f(n))

1. 漸近記法の規則を使用して、ステートメントの意味を言葉で書きます。
2. 陳述は真か偽か？正当化します。

私はそれを間違えました（私が書いたことを正確に覚えていません）が、次のようなものだと思います：

任意の関数 g(n) = o(f(n)) に対して、h(n) = O(f(n)) となる関数 h(n) = o(f(n)) が存在します。

それが正しいか？

(2)については、よくわかりません。誰かがこれで私を助けることができますか？

前もって感謝します。

私はトップKアルゴリズムに関してこれを求めています。O（n + k log n）の方が速いはずだと思います。たとえば、たとえばk=300とn=100000000を接続しようとすると、O（n + k log n）であることがわかります。小さいです。

ただし、C ++でベンチマークを実行すると、O（n log k）が2倍以上高速であることがわかります。完全なベンチマークプログラムは次のとおりです。

find_topkのアプローチは、O（n）でサイズnの完全なヒープを構築してから、ヒープの最上位要素をk×O（log n）で削除することです。find_topk2のアプローチは、最大要素が一番上になるようにサイズk（O（k））のヒープを構築し、次にkからnまで、要素が一番上の要素よりも小さいかどうかを比較し、そうである場合はポップすることです。一番上の要素を押して、新しい要素をプッシュします。これは、O（log k）のn倍を意味します。どちらのアプローチもまったく同じように記述されているため、実装の詳細（一時的なものの作成など）によって、アルゴとデータセット（ランダム）以外に違いが生じる可能性はないと思います。

ベンチマークの結果を実際にプロファイリングすることができ、find_topkが実際にfind_topk2よりも何度も比較演算子を呼び出していることがわかりました。しかし、私は理論的な複雑さの推論にもっと興味があります。2つの質問です。

1. 実装またはベンチマークを無視して、O（n + k log n）がO（n log k）よりも優れていると期待するのは間違っていましたか？私が間違っている場合は、O（n log k）が実際に優れていることがわかるように理由と理由を説明してください。
2. 私が1を期待するのが間違っていないのなら、なぜ私のベンチマークはそうではないのですか？

これはおそらくbig-O表記に関する初心者の質問だと思います。たとえば、リスト全体を再帰的に分解し (O(n))、それを元に戻す (O(n)) アルゴリズムがあるとします。これは、効率が O(n) + O(n) であることを意味すると仮定します。これは 2O(n)、O(2n)、または O(n) に単純化されますか? この表記法について私が知っていることから、それは O(2n) であり、漸近表記法の規則を使用して 2 を削除すると、O(n) の効率が得られます。

しかし、下限を見つけようとしていた場合、このルールは適用できるでしょうか? Ω(n) + Ω(n) = Ω(2n) の場合、2 を削除できますか? 実際には下限を下げることになるので（n < 2nなので）、そうではないと思います。

CLRS ( Cormen、Leiserson、Rivest、および Stein によるアルゴリズムの紹介) では、関数の

f ( n ) = an ² + bn + c

彼らは言った

定数c ₁ = a /4、c ₂ = 7 a /4、およびn ₀ = 2·max(| b |/ a , √(| c |/ a )) を取るとします。
次に、すべてのn ≥ n _{0に対して 0 ≤} c ₁ n ² ≤ an ² + bn + c ≤ c ₂ n ²です。 したがって、 f ( n ) は Θ ( n ² ) です。

しかし、彼らはこれらの定数の値がどのように得られたかを特定しませんでした?
証明しようとしましたができませんでした。
これらの定数の由来を教えてください。

n の関数として次のコード フラグメントの実行時間は?

「正確な答え」とは、漸近的な実行時間を決定する前に、コードに関連する方程式を指します。

ビッグオー記法については多くの質問がありますが、この質問に対する明確な答えは見つかりませんでした。

次のように書きます:
O(5n) = O(n)
および
O(3n^2 + n + 2) = O(n^2)

O(2^(2n)) = O(2^n)と書けるでしょうか?

対数の複雑さについても同じ: O(n log(4n)) = O(n log(n))?

以下の関数を漸近的に比較し、昇順で並べていきたいです。また、適切な説明lg（（√n）！）、lg（SquareRoot（n！））、SquareRootlg（n！）、（lg（√n））!,（SquareRoot（lg n））!, SquareRoot（ lg n）！

誰かがそのような計算を実行する方法を知っていますか例:

O(n^2) + THETA(n) + OMEGA(n^3) = ?

また

O(n^2) * THETA(n) * OMEGA(n^3) = ?

一般に、さまざまな漸近記法を加算および乗算する方法は?