問題タブ [space-complexity]

多くのシステムでは、一定のスペースが必要head.reverseですが、リストのサイズに比例したスペースが必要です。last

そのような変換を実行するシステムはありますか? 同様にreverse.take n.reverse？

編集: 質問を拡張したいと思います: 私は具体的な変換の後ではなく、むしろこの目的のための最適化の後です。

ここのストレージでの会社の毎日の平均成長率を計算する必要がありますが、正しい方法はどれでしょうか? Google 翻訳を使用して申し訳ありません。=)

ストレージに使用されるスペース:

PHPでの私のコード:

私の結果は次のとおりです: -5194.6666666667、それは間違っていますか?

n 個のレコードに 1 から k の範囲のキーがあるとします。

• レコードを O(n+k) 時間でソートするアルゴリズムを書きます。
• 入力配列の外側で O(k) ストレージを使用できます。
• あなたのアルゴリズムは安定していますか？

カウントソートを使用すると、O（n + k）時間で実行でき、安定していますが、適切ではありません。
k=2 の場合はその場で実行できますが、安定していません (k=0 と k=1 の配列のインデックスを維持するために 2 つの変数を使用します)
。

この機能を可能な限り最適化 (スペースと時間の複雑さを軽減) します。

私はこの特定の問題AIBOHPを行っていて、1 から始まる長さ i の部分文字列の末尾をチェックすることに基づく dp アプローチを使用しました。私の時間の複雑さは O(n^2) で問題ありませんが、スペースが多すぎるため、私はdp サイズが 6100*6100 になる可能性があるため、動的に宣言している場合は RTE を取得し、グローバル静的として宣言している場合は TLE を取得しています。この目的のために以下のコードを最適化する方法についての提案。

問題文は次のとおりです。

私のコードは次のとおりです。

Pythonでこの階乗関数の空間複雑度はどうあるべきですか?

C のような他の言語でのこの同じ考え方は、O(1) 空間の複雑さをもたらしますが、この例では、range(2,n+1) は O(n) 空間の複雑さの空間複雑さをもたらしますか?

nノードと高さを備えた完全にバランスの取れたバイナリ ツリーで機能する再帰関数がlog(n)あり、ツリーのルートで以下の関数を呼び出すとします。

配列を長さlog(n)とします (ツリーのパスに沿って値を格納します)。再帰呼び出しスタックが max height になることはわかっていますlog(n)。Java の「値渡し」の性質と Java ガベージ コレクションが時間と空間の複雑さにどのように影響するのか、私にはよくわかりません。

1) 配列を再帰呼び出しに渡す時間の複雑さは? Java が「値渡し」の場合、各再帰呼び出しはO(log(n))、関数の実行を開始する前に配列をコピーするだけで済みますか?

2) これらの配列のコピーがメモリ内で一度にいくつ浮遊するかの上限は? 私の傾向は言うことO(log(n))です。それは空間の複雑さが であることを意味しますO(log(n)log(n))か? O(log(n))「スペースの複雑さは、アルゴリズムが再帰O(log(n))回数を繰り返し、パスパラメーターがO(log(n))再帰中にスペースで1回だけ割り当てられるためです」という本を読んだことがあります。