gpt4 book ai didi

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

转载 作者:塔克拉玛干 更新时间:2023-11-01 22:44:03 25 4
gpt4 key购买 nike

在 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;
}

}

最佳答案

该算法的运行时间为 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;

关于java - e^x 函数的时间复杂度,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/29530081/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com