問題タブ [space-complexity]

そう; 私は SICP を使って作業しようとしている愛好家です (無料です! )。最初の章には、アメリカの硬貨で両替する方法を数えるための手順の例があります。(change-maker 100) => 292. 次のように実装されています。

ともかく; これはツリー再帰手順であり、作成者は同じ問題 (つまり、固定スペース) を解決するための反復手順を見つけることを「課題として残します」。私はこれを理解したり、イライラした後に答えを見つけたりすることができませんでした。それは私の側の脳のおならなのか、それとも作者が私をからかっているのか疑問に思っています.

私が行っているこのプログラムは、ソーシャル ネットワークに関するもので、ユーザーとそのプロファイルが存在することを意味します。プロファイル構造はUserProfile.

現在、考えられるさまざまなグラフの実装があり、最適なものを使用しているとは思いません。私はGraph構造を持っており、内部には type のリンクされたリストへのポインタがありますVertex。各Vertex要素には、値、次Vertexへのポインター、および type のリンクされたリストへのポインターがありますEdge。各Edge要素には、値 (重みと必要なものを定義できるようにするため)、次Edgeへのポインター、およびVertex所有者へのポインターがあります。

(CSV スタイルで) 処理してグラフに挿入するデータを含む 2 つのサンプル ファイルがあります。1 つ目はユーザー データ (1 行に 1 人のユーザー) です。2 つ目はユーザー関係 (グラフ用) です。最初のファイルはすぐにグラフに挿入されます。これは、私が常に先頭に挿入するためです。約 18000 人のユーザーがいます。2 番目のファイルは時間がかかりますが、それでも先頭にエッジを挿入します。このファイルには約 520000 行のユーザー関係が含まれており、グラフに挿入するのに 13 ～ 15 分かかります。簡単なテストを行ったところ、データの読み取りは非常に速く、瞬時に行われました。問題は挿入にあります。

この問題は、頂点のリンク リストを使用して実装されたグラフがあるために発生します。リレーションを挿入する必要があるたびに、それらをリンクできるように 2 つの頂点を検索する必要があります。これが問題です...〜520000のリレーションに対してこれを行うには、しばらく時間がかかります。

これをどのように解決すればよいですか？

解決策 1)グラフ (頂点部分) をリンク リストではなく配列として実装することを勧める人がいます。このようにして、すべての頂点に直接アクセスできるようになり、挿入が大幅に減少する可能性があります。しかし、配列に [18000] 個の要素を割り当てるという考えは好きではありません。これはどれくらい実用的ですか？私のサンプル データは ~18000 ですが、それよりも少ない場合や多い場合はどうすればよいですか? リンクされたリストのアプローチにはその柔軟性があり、メモリがある限り、好きなサイズにすることができます。しかし、配列はそうではありません。そのような状況をどのように処理しますか? あなたの提案は何ですか？

リンクされたリストの使用は、空間の複雑さには適していますが、時間の複雑さには適していません。また、配列の使用は時間の複雑さには適していますが、空間の複雑さには適していません。

このソリューションについて何か考えはありますか？

解決策 2)このプロジェクトでは、名前インデックスと ID インデックスに基づいてすばやく検索できる、ある種のデータ構造も必要です。このために、ハッシュ テーブルを使用することにしました。私のテーブルは、衝突解決として個別の連鎖を使用して実装されており、負荷係数が 0.70 に達すると、通常はテーブルを再作成します。次のテーブル サイズは、このLinkに基づいています。

現在、両方のハッシュ テーブルはUserProfile、ユーザー プロファイル自体を複製する代わりに、へのポインターを保持しています。それはばかげています。データを変更するには 3 つの変更が必要であり、そのようにするのは本当にばかげています。そのため、ポインターを に保存するだけUserProfileです。同じユーザー プロファイル ポインターも、各 Graph に値として保存されますVertex。

したがって、1 つのグラフと 2 つのハッシュ テーブルの 3 つのデータ構造があり、それらのすべてが同じ正確な を指していUserProfileます。グラフ構造は、最短パスなどを見つける目的に役立ちますが、ハッシュ テーブルは名前と ID によるクイック インデックスとして機能します。

グラフの問題を解決するために考えているのは、ハッシュ テーブルの値を に向けるのではなくUserProfile、対応する に向けることVertexです。それはまだポインターであり、使用されるスペースは多かれ少なかれありません。ポイントするものを変更するだけです。

このように、必要な各頂点を簡単かつ迅速に検索して、それらをリンクすることができます。これにより、~520000 のリレーションがすばやく挿入されます。

