ran*_*its 2 algorithm big-o amortized-analysis
我正在阅读Cracking the Coding Interview,在Big O章节中,有一个关于摊销时间的解释.这里使用了诸如ArrayList需要增长的经典示例.当阵列需要增长时,O(N)假设必须将N个元素复制到新阵列,插入将花费时间.这可以.
我不明白的是,由于数组的容量增加了一倍,为什么每次插入的摊销时间都是O(1)从我理解的内容中,无论何时插入数组,它总是一个O(N)操作.摊销时间有何不同？我确信文本是正确的,我只是不想讨论O(1)摊销的时间概念.
我正在回答你似乎感到困惑的问题,而不是你正式问的问题.
你真正的问题是追加是一种O(1)操作.如果已经为数组的下一个元素分配了空间,则追加只是更新有多少元素的记录,并复制该条目.这是一个O(1)操作.
如果溢出可用空间,仅追加是昂贵的.然后你必须分配一个更大的区域,移动整个数组,并删除前一个.这是一个O(n)操作.但是,如果我们每次都这样做O(1/n),那么平均来说它仍然会出现O(n * 1/n) = O(1).
平均事项是否取决于您的任务.如果您正在控制重型机械,在单独操作上花费太长时间就意味着您不能很快回到旋转叶片,这可能是正式的.如果您正在生成一个网页,那么重要的是一系列操作所需的总时间,这将是操作次数乘以每个操作的平均时间.
对于大多数程序员来说,平均值才是最重要的.