問題タブ [space-complexity]

したがって、anxnゲームボードがあり、ボード上の各場所には整数があります。プレーヤー1は行1から番号を選択し、プレーヤー2は行2から番号を選択し、行がなくなるまで交互に表示します。次に、それらはすべての数字を合計し、合計が所定の合計Sに等しい場合はプレーヤー1が勝ち、そうでない場合はプレーヤー2が勝ちます。特定のボードと合計（B、S）に対するプレーヤー1の勝利戦略は、プレーヤー2が何をしてもプレーヤー1が勝つことができるかどうかです。この問題がPSpaceで完全であることを示したい

したがって、最初に、それがPSpaceにあることを示す必要があります。これは、移動の総数がボードのサイズ（n ^ 2）によって制限されるため、非常に簡単だと思います。

PSpaceが難しいことを示すのに行き詰まっていますが、QSATから削減する必要があることはわかっていますが、その方法がわかりません。誰かが助けることができますか？

編集：実際、私はQSATから削減する必要があることを知りませんが、周りを検索した後、QSATが最も可能性の高い候補であるように見えます。他の多くの2人用ゲーム（地理が最も顕著な例です）はQSATから減少しているので、これも必要だと思いました。ただし、これについて間違っている場合は、遠慮なく訂正してください。

この質問は私には単純に見えますが、私が正しい方向に進んでいるかどうかを確認したかっただけです。

n=1のときと言うのと同じくらい簡単ですか??

このマージソートの実装を例として取り上げましょう

a）このマージソートの時間計算量はですO(n lg(n))。（1）と（2）を並列化すると、実用的な利益が得られますか？理論的には、それらを並列化した後も、で終わるように見えますO(n lg(n))。しかし、実際に私たちは何か利益を得ることができますか？

b）このマージソートのスペースの複雑さはここにありO(n)ます。ただし、リンクリストを使用してインプレースマージソートを実行することを選択した場合（配列で合理的に実行できるかどうかはわかりません）O(lg(n))、再帰スタックのフレームサイズを考慮する必要があるため、スペースが複雑になりますか？O(lg(n))64を超えることはできないので、定数として扱うことはできますか？私はこれをいくつかの場所で誤解したかもしれません。64の重要性は正確には何ですか？

c）ソートアルゴリズムの比較-Cprogramming.comによると、マージソートにはリンクリストを使用した一定のスペースが必要です。どのように？O(lg(n))彼らは一定に扱いましたか？

d）より明確にするために追加されました。スペースの複雑さの計算では、入力配列またはリストがすでにメモリにあると想定するのは公平ですか？複雑さの計算を行うときは、入力によってすでに使用されているスペースに加えて、必要になる「余分な」スペースを常に計算します。そうしないと、スペースの複雑さが常にO(n)悪化します。

n 個の要素を挿入した後、スキップ リストによって使用されると予想されるスペースはどれくらいですか?

最悪の場合、スペースの消費量が際限なく増える可能性があると予想しています。

ウィキペディアには「スペース O(n)」とあります。

これはどのように証明できますか？

以下は2つのスニペットです。プログラム間の唯一の違いは、すぐに一方break to returnと他方が異なることに注意してください。returnメソッド内に1つの出口点を設けることは、優れた設計手法であることを理解しています。しかし、ここではデザインについて心配していません。使用料を追加で支払う場合break、どのくらいの追加の計算/メモリ/クロックサイクルを支払いますか？

プログラム1：

プログラム2：

私はインタビューで、pallindromeのチェックの問題を解決するための効率的な方法を尋ねられました。

今、私は2つのことを行うことができます：

1. i=0からi=n / 2まで開始し、i番目とn番目の文字を比較して等しくなります。
2. 再帰を使用して、最初と最後が同じで、文字列の残りの部分がpallindromeであるかどうかを確認できます。

2番目は再帰的です。私の質問は、アルゴリズムの再帰バージョンと非再帰バージョンのスペースの複雑さの違いは何ですか？

0 と 1 で満たされたサイズ nxm の行列が与えられた場合

例えば：

1 1 0 1 0

0 0 0 0 0

0 1 0 0 0

1 0 1 1 0

行列の (i,j) に 1 がある場合、列 j と行 i を 1 で埋めます

つまり、次のようになります。

1 1 1 1 1

1 1 1 1 0

1 1 1 1 1

1 1 1 1 1

必要な複雑さ: O(n*m) 時間と O(1) スペース

注: マトリックス エントリには「0」または「1」以外を格納することはできません

上記は、マイクロソフト インタビューの質問です。