このソリューションを考えたのは、既にハッシュ テーブルがあり、それらが必要なためです。それなら、ユーザー プロファイルの代わりにグラフ頂点のインデックス作成にそれらを利用してみませんか? それは基本的に同じことです。私はまだUserProfile非常に迅速にアクセスできます.VertexUserProfile

しかし、最初のソリューションに対するこの 2 番目のソリューションの短所はありますか? それとも、最初のソリューションの長所と短所を圧倒する長所だけですか?

その他の解決策) 他に解決策があれば、私はすべて耳にします。しかし、前の 2 に対するそのソリューションの長所と短所を説明してください。私は今、これで無駄にしている時間があまりありません。このプロジェクトを進める必要があるので、そのようなことをしている場合変更する場合、何を変更する必要があるか、それが本当に正しいかどうかを正確に理解する必要があります。

これを読んで居眠りしてブラウザを閉じた人がいないことを願っています。しかし、私は本当にこれについて何をすべきかを決める必要があり、私は本当に変更を加える必要があります.

PS:私が提案した解決策に答えるときは、私と同じようにそれらを列挙してください。そうすれば、あなたが何を話しているのかが正確にわかり、自分自身をこれまで以上に混乱させないようにすることができます。

次の質問に出くわしました。

n 個の要素の配列とk < nの整数kが与えられます。要素 { a ₀ ... a _k } および { a _{k +1} ... a _n } は既にソートされています。O( n ) 時間と O(1) 空間でソートするアルゴリズムを与えてください。

O( n ) 時間と O(1) 空間で実行できるようには思えません。問題は、マージソートのマージステップをインプレースで行う方法を実際に尋ねているようです。可能であれば、マージソートはそのように実装されませんか? 私は自分自身を納得させることができず、意見が必要です。

これは非常に有名な多国籍企業から私に尋ねられた質問です。質問は次のとおりです...

0と1の2DN*N配列を入力します。A（i、j）= 1の場合、i番目の行とj番目の列に対応するすべての値は1になります。すでに1がある場合は、1のままです。

例として、配列がある場合

次のように出力を取得する必要があります

入力行列はまばらに入力されています。

これはO（N ^ 2）未満で可能ですか？

別の条件で、追加のスペースが提供されていません。スペース<=O（N）を使用して複雑さを実現する方法があるかどうかを知りたいです。

PS：O（N * N）の複雑さを与える答えは必要ありません。これは宿題の問題ではありません。私は多くのことを試みましたが、適切な解決策を得ることができず、ここでいくつかのアイデアを得ることができると思いました。複雑さのために印刷を脇に置いておきます

私の大まかなアイデアは、通過する要素の数を動的に排除して、それらを約2N程度に制限することでした。しかし、私は適切なアイデアを得ることができませんでした。

さまざまな入力文字列に対して、アルゴリズムが同じ数の 0 と 1 を持つバイナリ文字列を生成するとします。2 つの異なる入力文字列の出力は、同じである場合と異なる場合があります。アルゴリズムのスペースの複雑さについて何か言えますか?

みなさん、こんにちは。以下のアルゴリズムを読んで、バイナリ検索ツリーで2つのノードの最も低い共通の祖先を見つけます。

上記の関数は、n1がn2よりも小さいことを前提としていることに注意してください。時間計算量：O（n）空間計算量：O（1）

このアルゴリズムは再帰的です。再帰的な関数呼び出しを呼び出すと、関数の引数と他の関連するレジスタがスタックにプッシュされるため、余分なスペースが必要になります。一方、再帰的な深さは、のサイズまたは高さに関連します。ツリー、たとえばnは、O（n）である方が理にかなっていますか？

ここで説明してくれてありがとう！

スタックオーバーフロー。ここには時間計算量に関する優れたリソースがいくつかありますが、これまでのところ、それらを使用してこの空間計算量の質問に答えることはできませんでした。それで：

最初のn個の素数を掛け合わせる場合、答えを格納するためにどのようなスペースが必要になりますか？たとえば、最初の1000個の素数を乗算し、結果の数（大きいものではありますが整数）を格納します。n-squaredまたはlog（n）スペースが必要ですか？

本当にありがとう！

質問があります：

オブジェクトを含む配列"S"がありnます。また、各オブジェクトにはmフィールドがあります。のような別の配列にそれらのいくつかを保存したい"Q"。この簡単な方法のスペースの複雑さはO(|Q|)?

一般的な木を二分木に変換するときの時間と空間の複雑さは?!

ありがとう

ブルームフィルターを使用して、スペースの最適化を行います。cassandraフレームワークには、ブルームフィルターの実装もあります。しかし、詳細には、このスペースの最適化はどのように達成されますか？