3

CS では、HP 35 電卓をエミュレートする必要があったため、e^x の合計を調べました [この場合、'^' は「べき乗」を意味します]。式はsum n=0 to infinity ( (x^n) / (n!) )

私の実装では、最初の for ループは合計ループ:であり、2 番目の for ループは、double をオーバーフローしないよう1 + x + x^2 /2! + x^3 /3! + ...に項を個別に乗算するために使用されます。x... + (x/3) * (x/2) * (x/1) + ...

時間の複雑さに関しては、最初の for ループは必要な精度を確保するためにのみ必要ですが、2 番目の for ループは項を乗算するために使用されます。どちらのループも x のサイズに直接影響されないため、このアルゴリズムで時間の計算量を計算する方法がわかりません。n ln(n) だと思います。計算方法/このアルゴリズムの時間計算量は?

    public class TrancendentalFunctions {

        private static final double ACCURACY = .000000000000001;

        public static double exp(double x) {

            // if larger than 709, throw overflow error

            double result = 1; // result starts at one is important
            for(int i=1; i < 2147483647; i++) {

                double temp = 1; // temp starts at one is important
                for(int n = i; n > 0; n--) {
                    temp *= x / n;

                }

                result += temp;

                if (temp < ACCURACY) break; // accuracy of 14 digits
            }
            return result;
        }

    }
4

1 に答える 1

8

アルゴリズムは O(1) 時間で実行されます。これは、実行する作業の量が制限されているためです (ただし、巨大な値によって)。

i外側のループ ( over ) を境界ではなく無限として扱う場合、内側のループ ( over n) はi作業単位を実行します。x^i/i!が ACCURACY 未満になるまで外側のループが実行されます。

i! にスターリングの近似を使用すると、x^i/i!asの近似が得られ(1/sqrt(2*pi*i)) * (e*x/i)^iます。

(手を振っていますが、これは形式化できると思います) 大きなxの場合、これは (これが真になるとすぐe*x/i < 1に の値がx^i/i!ACCURACY よりも急速に小さくなるため) のあたりで真になります。それはi = e*x.

したがって、外側のループは O(x) 回実行され、総実行時間は O(x^2) になります。

ランタイムを O(x) に短縮する明らかな改善があります。x^i/i!毎回計算する代わりに、以前の値を再利用します。

double temp = 1;
double result = 1;
for (int i = 1; true; i++) {
    temp *= x / i;
    result += temp;
    if (Math.abs(temp) < ACCURACY) break;
}
return result;
于 2015-04-09T05:24:13.640 に答える