4

操作コストが正確に 2 のべき乗であり、それ以外の場合は 1 であるnデータ構造に対する一連の操作で、操作ごとの償却コストを見つけようとしています。ithii

コストの合計を数値まで表現する方法を見つける必要があると思いますが、n行き詰まっています。i特別な、より高価な値が父と離れて発生していることがわかります。

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

つまり、2 の 1 乗と 2 乗の間に数がないように見えます。次に 1 の数、次に 3、次に 7 です。これをしばらく見てみると (間違っていたら訂正してください)、jthと2 の累乗の間の 2 の非累乗kthは です2^(j-1) - 1。

しかし、どうすればこれをすべてまとめて合計することができますか? 2 の実際のべき乗の数自体を組み合わせたものを少し見ることができますがjs、すべてを 1 つの概念にまとめるのに苦労しています。

4

4 に答える 4

2

合計の閉じた形を提供することはできませんが、平均コストが2の累乗でピークに達し、そのようなピーク値が3.0に漸近し、次の2の累乗の前に減衰して下限に減衰し、2.0に向かって漸近することは明らかです。

厳密に2^nと2^（n + 1）の間の（2 ^ n）-1の値のそれぞれは、2 ^（n + 1）の値が加算されるまで、合計コストに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
    ...
于 2012-09-30T04:13:40.977 に答える
2

ステップあたりの償却コストは、次のように、3をわずかに下回る（nが2の累乗である場合）から2をわずかに下回る（nが2の累乗である場合）までの範囲です。

K（n）がnステップの総コストを示し、T（n）がnを超えない2の累乗のコストを表すとします。n = 2^jと仮定します。次に
K(n) = n + T(n) - j
、すべてのステップに1のコストを割り当て、次に2の累乗ステップの合計コストを加算し、それらのステップのダブルカウントのjを減算することでわかるように。nが2の累乗である場合、3
T(2^j) = 1 + 2 + 4 +...+ 2^j = 2^(j+1)-1 = 2*n-1,
を わずかに下回る償却原価に対して、があります
K(n) = 3*n - j - 1。

ここで、n = 2 ^（j + 1）-1と仮​​定します。（ステップ2^jの
K(n) = K(2^j) + n - 2^j
後のn-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、
nが2の累乗より1小さい場合、2よりわずかに少ない償却コストがあります。

于 2012-09-30T04:21:23.757 に答える
1

操作ごとの償却コストは最大で 3 です。これは、n 回の操作の合計コストを計算して n で割るか、課金引数によって取得できます。充電引数は次のように構成できます。

i が 2 の累乗でない場合、i に 1 のコストがかかります。それ以外の場合、i が 2^k の形式の場合、操作コストは 2^k になり、位置の操作間で再分配できます: [2^{k-1}+1, 2^k]。これは、[2^{k-1}+1, 2^k-1] 位置の各操作の電荷を 2 増やし、残りの電荷 2 を 2^k 位置の操作に割り当てることで実行できます。再配分後、任意の位置での最大チャージは 3 です。

于 2012-09-30T03:21:54.557 に答える
1

n 回の操作の総コスト -

ここに画像の説明を入力

どうやってこれにたどり着いたか -

2 の累乗のコスト - 2の最初の n 乗の合計は ですここに画像の説明を入力。n までの数の累乗が必要だったので、n を対数 n の下限に置き換えました。

他の数字のコスト -ここに画像の説明を入力ユニット コストを持つ数字が残ります。

両方を足すと方程式にたどり着きます。

于 2013-10-16T10:11:10.327 に答える