2

私は次の漸化式を持っています：

  f(0) = 0
  f(1) = 1
  f(n) = n + f(floor(n/2))

これは、コードで次のように表すことができます。

  int f(int n) {
    int s = 0;
    for (; n; n >>= 1)
      s += n;
    return s;
  }

f(n)1つのステップで計算できる閉じた形はありますか？

そうでない場合、f(n)より迅速に計算するために他にできることはありますか？

4

3 に答える 3

6

OEISで検索すると、このシリーズが得られます。

A005187：a（n）= a（[n / 2]）+ n; また、1 / sqrt（1-x）の展開の分母は2 ^ a（n）です。また、2n-2nの2進展開における1の数。

したがって、2番目の部分はの式を与え2*n - bitcount(2*n)ます。これは、gccなどの効率的なビットカウント実装を使用して計算できます__builtin_popcount。

于 2012-12-25T04:01:19.507 に答える
2

bitcount（2n）= bitcount（n）にも注意してください

派生は次のとおりです。

j = 0...Nに対してn=sum（b [j] 2 ^ j）とします。

b [N]=1と仮定します。

（a）F（n）= n + F（n / 2）= n + n / 2 + n / 4 + ... = 2 * n-（1/2 + 1/4 + ... 1/2 ^ N）等比数列による

この関数Fは実数値関数です。ここで、設定されたビットb [j]ごとに、床関数はb [j]（sum（1/2 ^ k、k = 1 ... j + 1））を減算します。これは、実際には1/2を取り出すためですが、伝播するにつれて後続の用語が追加されます。

それで

（b）f（n）= floor（F（n）-sum（b [j] sum（1/2 ^ k、k = 1 ... j + 1）、for j = 0 ... N-1 ）。

（a）を（b）に代入すると

（c）f（n）= floor（2n- （1/2 + 1/4 + ... 1/2 ^（N + 1）） -合計（b [j]（sum（1/2 ^（k ）、k = 1..j + 1）の場合、j = 0 ... N-1））の場合

わかりました、この部分はかなりクールです！b [j]が1の場合、太字の式からイタリック体の合計に1/2 ^（j + 1）をこっそり入れると、合計内の合計が1になることに注意してください。

b [j]（sum（1/2 ^（k）、for k = 1..j + 1）、for j = 0 ... N-1）= sum（b [j]、for j=0。 ..N-1）

したがって、式（c）は次のように簡略化されます。

f(n) = floor(2*n - sum(b[j], for j=0...N-1) - remainder)
f(n) = 2*n - bitcount(n-2^N) - 1    ; because remainder >0 and <1
f(n) = 2*n - bitcount(n)            ; b[N]=1, so bitcount(n)=bitcount(n-2^N)+1

ここで、余りはsum（1/2 ^ j、j = 1、.. N + 1 and b [j-1] == 0）ですが、この合計は常に> 0かつ<1です（最大で1-1です）。 / 2 ^（N + 2）および少なくとも1/2 ^（N + 1）なので、-1として床から移動できます。

また、ビットカウントの実行時間は、設定されたビット数と等しくすることができることに注意してください（http://gurmeet.net/puzzles/fast-bit-counting-routines/）。一部のプロセッサは、それを別個の命令として持っています。

ラテックスがここで機能するかどうかはわかりませんが、数学記号がないのは苦痛です。何かがいつも間違っているように見えるので、私はそれを編集し続けなければなりません。

于 2012-12-25T04:46:13.173 に答える
1 
The function grows as follows - 

f(n) = n + f(n/2)
f(n/2) can be further simplified as - 

n/2 + f(n/4)

If we keep doing this, we will see n + n/2 + n/4 + n/8.....upto log n terms
= n (1 + 1/2 + 1/4 + 1/8...log n terms)
= n[ (1- (1/2)^log n)/(1/2)]
= 2n [1 - (1/2)^log n]

The term (1/2)^log n will become smaller and smaller as n increases, therefore the 2n term dominates. Hence f(n) belongs to big Theta (n)
于 2013-01-27T09:34:45.463 に答える