問題タブ [space-complexity]

リンクされたリストをソートするためのインプレースソートアルゴリズムを読んでいます。ウィキペディアによると

多くの場合、マージ ソートはリンク リストのソートに最適な選択です。この状況では、Θ(1)追加のスペースのみを必要とする方法でマージ ソートを実装するのは比較的簡単です。アルゴリズム (クイックソートなど) のパフォーマンスは低く、他のアルゴリズム (ヒープソートなど) は完全に不可能です。

私の知る限り、マージ ソート アルゴリズムはインプレース ソート アルゴリズムではなくO(n)、補助的な最悪の場合のスペースの複雑さがあります。現在、これを考慮して、O(1)補助スペースを使用して単一リンクリストをソートするための適切なアルゴリズムが存在するかどうかを判断できません。

ウィキペディアのクイックソートのスペースの複雑さの説明で私が理解したことから、クイックソートのスペースの複雑さはその再帰的な性質に由来します。クイックソートを非再帰的に実装することが可能かどうか、そしてそうすることで、一定のスペースの複雑さでそれを実装することが可能かどうかについて興味があります。

メモリに収まらない可能性のある大きなファイルをソートするプログラムを実装しています。すべてのファイルは行でソートされるので、リストを使用してそれを行うことを考えています。

ファイルを小さなファイルに分割するためにメモリ内に何行持つことができるかはすでに計算しましたが、N個の要素のリストを並べ替えるためにメモリ内に必要なスペースの数がわかりません。

問題は、要素の最大数（既知のサイズの文字列）と使用可能なメモリを知っている場合、List.Sortメソッドに必要なメモリのスペースはどれくらいかということです。

元の問題ステートメントは次のとおりです。

32ビットの符号なし整数の配列で、3つ（1つだけ）を除いてすべての数値が正確に2回現れる場合、O（1）の余分なスペースを使用してO（n）時間でこれらの3つの数値を見つけます。入力配列は読み取り専用です。3ではなくkの例外がある場合はどうなりますか？

入力制限のために非常に高い定数係数を受け入れる場合、これをΟ(1)時間と空間で簡単に解決できます（配列には最大2つの³³エントリを含めることができます）。Ο(1)

したがって、この質問のために、ビット長の制限を解除し、数値が最大ビットになる可能性があるより一般的な問題に集中しましょうm。

k = 2のアルゴリズムを一般化すると、私が念頭に置いていたのは次のとおりです。

1. これらの数値の最下位ビット1と0個別の数値をXORします。両方のパーティションで、結果の値がゼロでない場合、繰り返されない数値を2つのグループに分割し、それぞれに少なくとも1つのメンバーが含まれていることがわかります。
2. これらのグループごとに、2番目に最下位ビットなどを調べてさらに分割してみてください。

ただし、考慮すべき特別な場合があります。グループを分割した後、グループの1つのXOR値が両方ともゼロである場合、結果のサブグループの1つが空であるかどうかはわかりません。この場合、私のアルゴリズムはこのビットを省略して次のビットを続行しますが、これは正しくありません。たとえば、入力に対して失敗します[0,1,2,3,4,5,6]。

ここで私が考えたのは、要素のXORだけでなく、特定の関数を適用した後の値のXORも計算することでした（f(x) = 3x + 1ここで選択しました）。この追加チェックの反例については、以下のEvgenyの回答を参照してください。

以下のアルゴリズムはk>=7に対しては正しくありませんが、ここに実装を含めて、アイデアを提供します。

私の分析によると、このコードの最悪の場合の時間計算量はO(k * m² * n)、n入力要素の数（XORはO(m)、最大でk分割操作が成功する可能性があります）とスペースの複雑さO(m²)（m最大の再帰深度であり、一時的な数は次のようになる可能性があるため）です。長さm）。

問題はもちろん、適切で効率的なアプローチがあり、漸近的なランタイムが良好であるかどうかです（完全を期すためにk << n、m << nここでは、追加のスペースもほとんど必要ありません（たとえば、入力を並べ替えるアプローチは受け入れられません）。O(n)入力を変更できないため、少なくとも追加のスペースが必要になるためです！）。

編集：上記のアルゴリズムが正しくないことが証明されたので、もちろん、おそらく少し効率を下げることによって、どのように正しくすることができるかを確認するのは良いことです。スペースの複雑さはにある必要がありますo(n*m)（つまり、入力ビットの総数が劣線形です）。kタスクが簡単になる場合は、追加の入力として使用してもかまいません。

私のアルゴリズムは以下のとおりです。サーバーへのリモート呼び出しを行い、結果を取得して処理し、再度リモート呼び出しをシステムに送信します。このアルゴリズムの時間と空間の複雑さを教えてください。

私は仕事に応募してきましたが、アルゴリズムの時間/空間の複雑さについての質問を聞くたびに、うんざりしてつまずきます. どれだけ読んでも、私の脳はそれを理解しないようにプログラムされているようで、その理由は、学校をスキップして数学のバックグラウンドが非常に低いという事実にあると思います. これは通常のSOの質問ではない可能性があり、基本的に数学に関するものであるために削除される可能性さえありますが、少なくとも、この質問で次にどこに行くべきかを理解したいと思っています.

パスカルの三角形を生成するために、レベル順序トラバーサルの概念を使用しています。

コードスニペットは次のとおりです。

完全なコードはここにあります：

このアプローチの利点は、スペースの複雑さがO（N）であるということです。ここで、Nは行数です。

同じことをするより良い方法はありますか？

ソートされたセットとredisのリストのスペースの違いは何ですか？私の推測では、ソートされたセットはある種の平衡二分木であり、リストはリンクリストです。つまり、キー、スコア、値のそれぞれについてエンコードしている3つの値に加えて、リンクリストのスコアと値をまとめますが、オーバーヘッドは、リンクリストが1つを追跡する必要があることです。他のノードであり、バイナリツリーは2つを追跡する必要があるため、ソートされたセットを使用するためのスペースオーバーヘッドはO（N）です。

私の値とスコアが両方ともlongであり、他のノードへのポインターもlongである場合、単一ノードのスペースオーバーヘッドは64ビットコンピューターで3longから4longになり、33％になるようです。スペースの増加。

これは本当ですか？

出現回数が偶数の 1 つの数値を除いて、各数値の出現回数が奇数である配列が与えられます。偶数の出現数を見つけます。

例えば

出力は次のようになります。

制約事項は次のとおりです。

1. 数値が範囲外です。
2. その場で行います。
3. 必要な時間の計算量は O(N) です。
4. 配列には負の数が含まれる場合があります。
5. 配列はソートされていません。

上記の制約により、比較ベースのソート、カウントソート、BST、ハッシュ、ブルートフォースなど、私の考えはすべて失敗しました。

知りたいのですが、XORing はここで機能しますか? はいの場合、どのように？

いくつかのSO 投稿を通過した後、エラトステネスのふるいが素数を生成する最良かつ最速の方法であることがわかりました。

と という 2 つの数値の間の素数を生成したいと考えていaますb。

私の知る限り、Sieveの方法では、空間の複雑さはO(b)です。

PS: 必要なスペースを削減できるかどうかわからないので、Theta ではなく Big-O を書きました。

エラトステネスの篩で空間の複雑さを減らすことはできますか?