java - e^x 函数的时间复杂度

Question

在 CS 中，我们必须模拟 HP 35 计算器，所以我查找了 e^x 的求和 [在这种情况下，'^' 表示“的幂”]。公式是 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!。低于准确度。

使用 i! 的 Stirling 近似值，给出 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;