Давайте попробуем это на конкретном примере.Пусть 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 0 + 2 1 + 2 2 + 2 3 + ... + 2 log 2 X .
Итакмы складываем ряд степеней из двух.Можем ли мы упростить это?Ага!Это сумма геометрического ряда, и с помощью короткого путешествия в Википедию мы можем узнать, что
2 0 + 2 1 + 2 2 + 2 3 + ... + 2 k = 2 k + 1 - 1 = 2 · 2k - 1.
В нашем случае k = lg X, поэтому сумма получается равной
2 · 2lg X - 1 = 2X - 1.
Итак, мы видим, что действительно эта сумма не более чем в два раза больше X.