big-o - 破解编码面试的摊销时间

Question

我正在阅读有关破解编码面试的摊销时间。作者开始谈论总和，我不明白为什么我们要从右到左求和，以及这如何给我们 2X (X+x/2+...)

“1 + 2 + 4 + 8 + 16 +... +X 的总和是多少？如果你从左到右阅读这个总和，它从 1 开始并加倍直到它到达 X。如果你从右到左阅读，它从 X 开始并减半直到它达到 1。那么 X+x/2+x/4+x/8+...+1 的总和是多少？这大约是 2X。因此，X 插入需要 O( 2X) 时间。每次插入的摊销时间为 O(1)。"

Answer 1

让我们用一个具体的例子来试试这个。让我们有 X = 128。我们想知道什么

1 + 2 + 4 + 8 + 16 + 32 + 64 + 128

是。作者的想法是将这个总和倒写为

128 + 64 + 32 + 16 + 8 + 4 + 2 + 1，

它与我们开始时的值相同。然后她建议将 64 视为 128/2，将 32 视为 128/4，将 16 视为 128/8，这意味着

128 + 64 + 32 + 16 + 4 + 2 + 1

= 128 + 128 / 2 + 128 / 4 + 128 / 8 + 128 / 16 + 128 / 32 + 128 / 64 + 128 / 128

= 128 (1 + 1/2 + 1/4 + 1/8 + 1/16 + 1/32 + 1/64 + 1/128)。

那么这个金额是多少呢？她的见解是这些分数加起来最多为两个。你明白这是为什么吗？如果您同意这个想法，您可以看到总和最多为 2 · 128.，是我们开始时的两倍。

你也可以用不同的方式计算这个总和。首先，请注意

1 + 2 + 4 + 8 + ... + X

= 2 ⁰ + 2 ¹ + 2 ² + 2 ³ + ... + 2 ^{log ₂ X}。

因此，我们将一系列 2 的幂相加。我们可以简化一下吗？是的！这是一个几何级数的总和，通过快速访问维基百科，我们可以了解到

2 ⁰ + 2 ¹ + 2 ² + 2 ³ + ... + 2 ^k = 2 ^k+1 - 1 = 2 · 2 ^k - 1。

在我们的例子中，我们有 k = lg X，所以总和为

2·2 ^{lg X} - 1 = 2X - 1。

所以我们确实看到，这个总和最多是 X 的两倍。