Python实现的归并排序的空间复杂度
每个函数调用会搞出O(n)大的内存（也就是分裂成leftpad和rightpad）分别递归两次（注意是分别的）空间复杂度T(n)=O(n)+T(n/2)由主定理得到总的空间复杂度是O(n)你会认为是O(nlogn)我想是你误解了这里的两次递归调用，误以为T(n/2)前面会有个系数2。实际是没有的，因为这里统计的是消耗的最大内存，而不是总共使用（或者说访问）了多少内存，所以并不需要这个系数2，这样复杂度自然是O(n).你可以直观想像一下你的调用栈，最多log次递归，每层分别需要O(n),O(n/2),O(n/4),...的内存，对他们求和也是O(n)没有错的（这样估计是比较粗糙的，不过更直观一些。。吧？）
推荐阅读
- 北京22家市属医院均开展安检基本实现重点区域安检措施全覆盖
- 长江流域渔民退捕“上岸”实现扩产新致富
- 实现“甜蜜计划”，这对中哈跨国夫妻好甜
- 北京地铁11号线西段三座车站提前实现主体结构封顶
- 怎样成为一名合格的Python程序员?
- python 爬虫，咋获得输入验证码之后的搜索结果
- python的html5lib这个库咋使用啊我在网上也没有找到相关文档
- 零基础入门学习啥语言好
- 特斯拉|特斯拉将全面发布全自动驾驶软件最新版，曾承诺年底实现完全无人干预
- |徐州建有农家书屋2205家，实现数字书屋全覆盖