問題タブ [space-complexity]

C1、C2、C3、および C4 がデータの列を表し、N 行のデータがある場合、タブ区切りの値の入力を保存したいと思います。もしそうなら、ハッシュを調べて、C1、C2、C3、C4 の特定の値が存在するかどうかを確認できます。誰かが私に、最悪の場合、これの空間複雑度は N ⁴であると提案しました。なぜそれが真実ではないのかについて、明確な説明を作成する手助けをしたいと思います。

特定のフォルダー内のすべてのファイルとフォルダーの幅優​​先走査を実行するイテレーターを作成しようとしています。私はすでに深さ優先トラバーサルでこれを実行しました。これは、たとえば次のように戻ります。

等

今、私は代わりに幅優先で結果を返すプログラムを作ろうとしています:(またはレベルごとに）

同じ階層に対して。しかし、私はつまずきに遭遇しました。これらを正しい順序で（具体的には逆の順序ではなく）実行したい場合、最終的にO（n）メモリを必要とせずにこのアクションを実行する方法を見つけることができません。nは、ドライブ上のファイル/フォルダーの数です。これは、ある時点でドライブ階層全体をメモリに保持する必要があるように思われるためです。一方、DFSの場合、以前に列挙したすべてのエントリを完全に無視できます。階層内の同じレベル。

だから私の質問は：フォルダをトラバースするためにメモリを使用するための線形よりも優れた方法はありますか？

整数の配列が与えられます。範囲内のすべての数値が配列に存在するように、最大​​範囲を出力する必要があります。番号は任意の順序で存在する可能性があります。たとえば、配列が

ここでは、これらの範囲内のすべての整数が配列に存在する 2 つの (自明ではない) 範囲、つまり [2,8] と [10,12] を見つけます。これらのうち [2,8] は長い方です。したがって、それを出力する必要があります。

この質問をされたとき、並べ替えを使用せずに線形時間でこれを行うように求められました。ハッシュベースの解決策があるのではないかと考えましたが、何も思いつきませんでした。

これが私の解決策の試みです：

この部分で立ち往生しています...いくつの tempanswer[] 配列を使用する必要があるかわかりません。

文字列内の回文数を見つけるために書いたこのコードの空間と時間の複雑さを見つけるのに苦労しています。

私はそれを試してみましたが、これは私が思うことです:
主に 2 つの while ループがあります。外側のものは、文字列の長さ 1 の全長にわたって実行されます。ここに混乱があります。内側の while ループは最初に全長にわたって実行され、次に n-1、次に n-2 など、外側の while ループの反復ごとに実行されます。ということは、私たちの時間計算量は になるということO(n(n-1)) = O(n^2-n) = O(n^2)ですか? そして、スペースの複雑さのために、最初に文字列の長さ+1、次に(長さ+1)-1、(長さ+1)-2などにスペースを割り当てます。checkPalin 関数の場合、O(n/2).
私は面接の準備をしていて、この概念を理解したいと思っています。
ありがとうございました

配列は次のように宣言されていますか：
int array[M]、O(1)スペース内またはO(n)？ここで、Mは固定値です。O(n)それは単一の変数ではなく、配列全体であるため、私には理にかなっています。O(1)でも、サイズが決まっていて変わらないから かもしれないと思います！

Lempel-Ziv-Welch および Huffman 圧縮アルゴリズムの Big O 表記での空間と時間の複雑さは何ですか? グーグルは私を失望させています。

ありがとう、

フランシスコ

Mathematica のCylindricalDecompositionは、Cylindrical Algebraic Decomposition として知られるアルゴリズムを実装しています。Wolfram MathWorld のCylindrical Algebraic Decompositionに関する記事では、このアルゴリズムは「複雑な不等式では計算上実行不可能になる」と述べています。

このステートメントをより正確にすることはできますか? 具体的には、時間と空間は、多変量多項式の変数の次数と数にどのように関係していますか? 時間と空間は他のパラメーターに依存しますか?

私が考えているアルゴは

• サイズ K の MaxHeap を保持する
• 各要素を挿入する
• ヒープがいっぱいの場合は小さい値を削除
• 結局、Kth max は MaxHeap の小さい方です

それは私にO（NlogK）を与えるでしょう。より良いアルゴリズムはありますか？配列をメモリに保存できないため、クイック選択を行うことができません。

ファイル内にコンマで区切られた任意の長さの整数 (または浮動小数点値) の行があります。

ここで、これらの値を読み取り、配列に格納する必要があります。

私の現在の実装は次のようになります。

私はこの実装が好きではありません:

• ファイル全体を使用ifstreamすると、メモリにロードされてから、float []
• 不要な重複があります ( からstd::stringへの変換const char*)

メモリ使用率を最適化する方法は何ですか?

ありがとう！

トップダウン マージ ソートでは、再帰関数は次のように呼び出されます。

この戦略の空間複雑度は O(n) であると教科書に記載されています。一方、再帰をよく見ると、再帰呼び出しで配列へのポインターを渡しています。2 番目に、最下位ノードを親ノードにマージすることにより、トラバーサルの前の順序で再帰が解決されます。そのため、毎回スタック上に O(logn) 個の変数 (またはスタック上に O(log n) 個のフレーム) があります。では、インプレース マージ技術があるにも関わらず、空間の複雑さが O(n) であるのはどうしてでしょうか?