algorithm - ループの再帰関係

Question

問題は、アルゴリズムによって与えられた値を見つけるために再帰関係を設定することです。答えは teta() 用語である必要があります。

foo = 0;

for int i=1 to n do
    for j=ceiling(sqrt(i)) to n do
        for k=1 to ceiling(log(i+j)) do
             foo++

Answer 1

完全にはわかりませんが、ここに行きます。

2 番目のループは1 - sqrt(1) + 2 - sqrt(2) + ... + n - sqrt(n) = n(n+1)/2 - n^1.5times => O(n^2)times を実行します。の議論については、こちらを参照してくださいsqrt(1) + ... + sqrt(n) = O(n^1.5)。

3 番目のループが発火O(n^2)回数を取得することを確認しました。したがって、アルゴリズムは次のようなものと漸近的に同等です。

for i = 1 to n do
    for j = 1 to n do
        for k = 1 to log(i+j) do
            ++foo

これは合計につながりlog(1+1) + log(1+2) + ... + log(1+n) + ... + log(n+n)ます。log(1+1) + log(1+2) + ... + log(1+n) = log(2*3*...*(n+1)) = O(n log n). これに を掛けるとn、 になりO(n^2 log n)ます。

したがって、あなたのアルゴリズムもO(n^2 log n)であり、Theta(n^2 log n)私が間違っていなければ。