时间复杂度和空间复杂度，如何计算空间复杂度

问题描述：

对于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

答

您分配size * size * sizeof(int)。在我看来很明显，尺寸*尺寸使得空间复杂度为n^2。空间复杂性意味着您需要多少内存，基于输入的大小。这里是size * size。

答

元素的大小Ñ的矩阵的数量是^Ñ2。

如果int的大小是4字节，那么在malloc调用中，您将划分出大小*大小* 4字节。因此空间需求是二次的。

即使你迭代仅大小元素（即对角线元素只），但你已经保留所有大小元素的空间。