arrays - 空间复杂度-涉及数组的各种情况函数

Question

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

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

空格=（0）+0=O（1）
辅助空间＝0＝O（1）
（原因：分配给输入的存储尚未处理，并且在函数中没有声明临时存储）
案例2：

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

空格=（0）+1=O（1）
辅助空间＝1＝O（1）
（原因：分配给输入的存储尚未处理，需要1个变量i的临时存储）
案例3：

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

间距=（1）+1=O（1）
辅助空间＝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;
   }
}

间距=（1+n）+1=O（n）
辅助空间＝1＝O（1）
（原因：1个存储变量n，n个存储变量arr[0]….arr[n-1]正在工作，需要1个临时存储变量i）
案例5:？?
其中arr[]是l的数组，其中l>n

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

间距=（1+1）+0=O（1）
辅助空间＝0＝O（1）
（原因：正在处理变量n的1个存储，在arr[]中只有1个存储将始终处理，而不管n的值是多少，未声明临时存储）
案例6:？?
其中arr[]是l的数组，其中l>i

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

间距=（1）+1=O（1）
辅助空间＝1＝O（1）
（原因：在arr[]中，只有一个存储始终在arr[i]中工作，而i需要一个临时存储）
案例7:？?
其中arr[]是l的数组，其中l>n

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

}

间距=（1+1）+1=O（1）
辅助空间＝1＝O（1）
（原因：正在处理变量n的1个存储，在arr[]中，不管n的值是多少，只有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;

}

间距=（1+1）+1=O（1）
辅助空间＝1＝O（1）
（原因：arr[]中只有一个存储始终在arr[i]中工作，一个存储用于处理变量n，一个临时存储用于处理变量i）
案例9：
其中arr1[]是m大小的数组

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

间距=（1）+n=O（n）
辅助空间= n = O（n）
（原因：正在处理的变量n需要1个存储，arr2[]需要n个临时存储）
案例10:？?
其中arr1[]是大小为l的数组

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

间距=（0）+1+m=O（m）
辅助空间= 1 + m = O（m）
（原因：变量m需要1个临时存储器，arr2[]需要m个临时存储器）
或
空格=（0）+1+1=O（1）
辅助空间＝1＋1＝O（1）
（原因：变量m需要1个临时存储器，而且由于m是常数，arr2[]所需的空间总是一些常数c）
案例11：？?

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

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

}

空格=（0）+1+1+1=O（1）
辅助空间＝1＋1＋1＝O（1）
（原因：变量m需要1个临时存储器，变量i需要1个临时存储器，由于m是一个常数，arr2[]所需的空间总是一些常数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;
   }   

}

间距=（1+n+1+m）+1=o（n+m）
辅助空间＝1＝O（1）
（原因：正在处理的变量n和m有2个存储器，arr1有n个存储器，arr2有m个存储器，而变量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;
   }   

}

间距=（1+N）+1+1+1=O（N）
辅助空间＝1＋1＋1＝O（1）
（原因：变量i和m需要2个空格，arr2需要常量m空格，var n需要1个空格，arr1需要n个空格）
案例14：

 algo(arr1[],n){

   int arr2[10];

 }

空格=（0）+1=O（1）
辅助空间＝1＝O（1）
（原因：每次调用函数时，都需要10个空格来声明arr2）

Answer 1

好的，我不是要逐一处理每一个案例，而是试图帮助你理解空间的复杂性，这可能会解答你所有的疑虑。
方法的空间复杂度定义为额外量的多少。
随着输入的增长，您的方法使用空间来运行
选择。

algo(arr[],n){
}

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

在上述方法定义中-
如果我只操作参数变量和一些额外的变量，比如-
积分a=1，b=10，c=99；
int[]new_array=new int[1000]；
int m=1；int[]arr=新int[m]；
所有这些都将被认为是 O(1)空间复杂度。正如你所看到的，
无论我的输入有多大，变量的数量和大小都不会改变。
如果我声明了随输入增长的其他变量，比如-
int[]sum=新int[n]；
int[][]sum=new int[n][n]；
int[][]sum=新int[n][m]；
如您所见，数组的大小取决于
传递给方法。这里，如果我的输入数组大小恰好是 n，则
方法也将消耗 1000000000使其在空间中 1000000000。
int[]sum=new int[n]；占用 O(n)空间，因为大小取决于 O(n)
int[][]sum=new int[n][n]；占用O（n2）空间，因为它有 n行和
n列。
int[][]sum=new int[n][m]；占用 n空间，因为它有 O(n*m)行和 n
柱。

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

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

上面的代码片段执行以下操作-
声明具有 m行的数组。
为每行指定列的大小/数目。如果每行的列大小不同，则称为交错数组。
示例-
第1行-1列。
第2行-2列。
第3行-3列。
第4行-4列。
等等直到
第n行- n列。
上述代码的空间复杂度为O（n2）。原因是，在渐近表示法中，我们更关心 n场景在这里，不管其他行如何，对于第n行，我们有 worst case列，这也随着输入而增长。
我希望这能让你清楚空间的复杂性。