3

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

在我的实现中，第一个 for 循环是求和循环：1 + x + x^2 /2! + x^3 /3! + ...，第二个 for 循环用于单独乘出x项，以免溢出双精度：... + (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;
        }

    }
4

1 回答 1

8

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

如果您将外循环 (over i) 视为无限而非有界，则内循环 (over n) 执行i工作单元。执行外部循环，直到x^i/i!小于 ACCURACY。

使用 i! 的斯特林近似值，给出x^i/i!as的近似值(1/sqrt(2*pi*i)) * (e*x/i)^i。

（挥手，虽然我相信这可以形式化）对于 large 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 回答