complexity-theory

1熱

1答えて

PはComplexity TheoryのP-Completeと同じですか？私は2つのクラスが同一かどうかを知る必要があります。私はいずれか2つの間でKarpの削減を持っているので、インターネット上でそれを見つけることはできません。

4熱

5答えて

O(N)未満のメモリを使用するN個の要素、たとえば1..Nの順列を生成するための十分に単純なアルゴリズムがあるのだろうかと思います。 n番目の順列を計算する必要はありませんが、すべての順列を計算できる必要があります。は、もちろん、このアルゴリズムは、いくつかの種類の発電機である、または既にサブリニアメモリの制限に違反したサイズNのベクトルとして戻りので、結果を以下O(N)メモリを使用するいくつか

4熱

2答えて

スタックの動的配列実装の複雑さ

一般的な動的配列の実装では、新しい要素のための空きがない場合にスタックを2倍にします。この倍増の場合、プッシュ操作の平均時間はO（n）です。倍増の代わりに、（n + k）だけスタックサイズを増加させた場合のプッシュの複雑さは何ですか？そのスタックが空であると仮定するとに従い、K = 10で、我々は10個の要素にスタックを増やすよう私のアプローチがあります。 10個の要素の後に、20個の要素と

1熱

1答えて

再帰関数の複雑さ

私は再帰関数を持っています、そして、私はその複雑さを理解しようとしています。は、P（n） - 関数のランタイム（パラメータnが与えられたとき）を示す。私はP（n）= n +（n-1）* P（n-1）[p（1）= 1] を知っています。）？

3熱

1答えて

グラフ::削除の収縮の複雑さ？

"n"個の頂点と "m"個のエッジのグラフGに従来の削除縮小アルゴリズムを適用します。 Z（G）= Z（G-E）+ Z（G/E）ウィキペディアにおいて、 http://en.wikipedia.org/wiki/Chromatic_polynomial#Deletion.E2.80.93contraction 彼らは複雑であることを言う：O（1.6180 ^（N + M））。 Miの主な質問は、

-1熱

2答えて

次のプログラムの時間の複雑さは何ですか？

次のプログラムの時間の複雑さは何ですか？どのように複雑さを計算する？複雑さの上限と下限は何ですか？ O（N^2）である（N^2-N）回の反復であるあなたは、N末端からつもりあなたの外側のループでは for(i=n;i<=n^2;i++) for(j=1;j<=i*log(i);j++) a[i][j]+=3*i*j;

3熱

1答えて

正方形の和を最小にする動的プログラミング

私はこの実習試験でこの問題を抱えており、解決方法はわからないので、最終的には非常に怖いです。とにかく、この問題は、答えは緩和されるだろうがあると私は、動的プログラミングを理解する助けとなることを見出し読書:)に感謝しますので問題： n個a1のシーケンスを考えると、...、（）は、ブロックが少なくとも2つ、多くても4つの要素を含むという制約に従って、ブロックの合計の二乗をの和が最小になるよ

4熱

3答えて

スキーム：リストの終わりまでの一定のアクセス？

Cでは、単一リンクリストの最初と最後の要素へのポインタを持つことができ、リストの末尾に一定時間アクセスできます。したがって、あるリストを別のリストに追加することは、一定の時間内に行うことができる。私の知る限り、schemeはデフォルトでこの機能（つまりリストの終わりへの定数アクセス）を提供しません。明確にするために、私は "ポインタ"機能を探していません。私はそれがスキームの中で非観念的であり、

3熱

2答えて

修正後のクイックソートの実行時間= O（Nk）

これは宿題に関する質問であり、私は複雑さを見つけるのではないが、私は最善を尽くしている！スリーウェイ分割は、要素をピボットよりも小さい、等しく、大きいグループに分割するクイックソートの変更です。小さい要素と大きな要素のグループだけが再帰的にソートされる必要があります。 N個のアイテムがあり、ユニークな値がk（つまり重複が多い）がある場合、quicksortに対するこの変更の実行時間はO（Nk）で

3熱

2答えて

このソートアルゴリズムの複雑さは何ですか？

template<class T> void sSort(T *A, int first, int last) { if(A[first]>A[last]) swap(A[first],A[last]); if(first+1>=last) return; double k = floor((last-first+1)/3);