問題タブ [asymptotic-complexity]

Dictionary<K,V>.NETコレクションクラス（など）のメソッドの漸近的な複雑さ（big-Oおよびその他）に関するリソースはありますList<T>か？

C5ライブラリのドキュメントにそれに関する情報が含まれていることは知っていますが（例）、標準の.NETコレクションにも興味があります...（そしてPowerCollectionsの情報もいいでしょう）。

Big-O表記O(n)とLittle-O表記の違いは何o(n)ですか?

n log nステップをとるアルゴリズム（ヒープソートなど）があり、ステップがlog n時間かかる場合（0からn-1の範囲の「大きな」整数の比較/交換など）、プロセス全体。

言うまでもなく「n（log n）（log n）」と言えますが、これを「nlogn」に単純化できないことを納得させるのに苦労しています。同時に、私は自分ができると主張する本能を正当化するのに苦労しています。

私の本能はこれについてまったく間違っていますか？

編集

問題を複雑にすることを避けるための私の単純な例が問題を複雑にしているようです。しかたがない。

質問の本当の理由は、私はしばしば既知の複雑さを持つ標準アルゴリズムを持っていますが、異なる基礎となるコンテナーを使用して実装されているため、個々のステップはO（1）ではなくO（log n）であるということです。たとえば、Hopcroftsオートマトン最小化アルゴリズムはO（n log n）ですが、状態、遷移、および中間結果にバイナリツリーコンテナを使用し始めると、ステップ自体がO（log n）になります-O（n log n）はO（1）アクセスの仮定が無効であるため、無効になりました。

それでも、人々はn個の状態とm個の遷移があると主張しますが、遷移注釈の数が一定であり、オートマトンが多かれ少なかれ決定論的であると仮定すると、nとmはオートマトンに対して線形に関連する傾向があります。

私は過去にこれについてあまり心配していませんでした-私が扱っているケースはそれほど大きくありません。しかし、まあ、私はオートマトンコードの主要なリファクタリングを行っており、いくつかの主要なアルゴリズムについては、計算を適切に行う方がよいと思いました。

編集

また、「n（log n）（log n）」が間違っていると私はますます確信しています。

aがO（b log b）であり、bがO（log c）である場合、cに関してaは何ですか？

4n ^ 2 + 7nの移動で達成するアルゴリズムがある場合、そのOは何ですか？O（4n ^ 2）？O（n ^ 2）？

7nがカットオフされていることは知っていますが、n^2係数を維持する必要があるかどうかはわかりません。

ありがとう

再帰ツリーを使用して、指定された再帰を解決しようとしています。T(n) = 3T(n/3) + n/lg n.

最初のレベルで(n/3)/(log(n/3)) + (n/3)/(log(n/3)) + (n/3)/(log(n/3)) = n/(log(n/3))。

2番目のレベルでは、であることがわかりますn/(log(n/9))。

上記の方程式を次の形式で一般化できますか？n.loglogn

これは私が持っている一般的な疑問です、私はこれについての洞察が必要です。

注：Theta(n^k log^k (n))その関数kに含まれている必要のある関数は、>=1である必要があります。そしてこの場合、kは-1であるため、マスター定理は思い浮かびません。

マージ アルゴリズムは、2 つの入力配列の最小要素を繰り返し比較し、2 つのうち小さい方を出力に移動することによって、2 つの並べ替えられた入力配列を並べ替えられた出力配列にマージします。

次に、同じ長さの 3 つの並べ替えられた入力配列 (A1、A2、および A3) を (並べ替えられた) 出力配列にマージする必要があります。2 つの方法があります。

1. 上記の Merge アルゴリズムを使用して A1 と A2 を A4 にマージし、同じアルゴリズムを使用して A4 と A3 を出力配列にマージします。

2. 3 つの入力配列の最小要素を繰り返し比較し、3 つの最小要素を出力配列に移動することにより、上記の Merge アルゴリズムを修正します。

上記の 2 つのアルゴリズムのうち、配列要素の移動 (つまり、代入) の最悪のケースのみを考慮した場合、どちらがより効率的ですか?

配列要素の比較の最悪のケースのみを考慮した場合、上記の 2 つのアルゴリズムのどちらがより効率的ですか?

これら 2 つのアルゴリズムのうち、最悪の場合に全体的な効率が高いのはどちらですか?

汎用コンパイラの最大許容漸近ランタイムはどれくらいですか?

明確にするために：コンパイルされたプログラムではなく、コンパイルプロセス自体の複雑さ。たとえば、プログラムのサイズに応じて、ソース コードの文字数、ステートメント、変数、プロシージャ、基本ブロック、中間言語命令、アセンブラ命令などの数が異なります。

これはあなたの視点に大きく依存するため、これはコミュニティ wiki です。

これは、コンパイラを書いている人の視点から見てください。-O4最適化の 1 つが O(n^6) かかる場合、最適化レベルは大規模なプログラムに使用されますか?

関連する質問:

• 超最適化(指数関数的な複雑さまたは計算不能でさえある) が許容されるのはいつですか?

• JITには何が許容されますか? 線形である必要がありますか？

• 確立されたコンパイラの複雑さは? GCC? VC? インテル？ジャワ？C#? ターボパスカル? LCC？LLVM? （参照？）

漸近的複雑度がわからない場合: コンパイラーがプロジェクトをコンパイルするまでどのくらい待ちますか? (スクリプト言語は除く)

関数が属するクラス Big-Theta(g(n)) を示し、アサーションを証明するよう求める演習です。

この場合、f(n) = (n^2+1)^10

定義により、f(n) E Big-Theta(g(n)) <=> c1*g(n) < f(n) < c2*g(n)、c1 と c2 は 2 つの定数です。

この特定の f(n) の Big-Theta が g(n^20) であることは知っていますが、それを適切に証明する人がわかりません。この不等式を操作する必要があると思いますが、方法がわかりません

標準 C ライブラリ関数の 1 つに時間がかかりすぎて、システム全体 (一連のプロセス) が基本的に「しゃっくり」していると思われるパフォーマンスの問題があります。案の定、ライブラリ関数呼び出しをコメント アウトすると、しゃっくりはなくなります。これにより、この種のことを証明するためにどのような標準的な方法があるかを調査するようになりました。関数をテストして、システム全体が1秒間ハングするかどうかを確認するためのベストプラクティスは何ですか?

少なくとも、呼び出されている関数と目に見えるフリーズを明確に関連付けたいと思います。

ありがとう

NP完全であるが、「迅速な」アルゴリズムを知っている言語はありますか? ナップザックのように平均的にうまくいくという意味ではありません。最悪の場合でも、実行時間は 2^n^epsilon のようなものであり、結果は 0 より大きい任意の epsilon に対して保持されるため、任意に 0 に近づけることができます。