algorithm - 時間複雑度と空間複雑度の関係

Question

O( n )の時間複雑度を持つアルゴリズムは、 O( n ² ) またはそれ以上の空間複雑度を持つことができますか?

Answer 1

X単位のスペースを書き込むにはOmega(X)時間がかかるため、スペースの複雑さは時間の複雑さを超えることはできません。

Answer 2

have a look at the DSPACE and DTIME groups, which indicate what algorithm can be done in which time/space complexity, and the relationship between groups.

all algorithms that use O(n) time are in the group DTIME(n).
all algorithms that use O(n^2) space, are in the group DSPACE(n^2).
since DTIME(n) <= NTIME(n) <= DSPACE(n) < DSPACE(n^2), so every algorithm that is O(n) time, is also O(n^2) space.

Answer 3

すべての O(n) 関数は自明に O(n ² ) であるため (たとえば、Big O 記法に関するウィキペディアを参照)、答えは「はい」です。

Answer 4

Big-O 表記法は上限を扱います。技術的に言えば、アルゴリズムは f(n) よりも漸近的に速く成長するすべての g(n) に対して O( g(n) ) であるため、アルゴリズムが O(n) である場合は、 O(n^2) および O(n^99) です。

Little-o 記法は、今夜の上限、つまり、f(n) よりも速く成長する最も速く成長しない関数のセットを扱います。したがって、f(n) が o(n^2) であると言うのは有効ではありません。

編集（コメントに答える）：

アルゴリズム A が与えられ、A が O(n^2) であると確実に伝えられた場合、A が O(n) (または何でも) である可能性がありますが、自分自身を見つけるために A を分析する必要があります。逆に、A が o(n^2) であると確実に伝えられた場合、それは O(n) ではありません。

Answer 5

おそらくあなたが聞きたいと思っていた質問に答えるために: 一般に、アカウンティングは、特定の量のメモリを割り当てるのに比例した時間がかかるようになっています。なんで？実際には、メモリを使用する前に何かを初期化する必要があります。

代わりに、すべてのメモリが事前に初期化されていると仮定すると、プロシージャがメモリ全体に書き込みを行うと、そうはなりません。後でメモリをクリーンアップする必要があります...

実際には、アルゴリズム分析で使用されるさまざまなプロセッサ モデルがあります。必要に応じて、「事前にゼロ化されたメモリは無料で、自分でクリーンアップする必要はありません」というモデルを指定できます。これにより、メモリをまばらに使用するアルゴリズムに対して別のメトリックが生成されます。ただし、実際にはメモリ割り当てとガベージ コレクションは無料ではないため、このメトリックは実際的な関連性が限られています。