시간 복잡도 및 공간 복잡성, 공간 복잡성을 계산하는 방법

Question

ShowMatrix의 경우 T (n)은 O 0으로. (malloc에 ​​대한 무시 시간)

MakeMatrix(size): 

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

(n은^2) 나는 단지 1 루프가있는 한 나는 T는 (N) (N) 선형 O 이유를 이해할 수 있다고 생각하지만, 왜 공간 복잡도가 O 것 ?

Answer 1

size * size * sizeof(int)을 할당합니다. 크기 * 크기가 공간 복잡성을 복잡하게 만드는 것은 꽤 분명합니다. n^2. 공간 복잡성은 입력 크기에 따라 필요한 메모리 양을 의미합니다. 여기는 size * size입니다.

Answer 2

크기 N의 행렬의 요소 수는 N ²이다.

int의 크기가 4 바이트이면 malloc 호출에서 크기 * 크기 * 4 바이트를 조각합니다. 따라서 공간 요구 사항은 2 차입니다. 당신이 요소 (즉, 대각선 요소 만), 아직 모든 크기 ² 요소에 대한 공간을 예약 한 경우에만 크기 반복 되더라도

.