269.算法的存储空间需求

  • 时间:
  • 浏览:1
  • 来源:大发uu快3_uu快3官方版app下载_大发uu快3官方版app下载

1.1定义

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

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

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

1.2补充

  这类,有以下算法,其中临時光英文间为变量i、maxi占用的空间。

所以,空间僵化 度是对另1个 算法在运行过程中临时占用的存储空间大小的量度,一般也作为大问题规模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=60

;
    while (i<=n)
    {      k++;
      i+=2;
    }
}
  解:该算法是另1个

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

变量的空间,它与大问题规模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];
}
   解:执行该递归算法需用多次调用自身,每次调用只临半时配1个整型变量的空间(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的空间,另另1个 重复计算了占用的空间。