Агрегатный анализ для последовательности n операций

Я не могу предложить закрытую форму для суммы, но ясно, что средняя стоимость достигает пика при степени двойки, причем последовательные такие пиковые значения асимптотичны до 3,0, уменьшаясь перед следующей степенью двойки до нижнего предела, который асимптотически возрастает до 2,0.

Каждое из значений (2^n) - 1 строго между 2^n и 2^(n+1) вносит 1 в общую стоимость (вызывая уменьшение среднего значения) до тех пор, пока значение 2^(n+1) не добавит 2 ^ (п + 1). Следовательно, средний вклад сегмента, начинающегося после 2^n и заканчивающегося 2^(n+1), равен ((2^n)-1 + 2^(n+1))/2^n или (3 * 2^ n - 1) / 2^n, которое приближается к 3 по мере увеличения n.

Вы можете увидеть оба эффекта в приведенной ниже таблице. Надеюсь это поможет.

      i       sum  average
-------   -------  -------
      1:        1  1.00000
      2:        3  1.50000
      3:        4  1.33333
      4:        8  2.00000
    ...
      7:       11  1.57143
      8:       19  2.37500
    ...
     15:       26  1.73333
     16:       42  2.62500
    ...
     31:       57  1.83871
     32:       89  2.78125
    ...
     63:      120  1.90476
     64:      184  2.87500
    ...
    127:      247  1.94488
    128:      375  2.92969
    ...
    255:      502  1.96863
    256:      758  2.96094
    ...
    511:     1013  1.98239
    512:     1525  2.97852
    ...
   1023:     2036  1.99022
   1024:     3060  2.98828
    ...
   2047:     4083  1.99463
   2048:     6131  2.99365
    ...
   4095:     8178  1.99707
   4096:    12274  2.99658
    ...
   8191:    16369  1.99841
   8192:    24561  2.99817
    ...
  16383:    32752  1.99915
  16384:    49136  2.99902
    ...
  32767:    65519  1.99954
  32768:    98287  2.99948
    ...
  65535:   131054  1.99976
  65536:   196590  2.99973
    ...
 131071:   262125  1.99987
 131072:   393197  2.99986
    ...
 262143:   524268  1.99993
 262144:   786412  2.99992
    ...
 524287:  1048555  1.99996
 524288:  1572843  2.99996
    ...
1048575:  2097130  1.99998
1048576:  3145706  2.99998
    ...

Амортизированная стоимость шага колеблется от чуть меньше 3 (когда n равно степени 2) до чуть меньше 2 (когда n равно 1 меньше степени 2), как показано ниже.

Пусть K(n) обозначает общую стоимость n шагов, а T(n) обозначает стоимость степеней двойки, не превышающих n. Предположим, что n = 2^j. Тогда
K(n) = n + T(n) - j
можно получить, приписав каждому шагу стоимость, равную единице, затем добавив общую стоимость шагов в степени 2 и вычтя j из-за двойного счета на этих шагах. Поскольку
T(2^j) = 1 + 2 + 4 +...+ 2^j = 2^(j+1)-1 = 2*n-1,
у нас есть
K(n) = 3*n - j - 1,
при амортизированной стоимости чуть меньше 3, когда n является степенью двойки.

Теперь предположим, что n = 2^(j+1)-1. У нас есть
K(n) = K(2^j) + n - 2^j
(из-за n - 2^j шагов удельной стоимости после шага 2^j ), т.е.
K(n) = (3*2^j - j - 1) + (2^(j+1) - 1) - 2^j,
или
K(n) = 2*(2^(j+1)-1) - j = 2*n - j,
для амортизированной стоимости чуть меньше 2, когда n на единицу меньше степени 2.

Амортизированная стоимость операции будет не более 3. Вы можете получить это значение либо путем вычисления общей стоимости n операций и деления ее на n, либо с помощью аргумента начисления платы. Аргумент зарядки может быть построен следующим образом.

Когда i не является степенью числа 2, заряд стоит 1 на i. В противном случае, когда i имеет форму 2^k, стоимость операции была бы 2^k, которая должна быть перераспределена между операциями в позициях: [2^{k-1}+1, 2^k]. Это можно сделать, увеличив заряд каждой операции в позициях [2^{k-1}+1, 2^k-1] на 2 и назначив оставшийся заряд 2 операции в позиции 2^k. После перераспределения максимальный заряд на любой позиции равен 3.

Общая стоимость n операций -

Как я к этому пришел -

Стоимость степеней двойки. Сумма первых n степеней двойки равна . Поскольку мне нужны степени чисел до n, я заменил n на пол журнала n.

Стоимость остальных номеров. Останутся номера, имеющие единицу Стоимость.

Сложите их обоих, и вы получите уравнение.