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

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である理由私は理解して考えます？

2016-10-13 Bossrevz

まだ行列全体をメモリに格納する必要があるので、O（n^2）です。 – Rob

適切な書式設定を使用してください... "i = 0からsize-1までのMakeMatrix（size）A = malloc（sizesizesize（int））A [i、i] = 0 return A"はかなり読めません。 – luk32

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

2016-10-13 00:09:21

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

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

。

2016-10-13 00:40:26 displayName

答えて