在这里,我写了一些不同的函数案例,其中数组作为输入,我需要帮助来确定我的答案背后的推理是否正确(我在我遇到困难的案例上打了问号)
案例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)
最佳答案
好的,我不是要逐一处理每一个案例,而是试图帮助你理解空间的复杂性,这可能会解答你所有的疑虑。
方法的空间复杂度定义为额外量的多少。
随着输入的增长,您的方法使用空间来运行
选择。
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
列,这也随着输入而增长。我希望这能让你清楚空间的复杂性。
关于arrays - 空间复杂度-涉及数组的各种情况函数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/51761602/