269.算法的存储空间需求

  • 时间:
  • 浏览:2
  • 来源:大发uu快3_uu快3概率_大发uu快3概率

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=50;
    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的空间,从前重复计算了占用的空间。