對於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) ?
因爲你仍然必須將整個矩陣存儲在內存中,所以O(n^2)。 – Rob
請使用適當的格式...「我從0到大小-1 A [i,i] = 0返回A」的MakeMatrix(size)A = malloc(sizesizesizeof(int))是非常不可讀的。 – luk32