269.算法的存储空间需求

  • 时间:
  • 浏览:0

1.1定义

  另3个 算法的存储量包括形参所占空间和临时变量所占空间。在对算法进行存储空间分析时,只考察临时变量所占空间。

  算法的空间繁复度定义为:S(n) = O(g(n))​

  表示随着大问题规模 n 的增大,算法运行所需存储量的增长率与 g(n) 的增长率相同。​​​

1.2补充

  这种 ,有以下算法,其中临时空间为变量i、maxi占用的空间。

很多很多很多很多有,空间繁复度是对另3个 算法在运行过程中临时占用的存储空间大小的量度,一般也作为大问题规模n的函数,以数量级形式给出,记作:

S(n)=O(g(n))、Ω(g(n))或Θ(g(n))

其中渐进符号的含义与时间繁复度中的含义相同。

int max(int a[],int n)
{   int i,maxi=0;
    for (i=1;i<=n;i++)
    if (a[i]>a[maxi])
         maxi=i;
    return a[maxi];
}
函数体内分配的变量空间为临时空间,不计形参占用的空间,
这里的仅计i、maxi变量的空间,其空间繁复度为O(1)。

  注意:​若输入数据所占空间只取决于大问题四种 ,和算法无关,​则只时需分析除输入和线程之外的辅助变量所占额外空间。若所需额外空间相对于输入数据量来说是常数,则称此算法为原地工作。若所需存储量依赖于特定的输入,则通常按最坏清况 考虑。引用大概给个变量别名,不占用空间。

  • 算法的存储量包括:
    • 1.输入数据所占空间
    • 2.线程四种 所占空间
    • 3.辅助变量所占空间
【例1.9】分析例1.6算法的空间繁复度。  
void func(int n)
{   int i=1,k=50;
    while (i<=n)
    {      k++;
      i+=2;
    }
}
  解:该算法是另3个



非递归算法,其中只临九时配了i、k另3个



变量的空间,它与大问题规模n无关,很多很多很多很多有其空间繁复度均为O(1),即该算法为原时工作算法。
【例1.10】有如下递归算法,分析调用
    maxelem(a,0,n-1)
    的空间繁复度。
int maxelem(int a[],int i,int j)
{   int mid=(i+j)/2,max1,max2;
    if (i<j)
    {    max1=maxelem(a,i,mid);
       max2=maxelem(a,mid+1,j);
    return (max1>max2)?max1:max2;
    }
    else return a[i];
}
   解:执行该递归算法时需多次调用自身,每次调用只临九时配3个整型变量的空间(O(1))。
   设调用maxelem(a,0,n-1)的空间为S(n),有:
S(n)=O(1)            当n=1
S(n)=2S(n/2)+O(1)        当n>1     o(1)是int mid=(i+j)/2,max1,max2;常量空间
则:
S(n) 
= 2S(n/2)+1=2[2S(n/22)+1]+1=22S(n/22)+1+21
= 23S(n/23)+1+21+22
= …
= 2kS(n/2k)+1+21+22+…+2k-1(设n=2k,即k=log2n)
= n*1+2k-1 = 2n-1 
= O(n)

1.3注意

  为有哪些算法占用的空间只考虑临时空间,而无须考虑形参的空间呢?这是机会形参的空间会在调用该算法的算法中考虑,这种 ,以下maxfun算法调用max算法:

void maxfun()
{   int b[]={1,2,3,4,5},n=5;
  printf("Max=%d\n",max(b,n));
}
int max(int a[],int n)
{   int i,maxi=0;
    for (i=1;i<=n;i++)
    if (a[i]>a[maxi])
         maxi=i;
    return a[maxi];
}

maxfun算法中为b数组分配了相应的内存空间,其空间繁复度为O(n),机会在max算法中再考虑形参a的空间,很多很多很多很多重复计算了占用的空间。