Space 复杂性 - 涉及数组的各种案例函数

Question

在这里我写了一些不同的函数案例，它们以数组作为输入我需要帮助来确定我的答案背后的推理是否正确（我在我遇到困难的案例上打了问号）

案例 1:

algo(arr[],n){
  //does nothing
}

Space = (0) + 0 = O(1)

辅助Space=0=O(1)

（原因：分配给输入的存储尚未处理并且函数内部没有声明临时存储）

案例2：

algo(arr[],n){
   int i;
}

Space = (0) + 1 = O(1)

辅助Space=1=O(1)

（原因：尚未处理为输入分配的存储空间，需要为变量 i 提供 1 个临时存储空间）

案例 3：

algo(arr[],n){
   int i;
   for(i=0; i<n ; i++){
    //does nothing
   }
}

Space = (1) + 1 = O(1)

辅助Space=1=O(1)

（原因：变量 n 的存储正在处理中，变量 i 需要 1 个临时存储）

案例4：

其中 arr[] 是大小为 L 的数组，其中 L > n

algo(arr[],n){
   int i;
   for(i=0;i<n;i++){
    arr[i] = i;
   }
}

Space = (1 + n) + 1 = O(n)

辅助Space=1=O(1)

（原因：变量 n 的 1 个存储空间和 arr[0] 的 n 个存储空间......正在处理 arr[n-1] 并且需要变量 i 的 1 个临时存储空间）

案例 5:??

其中 arr[] 是大小为 L 的数组，其中 L > n

algo(arr[],n){               
   arr[n]=n;
}

Space = (1 + 1) + 0 = O(1)

辅助Space=0=O(1)

（原因：正在处理变量 n 的 1 个存储，并且无论 n 的值如何，arr[] 中始终只处理 1 个存储，没有声明临时存储）

案例 6:??

其中 arr[] 是大小为 L 的数组，其中 L > i

algo(arr[],n){
   int i = 1;
  arr[i]=i;
}

Space = (1) + 1 = O(1)

辅助Space=1=O(1)

（原因：arr[] 中始终只处理 1 个存储，它始终位于 arr[i] 中，i 需要 1 个临时存储）

案例 7:??

其中 arr[] 是大小为 L 的数组，其中 L > n

algo(arr[],n){
   int i;
   for(i=0;i<n;i++){
    // does nothing
   }
   arr[n] = n;

}

Space = (1 + 1) + 1 = O(1)

辅助Space=1=O(1)

（原因：正在处理变量 n 的 1 个存储，无论 n 的值如何，arr[] 中始终只处理 1 个存储，为变量 i 声明了 1 个临时存储）

案例 8:??

其中 arr[] 是大小为 L 的数组，其中 L > i

algo(arr[],n){
   int i;
   for(i=0;i<n;i++){
    // does nothing
   }
   i = 1;
   arr[i] = i;

}

Space = (1 + 1) + 1 = O(1)

辅助Space=1=O(1)

（原因：arr[] 中始终只处理 1 个存储，它总是在 arr[i] 中，1 个存储用于正在处理的变量 n，1 个临时存储用于变量 i）

案例 9:

其中 arr1[] 是一个大小为 m

的数组

algo(arr1[],n){
   int arr2[n];
}

Space = (1) + n = O(n)

辅助Space=n=O(n)

（原因：变量 n 的 1 个存储正在处理，arr2[] 需要 n 个临时存储）

案例 10:??

其中 arr1[] 是一个大小为 L 的数组

algo(arr1[],n){
   int m=1;
   int arr2[m];
}

Space = (0) + 1 + m = O(m)

辅助Space=1+m=O(m)

(原因：变量m需要1个临时存储，arr2[]需要m个临时存储)

或

Space = (0) + 1 + 1 = O(1)

辅助Space=1+1=O(1)

（原因：变量 m 需要 1 个临时存储，并且由于 m 是常数，arr2[] 所需的 space 总是某个常数 c）

案例 11:??

algo(arr1[],n){
   int i;
   int m=10;
   int arr2[m];

   for(i=0;i<m;i++){
     arr2[i]= i;
   }   

}

Space = (0) + 1 + 1 + 1 = O(1)

辅助Space=1+1+1=O(1)

（原因：变量 m 需要 1 个临时存储空间，变量 i 需要 1 个临时存储空间，并且由于 m 是常数，arr2[] 所需的 space 总是某个常数 c）

案例 12:

