時間複雜度和空間複雜度，如何計算空間複雜度

對於MakeMatrix，顯示T（n）是O（n）和S（n）是O（n^2），它創建一個方形矩陣並僅設置對角線元素歸零。（無視時間的malloc）時間複雜度和空間複雜度，如何計算空間複雜度

MakeMatrix(size): 

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

我想我明白爲什麼T（n）是線性爲O（n）因爲只有1 for循環中，但爲什麼空間複雜度是O（N^2）？

2016-10-13 Bossrevz

因爲你仍然必須將整個矩陣存儲在內存中，所以O（n^2）。 – Rob

請使用適當的格式...「我從0到大小-1 A [i，i] = 0返回A」的MakeMatrix（size）A = malloc（sizesizesizeof（int））是非常不可讀的。 – luk32

您分配size * size * sizeof(int)。在我看來很明顯，尺寸*尺寸使得空間複雜度爲n^2。空間複雜性意味着您需要多少內存，基於輸入的大小。這裏是size * size。

2016-10-13 00:09:21

元素的大小Ñ的矩陣的數量是^Ñ2。

如果int的大小是4字節，那麼在malloc調用中，您將劃分出大小*大小* 4字節。因此空間需求是二次的。

即使你迭代僅大小元素（即對角線元素只），但你已經保留所有大小元素的空間。

2016-10-13 00:40:26 displayName

回答