了解摊销时间以及为什么数组插入是 O(1)
Understanding Amortized Time and why array inserts are O(1)
我正在阅读 Cracking the Coding Interview，在 Big O 章节中，有一个关于 Amortized Time 的解释。这里使用了诸如需要增长的 ArrayList 之类的经典示例。当一个数组需要增长时，假设它必须将 N 个元素复制到新数组，插入将花费 O(N) 时间。这很好。
我不明白的是，由于数组的容量增加了一倍，为什么每次插入的摊销时间都是O(1)据我所知，无论何时插入数组，它总是O(N) 操作。摊销时间有何不同？我确信文本是正确的，我只是没有理解 O(1) 摊销时间概念。
我是在回答你似乎困惑的问题，而不是你正式提出的问题。
您真正的问题是追加如何成为 O(1) 操作。如果 space 已经分配给数组的下一个元素，那么附加只是更新有多少元素的记录，并复制条目。这是一个 O(1) 操作。
如果溢出可用，仅附加是昂贵的space。然后你必须分配一个更大的区域，移动整个数组，并删除以前的。这是一个 O(n) 操作。但是，如果我们只每 O(1/n) 次执行一次，那么在 平均 上它仍然可以达到 O(n * 1/n) = O(1).
平均值是否重要取决于您的任务。如果您正在控制重型机械，在单个操作上花费太长时间可能意味着您不能足够快地回到旋转 blade，这在官方上可能是糟糕的。如果您要生成网页，那么重要的是一系列操作所花费的总时间，即操作次数乘以每个操作的平均时间。
对于大多数程序员来说，平均值才是最重要的。
我正在阅读 Cracking the Coding Interview，在 Big O 章节中，有一个关于 Amortized Time 的解释。这里使用了诸如需要增长的 ArrayList 之类的经典示例。当一个数组需要增长时，假设它必须将 N 个元素复制到新数组，插入将花费 O(N) 时间。这很好。
我不明白的是，由于数组的容量增加了一倍，为什么每次插入的摊销时间都是O(1)据我所知，无论何时插入数组，它总是O(N) 操作。摊销时间有何不同？我确信文本是正确的，我只是没有理解 O(1) 摊销时间概念。
我是在回答你似乎困惑的问题，而不是你正式提出的问题。
您真正的问题是追加如何成为 O(1) 操作。如果 space 已经分配给数组的下一个元素，那么附加只是更新有多少元素的记录，并复制条目。这是一个 O(1) 操作。
如果溢出可用，仅附加是昂贵的space。然后你必须分配一个更大的区域，移动整个数组，并删除以前的。这是一个 O(n) 操作。但是，如果我们只每 O(1/n) 次执行一次，那么在 平均 上它仍然可以达到 O(n * 1/n) = O(1).
平均值是否重要取决于您的任务。如果您正在控制重型机械，在单个操作上花费太长时间可能意味着您不能足够快地回到旋转 blade，这在官方上可能是糟糕的。如果您要生成网页，那么重要的是一系列操作所花费的总时间，即操作次数乘以每个操作的平均时间。
对于大多数程序员来说，平均值才是最重要的。