時間の複雑さと空間の複雑さ、空間の複雑さの計算方法

Question

ShowMatrixの場合、T（n）はO（n）、S（n^2）は正方行列を作成し、対角要素ゼロにする。 （malloc関数を無視時間）

MakeMatrix(size): 

A = malloc(size * size * sizeof(int)) 
for i from 0 to size -1 
A[i,i] =0 
return A 

私はそこだけ1 forループがあるが、なぜ宇宙の複雑さはO（N^2）になるとT（n）は（n）の線形Oである理由私は理解して考えます？

Answer 1

size * size * sizeof(int)を割り当てます。サイズ*サイズが空間の複雑さをn^2にするのはかなり明らかです。スペースの複雑さは、入力のサイズに基づいて、どれくらいのメモリが必要かを意味します。ここはsize * sizeです。

Answer 2

サイズNの行列の要素の数は、Nあります。

intのサイズが4バイトの場合、malloc呼び出しでは、サイズ*サイズ* 4バイトを切り出しています。したがって、必要なスペースは2次です。あなたは要素（すなわち、対角要素のみ）、まだあなたはすべてのサイズ要素のためのスペースを予約しているだけサイズを反復しているにもかかわらず

。