ArrayList基础数组成本
我最近正在从Java中读取ArrayList。根据我的理解，当ArrayList达到其容量时，它将调用其resize方法并创建一个新的基础数组，该数组的大小是原始数组的两倍。由于这种情况，这种插入方式可以视为O（n），但平均而言仍为O（1）。但是，我对将其增加到两倍大小的原因感到困惑。将其增加到原始容量的三倍会更好吗？
问题来源：stackoverflow
展开
收起
2
条回答
写回答
写回答
-
-
做一个优秀的阿里云志愿者重要的是容量要增加一个常数。不管那个因素是多少：1.5等于3。摊销成本将为O（1）-恒定时间。尽管不同的因素导致不同的常数。
如果您在考虑因素的情况下进行数学运算，则摊销时间成本为O（f /（f-1）），其中f是因素。如果加倍的时间成本为2，则三倍的时间成本为1.5。
容量的增加很大程度导致调整大小操作减少，但浪费的空间更大。您必须找到一个平衡点：是否将执行时间减少了25％相当于将存储开销增加了50％？
答案来源：stackoverflow
2020-03-28 11:13:13赞同 展开评论 打赏
版权声明：本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
相关问答
问答排行榜
最热
最新
推荐问答
