269.算法的存储空间需求

  • 时间:
  • 浏览:0
  • 来源:大发时时彩官网_大发时时彩平台有哪些_大发时时彩正规平台

1.1定义

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

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

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

1.2补充

  类式,有以下算法,其中临光阴间为变量i、maxi占用的空间。

就说就说,空间僵化 度是对有俩个 算法在运行过程中临时占用的存储空间大小的量度,一般也作为问题图片规模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=1150;
    while (i<=n)
    {      k++;
      i+=2;
    }
}
  解:该算法是有俩个

非递归算法,其中只临深冬配了i、k有俩个

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