Bil*_*its 1 java arraylist time-complexity data-structures
ArrayList 的大多数实现在内部使用数组，当向列表添加元素时大小已经耗尽时，它会通过本质上执行以下操作来调整大小或“增长”：
\nN - 1为元素对象，其中N是数组的新大小。提供的解释是，增长列表对于平均添加操作来说很少有必要，因此平均添加的时间复杂度为O(1)，因此摊销常数时间。
我很困惑这有什么意义。假设列表增长了Q. 简单的算术系列将向您展示，如果我向xArrayList 添加元素，则内部完成的元素副本总数为x^2 + Qx / 2Q，如果x比 多几倍Q。
当然，对于添加的前几个值，时间很可能是恒定的，但是对于添加的足够多的元素，我们看到每个添加操作的平均时间复杂度是线性的或O(n)。因此，向列表添加大量元素需要指数时间。我不明白单个加法操作的摊余时间复杂度如何是恒定的。我有什么遗漏的吗？
编辑：我没有意识到列表增长实际上是几何级数，这优化了摊销时间复杂度。
\n结论：
\n动态列表线性增长
\n让N = kQ
用于N + 1插入
副本：
\n Q + 2Q + 3Q + \xe2\x80\xa6 + kQ\n= (k / 2)(2Q + (k - 1)Q)\n= (k / 2)(Q + kQ) \n= (kQ + k^2 * Q) / 2 \n-> kQ + k^2 * Q\n元素初始化：
\n Q + 2Q + 3Q + 4Q + \xe2\x80\xa6 + (k + 1) * Q \n= ((k + 1) / 2)(2Q + kQ) \n= (k^2 * Q + 2kQ + 2Q + kQ) / 2 \n-> k^2 * Q + 3kQ + 2Q\n廉价插入：
\n kQ + 1 \n-> kQ\n总成本： 2Q * k^2 + 5kQ + 2Q
每次插入的摊销成本：
\n 2k + 5 + 2 / k \n-> 2k + 2 / k\n-> O(N / Q)\n-> O(N)\n动态列表的几何增长
\n让N = Q^k
用于N + 1插入
副本：
\n 1 + Q + Q^2 + \xe2\x80\xa6 + Q^k \n= (1 - Q^(k + 1)) / (1 - Q) \n-> Q^k\n元素初始化：
\n 1 + Q + Q^2 + \xe2\x80\xa6 + Q^(k + 1) \n= (1 - Q^(k + 2)) / (1 - Q) \n-> Q^(k + 1)\n廉价插入：
\n Q^k + 1 \n-> Q^k\n总成本： 2Q^k + Q^(k + 1)
每次插入的摊销成本：
\n 2 + Q\n-> O(1)\n比较
\n数组的几何调整大小/增长是恒定时间，而线性调整大小是线性时间。比较这两种增长方法以了解性能差异以及为什么选择 ArrayList 进行几何增长是很有趣的。
\n不失一般性，假设列表的初始容量为1。我们进一步假设每次插入超出容量时容量都会加倍。现在考虑插入2^k + 1元素（这是一般最坏的情况，因为最后一个操作触发动态增长）。
存在k触发动态增长的插入，其累积成本为
1 + 2 + 4 + 8 + ... + 2^k = 2^(k+1) - 1
其他“廉价”插入的累计成本为2^k - k + 1。
但我们对摊余复杂度感兴趣，因此我们必须对所有2^k + 1操作进行平均：
(2^(k+1) + 2^k - k) / (2^k + 1)
< (2^(k+1) + 2^k - k) / 2^k
= 2 + 1 - k/2^k
= O(1)
因此，向2^(k+1)列表中插入元素的每次插入的摊余时间复杂度为 O(1) ，常数因子接近 3。向列表中插入任何其他数量的元素都不能更差，因此每次插入的摊余时间复杂度为 O( 1）一般情况。
| 归档时间： |
|
| 查看次数： |
1340 次 |
| 最近记录： |