0

Обычная задача по возведению в степень. Есть 2 функции. Подскажите, почему при значениях x = 0.00001 n = 2147483647 работает только первая (вторая не проходит по времени)? ведь идет простое перемножение.

double myPow1(double x, int n) {
    if(n==1)
        return x;
    if(n==0)
        return 1;
    if(n==-1)
        return 1/x;
    if(n==2)
        return x*x;
    return myPow(myPow(x, n/2), 2)* myPow(x, n%2);
}

double myPow2(double x, int n){
    double result = 1;
    if (n>=0){
        while (n-->=1) {
            result *= x;
        }
    }
    else {
        while (n++<0) {
            result /= x;
        }
    }
    return result;
}
4
  • Потому что на первую уходит порядка 30 операций, а на вторую порядка 2^30 операций. Разница весьма существенна.
    – coder675
    9 июн 2019 в 16:09
  • 1
    Потому-что у первой логарифмическая сложность (O(log N) ), а у второй - линейная ( O(N) ).
    – vt-egorov
    9 июн 2019 в 16:21
  • "ведь идет простое перемножение". Нет, в первом варианте идет совсем не простое перемножение. 9 июн 2019 в 17:21

1 ответ 1

3

Первая работает за О(log2(n)), вторая за О(n). Допустим нужно 2 ^ 16. Первая посчитает это (((2 ^ 2) ^ 2) ^ 2) ^ 2. Итого 4 действий. 4 = log2(16). На самом деле их несколько больше, но логарифмическая зависимости остаётся. Для 2147483647 понадобится порядка log2(2147483647) = 31 операций. Во втором же способе будет честно 2147483647 умножений. Правда ответ будет достаточно неверный ни там, ни там. Он просто в double не влезет. Минимальное положительное число у double ≈ 2.2*e-308. А 0.00001 ^ 2147483647 сильно меньше.

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.