問題タブ [space-complexity]
For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.
recursion - nビット文字列を生成するための分割統治アルゴリズム？
誰かがnビット文字列（すべての可能な組み合わせ）を生成する方法を教えてもらえますか？つまり、分割統治法を使用して0から2^n-1までのビットを数えます。
次のアルゴリズムでこれを行うことができましたが、空間の複雑さと時間の複雑さはO（2 ^ n）です。誰かが私に（分割統治法を使用して）これよりも少ないスペースを必要とするより良いアルゴリズムを教えてもらえますか？
java - QuickSort が O(log(n)) 余分なスペースを使用するのはなぜですか?
以下のクイックソートアルゴリズムを実装しました。オンラインで、O（log（n））のスペース要件があることを読みました。これはなぜですか？余分なデータ構造を作成していません。
私の再帰がスタック上の余分なスペースを使用するためですか? この場合、再帰的ではなく（反復的にするのではなく）少ないメモリでそれを行うことは可能ですか？
complexity-theory - 時間と空間の複雑さを前置する中置
オペランド スタックと演算子スタックを使用して中置記法から前置記法に変換する Java プログラムの作成に取り組んでいます。ここの一番上の回答の疑似コードに基づいて、機能するコンバーターを実装しました。
ただし、現在、上記のアルゴリズムの時間と空間の複雑さを解決しようとしています。
スペースの複雑さは O(n) でなければならないと思います。なぜなら、それらの間で共有される入力を格納する 2 つのスタックしかないからです。
時間の複雑さについて考えると、完全にはわかりませんが、各サブパートをインフィックスからプレフィックスに変換する必要があるため、O(n^2) ですか? この部分についてはよくわかりません。
基本的に私の質問は次のとおりです:私の空間複雑度の結果は正しいですか?アルゴリズムの時間複雑度はどれくらいですか?
どうもありがとう！
編集: これはアルゴリズムの擬似コードです:
algorithm - O（1）補助記憶スペースを使用してバイナリツリー内のすべてのノードを削除しますか？
二分木のすべてのノードを削除するための標準的なアルゴリズムは、これらの線に沿ったノードのポストオーダートラバーサルを使用します。
このアルゴリズムは、再帰呼び出し中にスタックフレームを格納するために必要なスペースのため、O（h）補助記憶スペースを使用します。hはツリーの高さです。ただし、すべてのノードが1回だけアクセスされるため、時間O（n）で実行されます。
ランタイムを犠牲にすることなく、O（1）補助記憶域のみを使用してバイナリツリー内のすべてのノードを削除するアルゴリズムはありますか？
language-agnostic - スペースの複雑さの混乱
一般的に空間の複雑さを分析することについて少し混乱しています。「アルゴリズムによって占有される余分なスペース」の意味がわかりません。1 のスペースとしてカウントされるのは何ですか? ここの例では
スペースの複雑さは O(n) で、配列サイズが n のためだと推測しています。
しかし、ヒープソートのようなものでは、O(1) かかります。インプレース ヒープソートにもサイズ n (n は入力のサイズ) の配列が必要ではないでしょうか? それとも、入力がすでに配列にあると想定していますか? なぜヒープソートの空間複雑度は O(1) なのですか?
ありがとう！
machine-learning - EM アルゴリズムの計算量はどれくらいですか?
一般的に、より具体的には、ベルヌーイ混合モデル (別名、潜在クラス分析) の場合です。
complexity-theory - アルゴリズムの複雑さを測定するときに T (1) を見つけるにはどうすればよいですか?
質問 01: アルゴリズムの複雑さを測定するとき、T (1) を見つけるにはどうすればよいですか?
たとえば、私はこのアルゴリズムを持っています
T(1) を見つけるにはどうすればよいですか?
質問2 ：
この式の「1」の意味は何ですか
心から
java - マージソートのスペース効率の良い実装はありますか?
この作業バージョンのmergesortをコード化しました：
ただし、お気づきの場合は、親配列の特定の部分のコピーである新しい配列を作成する copyOfRange 関数を使用します。これよりスペース効率の良いマージソート実装が Java にありますか?
c - パズル: 誰がゲームに勝つ?
子供たちのグループがリングを形成します。最初の子が選択され、その子から時計回りにカウントを開始し、固定数 (ゲームの開始時に与えられる n) に達するまでカウントします。カウントが n に達すると、n 番目のスポットの子が削除されます。ゲームは次の子から再開し、残りの子が 1 人になるまでこのプロセスが続きます。最後まで残った子の位置を出力することが目的です。
例えば、子供が10人で固定数nが6の場合、最後まで残った最後の子供の位置は3になります。
この問題を解決するためのより良いプログラム アルゴリズムはありますか?
PS配列やその他のデータ構造を使用してこれを簡単に実行できることを私は知っています。最善の戦略、できれば数学的アプローチが欲しいだけです。
java - ifステートメントの複雑さ
ifステートメントに従うことの複雑さを疑問に思っています
VS
そしてisTrueは次のように定義されます
私が考えていたのは、ケース2ではequalsの追加の比較が必要なため、の複雑さif (isTrue())はそれよりも低いということです。if(isTrue()==true)
スペースの複雑さはどうですか？
別の考えはありますか？