老师参与

【参考答案】算法3的空间复杂度是多少？

陈越 发表于2022年07月03日
<p>1. 由于递归而产生的空间复杂度是多少？</p><p><br ></p><p>这个问题是问一共递归了多少层。由于我们每次递归都把搜索范围缩小一半，也就是N/2/2/2...直到得到1，于是有公式<img src="https://mooc-image.nosdn.127.net/_PhotoUploadUtils_d695085c-07a8-46ad-9fcc-5bceaef61553.png" />，推出<img src="https://mooc-image.nosdn.127.net/_PhotoUploadUtils_bde95eed-9898-48b9-b1a3-a39450601fcb.png" />，即递归最多需要O(logN)次，占用的空间跟递归的次数成正比，也就是O(logN)。</p><p><br /></p><p>2. 算法的整体空间复杂度一共是多少？</p><p><br /></p><p>由于List是作为指针参数传递的，函数内部并没有声明额外的、长度跟N有关的数组，所以每次调用函数都只占用O(1)的额外空间，于是占用的空间跟递归的次数成正比，也是O(logN)。</p><p><br /></p><p>如果考虑整个main函数的空间复杂度，就要把原始List也算在内，它占了O(N)的空间，那么整体空间复杂度就应该是O(N)+O(logN) = O(N)。</p><p><br /></p><p>注意：如果每次传递的不是数组的指针，而是每次复制一段数组，那么递归产生的空间复杂度就变成O(N)了！</p><p><br /></p>
举报
3 回复
    深度学习爱好

    1楼

  • 深度学习爱好 发表于2022年07月28日
    0 | 0 | 举报
    <p><a href="https://jibing.qiuyi.cn/yykshsj/" >https://jibing.qiuyi.cn/yykshsj/</a></p><p><a href="https://m.qiuyi.cn/yykshsj/" >https://m.qiuyi.cn/yykshsj/</a></p><p><a href="https://jibing.qiuyi.cn/yykshsj/tese/" >https://jibing.qiuyi.cn/yykshsj/tese/</a></p><p><a href="https://jibing.qiuyi.cn/yykshsj/dongtai/" >https://jibing.qiuyi.cn/yykshsj/dongtai/</a></p><p><a href="https://jibing.qiuyi.cn/yykshsj/jianjie/" >https://jibing.qiuyi.cn/yykshsj/jianjie/</a></p><p><a href="https://jibing.qiuyi.cn/yykshsj/yisheng/" >https://jibing.qiuyi.cn/yykshsj/yisheng/</a></p><p><a href="https://jibing.qiuyi.cn/yykshsj/zhinan/" >https://jibing.qiuyi.cn/yykshsj/zhinan/</a></p><p><a href="https://jibing.qiuyi.cn/yykshsj/huanjing/" >https://jibing.qiuyi.cn/yykshsj/huanjing/</a></p><p><a href="https://jibing.qiuyi.cn/yykshsj/lianxi/" >https://jibing.qiuyi.cn/yykshsj/lianxi/</a></p><p><a href="https://www.ykxxlt.com/" >https://www.ykxxlt.com/</a></p><p><a href="https://www.jk001.org/" >https://www.jk001.org/</a></p><p><a href="https://www.nihaodj.com/" >https://www.nihaodj.com/</a></p><p><a href="https://www.ku6ku6.com/" >https://www.ku6ku6.com/</a></p><p><a href="https://jzshengedu.com/jiaoyu/36131.html" >https://jzshengedu.com/jiaoyu/36131.html</a></p><p><a href="https://jyzhongg.com/xinwen/9006.html" >https://jyzhongg.com/xinwen/9006.html</a></p><p><a href="https://news.fh21.com.cn/ysxw/swsd/6840777.html" >https://news.fh21.com.cn/ysxw/swsd/6840777.html</a></p><p><a href="https://m.qiuyi.cn/yykshsj/dongtai/269381.html" >https://m.qiuyi.cn/yykshsj/dongtai/269381.html</a></p><p><a href="https://www.zhihu.com/people/wangluoredain" >https://www.zhihu.com/people/wangluoredain</a></p><p><a href="https://www.zhihu.com/column/c_1510225443295129600" >https://www.zhihu.com/column/c_1510225443295129600</a></p><p><a href="https://jibing.qiuyi.cn/yykshsj/tese/183042.html" >https://jibing.qiuyi.cn/yykshsj/tese/183042.html</a></p>
    深度学习爱好 发表于2022年07月28日
    0 | 评论(0) | 举报
    添加评论
    • mooc11933851080079815

    2楼

  • mooc11933851080079815 发表于2022年07月28日
    0 | 0 | 举报
    <p><a href="https://jibing.qiuyi.cn/yykshsj/wenda/" >https://jibing.qiuyi.cn/yykshsj/wenda/</a></p><p><a href="https://m.fh21.com.cn/news/mip/6840777.html" >https://m.fh21.com.cn/news/mip/6840777.html</a></p><p><a href="https://jibing.qiuyi.cn/yykshsj/dongtai/225798.html" >https://jibing.qiuyi.cn/yykshsj/dongtai/225798.html</a></p><p><a href="https://www.szhk.com/2019/12/03/283047305744107.html" >https://www.szhk.com/2019/12/03/283047305744107.html</a></p><p><a href="https://jibing.qiuyi.cn/yykshsj/yisheng/716.html" >https://jibing.qiuyi.cn/yykshsj/yisheng/716.html</a></p><p><a href="https://jibing.qiuyi.cn/yykshsj/dongtai/261596.html" >https://jibing.qiuyi.cn/yykshsj/dongtai/261596.html</a></p><p><a href="https://www.ommoo.com/news/20210501/105827.html" >https://www.ommoo.com/news/20210501/105827.html</a></p><p><a href="https://jibing.qiuyi.cn/yykshsj/dongtai/237728.html" >https://jibing.qiuyi.cn/yykshsj/dongtai/237728.html</a></p><p><a href="https://jibing.qiuyi.cn/yykshsj/tese/208548.html" >https://jibing.qiuyi.cn/yykshsj/tese/208548.html</a></p><p><a href="https://m.qiuyi.cn/yykshsj/dongtai/238982.html" >https://m.qiuyi.cn/yykshsj/dongtai/238982.html</a></p>
    mooc11933851080079815 发表于2022年07月28日
    0 | 评论(0) | 举报
    添加评论
    • mooc11933851080079815

    3楼

  • mooc11933851080079815 发表于2022年07月28日
    0 | 0 | 举报
    <p><a href="https://jibing.qiuyi.cn/yykshsj/dongtai/237712.html" >https://jibing.qiuyi.cn/yykshsj/dongtai/237712.html</a></p><p><a href="https://jibing.qiuyi.cn/yykshsj/dongtai/237714.html" >https://jibing.qiuyi.cn/yykshsj/dongtai/237714.html</a></p><p><a href="https://jibing.qiuyi.cn/yykshsj/dongtai/237735.html" >https://jibing.qiuyi.cn/yykshsj/dongtai/237735.html</a></p><p><a href="https://jibing.qiuyi.cn/yykshsj/dongtai/237709.html" >https://jibing.qiuyi.cn/yykshsj/dongtai/237709.html</a></p><p><a href="https://jibing.qiuyi.cn/yykshsj/dongtai/237711.html" >https://jibing.qiuyi.cn/yykshsj/dongtai/237711.html</a></p><p><a href="https://jibing.qiuyi.cn/yykshsj/tese/227492.html" >https://jibing.qiuyi.cn/yykshsj/tese/227492.html</a></p><p><a href="https://jibing.qiuyi.cn/yykshsj/dongtai/237728.html" >https://jibing.qiuyi.cn/yykshsj/dongtai/237728.html</a></p><p><a href="https://jibing.qiuyi.cn/yykshsj/dongtai/237702.html" >https://jibing.qiuyi.cn/yykshsj/dongtai/237702.html</a></p><p><a href="https://jibing.qiuyi.cn/yykshsj/tese/208432.html" >https://jibing.qiuyi.cn/yykshsj/tese/208432.html</a></p><p><a href="https://jibing.qiuyi.cn/yykshsj/dongtai/231869.html" >https://jibing.qiuyi.cn/yykshsj/dongtai/231869.html</a></p><p><a href="https://jibing.qiuyi.cn/yykshsj/dongtai/213723.html" >https://jibing.qiuyi.cn/yykshsj/dongtai/213723.html</a></p><p><a href="https://jibing.qiuyi.cn/yykshsj/tese/199408.html" >https://jibing.qiuyi.cn/yykshsj/tese/199408.html</a></p><p><a href="https://baijiahao.baidu.com/s?id=1739068626833756782" >https://baijiahao.baidu.com/s?id=1739068626833756782</a></p><p><a href="https://baijiahao.baidu.com/s?id=1735083014834654923" >https://baijiahao.baidu.com/s?id=1735083014834654923</a></p><p><a href="https://weibo.com/ttarticle/p/show?id=2309351000494392219300724993" >https://weibo.com/ttarticle/p/show?id=2309351000494392219300724993</a></p>
    mooc11933851080079815 发表于2022年07月28日
    0 | 评论(0) | 举报
    添加评论
发表回复