Временная сложность функции 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 термин, чтобы не переполнить двойное: ... + (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!, дает приближение для x^i/i! как (1/sqrt(2*pi*i)) * (e*x/i)^i,

(Машет рукой, хотя я считаю, что это можно формализовать) Для больших x, это будет верно в отношении точки, где e*x/i < 1 (поскольку, как только это правда, значение x^i/i! быстро станет меньше ТОЧНОСТИ). Что бывает когда 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;