1

このアルゴリズムから再帰方程式を見つける必要があります。

    ALGO(n)
    if n <= 2 then return(0)
    else
        y = ALGO(n/3)
        i = 2^n
        while i >= 2 do
            j = (1/2) * log(i) //base 2
            while j > 0 do
                i = i/2
                j = j - 1
        z = ALGO(n/2)
        return(z+y)

私はそれについて推論し、n<=2 の場合、T(n) = O(1) と結論付けました

内側の while は O(n) (反復ごとに j が 1 ずつ減少) であり、外側の while は O(logn) (反復ごとに i が半分になる) であり、O(n*log( n)):

T(n) = T(n/3) + T(n/2) + O(n*log(n)) n > 2の場合

これは良い議論ですか？

4

1 に答える 1

3

2 つの while ループは O(n) である必要があります。

1. i = 2^n;
2. j = (1/2) * log (i) = 1/2 * n = n/2
3. the inner while executes for n/2 times then j becomes 0, now i = i / 2^(n/2) = 2^(n/2);

ここで、このプログラムはステップ 1 に戻りますが、i は半分になります。したがって、2 つのループは次のようになります。

n/2+n/4+n/8+... = O(n)

実際、これはより単純な観点からも見ることができます。ループは i == 1 になるまで終了せず、実行ごとに i = i / 2 になるため、内側のループは n 回実行されます。内側のループと外側のループを平坦化すると想像してください。i = i / 2 が n 回あるため、2 つのループは O(n) になります。

結論として、T(n) = T(n/3) + T(n/2) + O(n) です。

これが役立つことを願っています！

于 2011-07-07T15:12:03.690 に答える