269.算法的存储空间需求

  • 时间:
  • 浏览:1
  • 来源:幸运快3_快3平台代理_幸运快3平台代理

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=5000;
    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的空间,好多好多 重复计算了占用的空间。

猜你喜欢

IBM发表论文:证明量子计算机比传统计算机更快

IT之家10月21日消息 根据Tom'sHardware的报道,IBM的研究人员因为发表了一篇论文,证明量子计算机人太好比传统计算机很快,怎么让某些点到目前为止还在理论层面。▲

2020-01-25

梅利亚VS塞尔塔B队免费视频直播,梅利亚VS塞尔塔B队比赛集锦,梅利亚VS塞尔塔B队录像,梅利亚VS塞尔塔B队首发阵容

首页新闻视频直播数据APP懂球号直播君广告相互相互合作梅利亚01-1918:150西乙B1-0已结速塞尔塔B队直播君|分析|集锦暂无数据近期比赛多特蒙德德甲2-0科隆布雷西亚意

2020-01-25

Xbox老大:主机失去意义,串流可服务20亿玩家

从几年前现在开使,就因为着越来越人论断“下一代主机将是最后一代主机,因为着串流技术和云技术因为着让主机硬件拖累意义”,现在随着现实的技术越来越接近你这一想法,或许你这一未来离亲

2020-01-25

英倡组“欧洲海军”保卫波斯湾

图:伊朗舰队19日包围英国油轮美联社【大公报讯】据法新社及彭博社报道:伊朗19日扣押一艘英国油轮,以报复英国海军月初在直布罗陀扣押伊朗油船,大幅加剧了区域紧张局势。英国22日表

2020-01-25

世界上最小的磁体诞生:IBM实现在单原子上存储位数据

别问我当当让我们儿与否愿意幻想过愿意的场景:有朝一日当当让我们儿要能将iTunes曲库中的35000万首歌曲存储在一张非要信用卡大小的设备当中。尽管愿意的理想很美好,然而目前的

2020-01-25