ここで2時間考えました。手がかりはあるが、これ以上先に進めない。

Ok。この問題の最初の重要な部分は、Even using a straight forward brute-force way簡単には解決できないということです。

2 つのループを使用してマトリックス内のすべてのセルを反復処理し、それに応じて行と列を変更すると、結果のマトリックスは元のマトリックスに基づく必要があるため、実行できません。

たとえば、 が表示されている場合、すべてをにa[0][0] == 1変更することはできません。これは、 には元々 0 がないため影響します。row 0column 01row 1row 1

2 番目に気付いたのは、行rに のみが含まれ0、列cに のみが含まれる場合、 ;0でa[r][c]なければならないということです。0このパターンにない他のポジションは1.

a[r][c]次に、別の質問があります。そのような行と列が見つかった場合、対応するセルをspecialすでに 0 としてマークするにはどうすればよいですか。

私の直感は、これに対してある種のビット操作を使用する必要があるということです。または、必要な複雑さを満たすために、次のようなことをしなければなりませんAfter I take care of a[i][j], I should then proceed to deal with a[i+1][j+1], instead of scan row by row or column by column。

時間の複雑さを考慮しない力ずくの場合でも、他の条件では解決できません。

誰にも手がかりがありますか？

解決策: Java バージョン

@japreiss はこの質問に答えており、彼/彼女の答えは賢明で正しいものです。彼のコードは Python で書かれており、今は Java バージョンを提供しています。クレジットはすべて @japreiss に送られます

これは私には少し混乱します。制約が次の場合、特定の問題を解決するための私のアプローチはどうあるべきですか。

1）余分なスペースを使用しない：例：特定の配列を並べ替える場合、いくつかの方法があります。スワップを続けるバブルソート（ループのみ、再帰なし）。余計なスペースを使わないということだと思います。再帰を使用して要素を並べ替えるとどうなりますか。「余分なスペースを使用しない」と同じですか、それとも使用されたスタックがアルゴリズムのスペースの複雑さでカウントされますか？

2）O（1）スペースの場合：O（1）スペースの意味は何ですか？それは一定のスペースを意味しますか？一定のスペースの場合は、次の場合についてコメントしてください。

a）3番目の変数を使用してバブルソートでスワップしている場合。それは余分なスペースではなく、入力のサイズに依存しないため、一定のスペースにあります。

b）さらに、自然数に適用されるカウントソートを使用している場合、実際には総数に比例するスペースの量を必要としないので、定数スペースO（1）にあると見なしますか？

違いがあれば説明してください。ありがとう

私は答えを得る前にこの質問が閉じられる危険を冒していますが、私は本当に答えを知りたいです。だからここに行きます。

私は現在、アルゴリズムを学ぼうとしています。それ自体は理解し始めていますが、関連することはできません。

時間計算量と空間計算量を理解しています。擬似コードに基づくいくつかの並べ替えアルゴリズムも理解しています

次のような並べ替えアルゴリズム

1. バブルソート
2. 挿入ソート
3. 選択ソート
4. クイックソート
5. マージソート
6. ヒープソート（いくらか）

また、ベストケースとワーストケースのシナリオも認識しています（平均的なケースはそれほど多くありません）。

いくつかのオンライン関連参照

• 上記のすべてをグラフィカルに表示する素敵な場所。
• これも私に良い理解を与えてくれました。

しかし、私の質問は-これらのソートアルゴリズムが実装されている実際の世界の例を誰かに教えてもらえますか？

サフィックスツリーが拡張サフィックスアレイよりも優れている場合を知りたいだけです。

「サフィックス ツリーを強化されたサフィックス アレイに置き換える」を読んだ後、サフィックス ツリーを使用する理由がわかりません。一部のメソッドは複雑になる可能性がありますが、接尾辞配列を使用してすべてを行うことができ、接尾辞ツリーで実行できることと同じ時間の複雑さを必要としますが、メモリは少なくて済みます。

ある調査では、接尾辞配列の方がキャッシュにやさしく、キャッシュミスが少ないため、より高速であることが示されました (そのため、キャッシュは再帰ツリー構造よりも配列の使用をはるかによく予測できます)。

では、サフィックス配列よりもサフィックスツリーを選択する理由を知っている人はいますか?

編集 OK、もっと知っているなら教えてください、これまでのところ:

• Suffixarray はオンライン構築を許可しません
• 一部のパターン マッチング アルゴリズムは、Suffixtree で高速に実行されます
• (追加) オンライン構築のため、hd a に保存し、既存の suffixtree を拡大することができます。SSD を使用する場合は、静かで高速である必要があります。