其中 arr1[] 是一个大小为 L 的数组，其中 L > n 然后 arr2[] 是一个大小为 K 的数组，其中 K > m

algo(arr1[],n, arr2[], m){
   int i;

   for(i=0;i<n;i++){
     arr1[i]= i;
   }   

   for(i=0;i<m;i++){
     arr2[i]= i;
   }   

}

Space = (1 + n + 1 + m) + 1 = O(n + m)

辅助Space=1=O(1)

（原因：正在处理的 var n 和 m 需要 2 个存储空间，arr1 需要 n 个存储空间，arr2 需要 m 个存储空间，var i 需要 1 个存储空间）

案例 13:??

其中 arr1[] 是大小为 L 且 L > n

的数组

algo(arr1[],n){
   int i;
   int m=10;
   int arr2[m];

   for(i=0;i<n;i++){
     arr1[i]= i;
   }   

   for(i=0;i<m;i++){
     arr2[i]= i;
   }   

}

Space = (1 + n) + 1 + 1 + 1 = O(n)

辅助Space=1+1+1=O(1)

(原因：变量 i 和 m 需要 2 spaces，arr2 需要常量 m space，var n 和 n [=215 需要 1 space =] 正在为 arr1)

案例 14:

 algo(arr1[],n){

   int arr2[10];

 }

Space = (0) + 1 = O(1)

辅助Space=1=O(1)

（原因：调用函数时总是需要10 spaces来声明arr2）

Answer 1

如果您使用的是一个已经分配的数组，例如 INTEGERS，它将具有以下大小； sizeof(int)*n，这里的 n 是所述数组的大小。如果按值传递它，您将拥有它的本地副本，如果您按引用或指针传递它，则不会复制它。将元素放入数组或修改其元素不会改变其已分配的大小，您将具有相同的 space 复杂度。

声明固定数量的变量也不会改变 space 复杂度，注意这里我说的是 space 复杂度而不是实际的 space。所以一次回答你的问题;

如果你修改一个已经存在的数组的元素，你不会改变 space 复杂度（即使它是空的，它已经分配了 sizeof(elementtype)* element_number space）。
如果您之前有 O(n) space，然后您创建了一个包含 m 个元素的新数组，您将需要额外的 space 并且您 space 复杂将是 O(m+n)（以较大者为准）。
固定数量的变量不会影响 space 复杂度，只会影响您使用的总 space。

Answer 2

好的，我不会一一解决每个案例，而是会尝试帮助您理解 space 复杂性，这可能会解答您所有的疑惑。

Space complexity of a method is defined as how much amount of extra space your method uses, as the input grows, to run an algorithm of your choice.

algo(arr[],n){
}

algo(arr1[],n, arr2[], m){
}

在上面的方法定义中-

如果我只对参数变量和一些额外的变量进行操作，比如-

int a=1,b=10,c=99;

int[] new_array = new int[1000];

int m=1; int[] arr = new int[m];

所有这些仍将被视为 O(1) space 复杂性。如您所见，无论我的输入有多大，变量的数量和大小都不会改变。
如果我声明随输入增长的附加变量，例如-

int[] sum = new int[n];

int[][] sum = new int[n][n];

int[][] sum = new int[n][m];

如您所见，我的数组大小取决于 n 传递给方法。在这里，如果我的输入数组大小恰好是 1000000000，我的方法也将消耗 1000000000 使其成为 O(n) in space.

int[] sum = new int[n]; takes O(n) space since size depends on n

int[][] sum = new int[n][n]; takes O(n²) space since it has n rows and n columns.

int[][] sum = new int[n][m]; takes O(n*m) space since it has n rows and m columns.

int[][] arr = new int[n][];

for(int i=0;i<n;++i){
   arr[i] = new int[i+1];
}

以上代码片段执行以下操作-

声明一个包含 n 行的数组。
将 size/number 列分配给每一行。如果每行的列大小不同，则称为 锯齿状数组。
示例-

1^st 行 - 1 列。

2^nd 行 - 2 列。

3^rd 行 - 3 列。

4^th 行 - 4 列。

依此类推直到

n^th 行 - n 列。

上述代码的space复杂度为O(n²)。原因是因为在渐近符号中，我们更关心 worst case 场景。在这里，不管其他行如何，对于第 n^th 行，我们有 n 列，并且这也会随着输入而增长。

我希望这能让您清楚 space 复杂性。

Space 复杂性 - 涉及数组的各种案例函数

Space complexity- various cases functions involving arrays

arrays

algorithm

big-o

computer-science

space-complexity