algorithm - n 个操作序列的聚合分析

Question

我试图在数据结构上的 n 操作序列中找到每个操作的摊销成本，其中 ith<​​ 操作成本 i 如果 i 是 2 的精确幂，否则为 1。

我想我需要找到一种方法来表示成本总和到一个数字 n，但我被卡住了。我可以看到特殊的、更昂贵的 i 值发生在父亲和更远的地方:

i = 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20...

所以，看起来我在 2 的第一个和第二个幂之间没有数字，然后是一个数字，然后是 3，然后是 7。当我看了一会儿，我(如果这个关闭了请纠正我)发现2 的 jth 和 kth 幂之间的 2 的非幂数是 2^(j-1) - 1。

但是我怎样才能将所有这些联系起来形成一个总和呢？我可以通过 js 结合 2 本身的实际幂数看到一些东西，但我无法将它们全部整合到一个概念中。

Answer 1

我无法提供求和的封闭形式，但很明显，平均成本在 2 的幂处达到峰值，连续的此类峰值渐近到 3.0，在下一个 2 的幂之前衰减到渐近上升的下限迈向 2.0。

严格介于 2^n 和 2^(n+1) 之间的 (2^n) - 1 个值对总成本贡献 1(导致平均值向下衰减)，直到 2^(n+ 1) 加 2^(n+1)。因此，从 2^n 之后开始到 2^(n+1) 结束的片段的平均贡献是 ((2^n)-1 + 2^(n+1))/2^n 或 (3 * 2^ n - 1)/2^n，随着 n 的增加接近 3。

您可以在下面的摘录表中看到这两种效果。希望这会有所帮助。

      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
    ...