e^x 函数的时间复杂度

Question

在 CS 中，我们必须模拟 HP 35 计算器，所以我查找了 e^x 的求和 [在这种情况下，'^' 表示 "to the power of"]。公式为 sum n=0 to infinity ( (x^n) / (n!) )

在我的实现中，第一个for循环是求和循环：1 + x + x^2 /2! + x^3 /3! + ...，第二个for循环用于单独乘出x项，以免溢出double : ... + (x/3) * (x/2) * (x/1) + ...

关于时间复杂度，第一个for循环只是为了保证必要的精度，而第二个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;
        }

    }

Answer 1

该算法在 O(1) 时间内运行秒，因为您执行的工作量是有限的（尽管是一个巨大的值）。

如果您将外循环（i）视为无限而不是有界，则内循环（n）执行 i 个工作单元。执行外循环，直到 x^i/i! 小于 ACCURACY。

使用斯特林对 i! 的近似，给出 x^i/i! 的近似为 (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;

e^x 函数的时间复杂度

Time complexity of e^x function

java

time-complexity

exp