破解编码面试的摊销时间

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) time.The，每次插入的摊销时间为 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 的两倍。