List.Add的渐近复杂性是什么？
Eug*_*kov 7 c# algorithm asymptotic-complexity
我发现关于渐近复杂性存在很多争议List.Add().我怀疑它的来源是最糟糕的情况导致底层数组调整大小并且逻辑上是O(n)操作.但是,每次列表空间不足时,阵列的大小会增加两倍.这使n元素所需的调整大小成比例log(n).
这是不是意味着Add平均情况下操作的渐近复杂性会是O(n/log(n))什么？
真正的基准List.Add()是在下面.然而,基准测试并不能真正表达这种操作 - 在任何偏离直线(对数刻度)线变得可见之前,我们可能会耗尽内存.
这意味着,按摊余复杂的List.Add()可以通过总结调整大小操作,然后通过向列表中进行总增加数相乘来计算.
T(n) = (2 + 4 + 8 + ... + n/2 + n) / n
但请注意,求和是一个几何级数,我们可以做得比假设(求和)更好n*log(n):
T(n) < 2n/n = 2 -> T(n) is in O(1)
注意:这里我假设你的意思add()是附加.在任意位置插入元素需要花费O(n)时间,您也必须考虑到这一点,这会将最终结果从O(1)摊销的复杂性更改为O(n)分摊的复杂性.