-2

実行時間を計算したいアルゴリズムは次のとおりです。

T(n) = {
        c0 * n, if n <= 20
        T(roundUp(n/4)) + T(roundUp(5/12 * n + 3/2)) + c1*n, if n > 20
       }

n は正の自然数の一部で、c0 と c1 は定数です。

Javaコードのアルゴリズムは次のとおりです。

    public static void main(String[] args) {
        for (int i = 20; i < 100; i++) {
            System.out.println("i: " + i + " :    " + rec(i, 1, 1));
        }
    }

    public static int rec(int n, int c0, int c1) {
        int res = 0;
        if (n <= 20) {
            res += c0 * n;
        } else {
            double temp = n / 4d;
            double temp2 = n * (5 / 12d) + (3 / 2d);
            res += rec((int) Math.ceil(temp), c0, c1) + rec((int) Math.ceil(temp2), c0, c1) + c1 * n;
        }
        return res;
    }

アプローチまたは説明の例を探しています。

4

1 に答える 1

1

うーん、これは長い間やっていませんでしたが、まだ誰も答えを出していないので、試してみましょう。ここでは基本的に、2 つの重要な子を持つツリーを作成します。左がtemp = n / 4d、右が をベースにしていtemp2 = n * (5 / 12d) + (3 / 2d)ます。問題は、この木の深さはどれくらいかということです。n / 4dすぐに終わるので、右の子だけを気にします20。n * (5 / 12d) + (3 / 2d)それで問題は、どのくらい右端の子供がいるということnですか? 反復すると、次のようになります。

n * (5 / 12d) + (3 / 2d) 
ceil(n * (5 / 12d) + (3 / 2d) ) * (5 / 12d) + (3 / 2d)
ceil(ceil(n * (5 / 12d) + (3 / 2d)) * (5 / 12d) + (3 / 2d) ) * (5 / 12d) + (3 / 2d)
...

ここでは、3/2d一部とそれに関連するすべてを無視することもできるため、次のようになります。

n * (5 / 12) ^ k < 20

k一番右の子に到達するためのステップ数はどこにあるので、次のようになります。

n * (5 / 12) ^ k < 20
k = log_(5 / 12) (20 / n)
k = log_2(20 / n) / log_2 (5 / 12)   
k = (log_2 (20) - log_2(n) ) / log_2 (5 / 12)

これから：

k = log_2 (20) / log_2 (5 / 12)

は特定の数値です。無視できます...

k = - log_2(n) / log_2 (5 / 12)

以来：

log_2 (5 / 12)  < 0

私たちは残っています：

k = log_2(n) = lgn

予想どおり、ツリーのみを使用するため、 が得られO(n) = lg(n)ます。

于 2016-05-04T10:45:04.190 に答える