2

以下は、私がインタビューストリートのウェブサイトで見た C++ コードで、0 から a (入力番号) までの 1 のビットをカウントします。ただし、0 には 1 がないため、1 ~ a と言えます。このコードの時間計算量は、再帰を使用して O(logn) です。

ただロジックがわかりません。誰でも理由を説明できますか？どうも！

long long solve(int a)
{
 if(a == 0) return 0 ;
 if(a % 2 == 0) return solve(a - 1) + __builtin_popcount(a) ;
 return ((long long)a + 1) / 2 + 2 * solve(a / 2) ;
}

BTW __builtin_popcount() は、1 であるビットをカウントするために GNU が提供する組み込みメソッドです。

4

1 に答える 1

2

O(lg n)その複雑さを突き詰めていきます。証明はまだ実行時間を保持する必要がありますが、関数が何をするのかよくわからないことに注意してください。

再帰関係を考えると、次のようになります。

T(a) = 0, if a == 0
     | T(a - 1) + O(1), if a is divisible by 2
     \ O(1) + T(a/2)

ここでは反復法を使用します。

T(a) = T(a/2) + O(1)
T(a) = T(a/2^2)) + O(1) + O(1)
T(a) = T(a/2^k)) + (k-1)O(1)
// continue unrolling until we reach the base case
T(a) = 0 + O(1) + ... + O(1) + O(1) = kO(1)
// k here corresponds to lg a since we continued dividing the problem set in half
T(a) = (lg a)*O(1)
T(a) = lg a

QED

于 2012-05-09T19:57:19.953 に答える