Почему этот код плохо рассчитывает мощность (менее эффективен)?

Question

class Solution {
   public:
      double myPow(double x, int n) {
         double result=1;
         bool neg=false;

         if(n<0)
         {
            n = -1*n;
            neg=true;
         }
         for(int i =1; i<=n;i++)
         {
            result = x*result;
         }  
         if(neg)
         {
            result = 1/result;
         }
         return result;
      }

};

Answer 1

Ваш метод использует O(N) операции для вычисления мощности.
Возможно вычислить мощность в O(log(N)) операциях.

По этой причине он не самый эффективный.

Логика для преобразования его в O(log(N)) операций можно увидеть на https://en.wikipedia.org/wiki/Exponentiation_by_squaring.

Основная идея заключается вчто

Чтобы заставить эту логику работать, вам нужно переместить код, который вычисляет мощность, в положительное значение для его собственной функции, которая может бытьрекурсивный.

      double myPowPositive(double x, int n) {
         // Use the efficient algorithm.
      }

      double myPow(double x, int n) {
         double result=1;
         bool neg=false;

         if(n<0)
         {
            n = -1*n;
            neg=true;
         }

         result = myPowPositive(x, n);

         if(neg)
         {
            result = 1/result;
         }
         return result;
      }

Answer 2

Я не предоставляю код, потому что это явно домашний вопрос, но я надеюсь, что вы поможете найти правильное решение.

Проблема в том, что ядро ​​цикла требует n умножения.Обычный способ сделать это - циклически перебирать биты в n, умножая на x, если бит установлен, и возводя в квадрат x каждый раз, когда вы переходите к следующему биту.Это требует умножения O (ceil (lg (n))).

Answer 3

Вы не можете действительно остановить потерю точности в знаменателе, если не знаете его главных факторов.Вот почему не стоит пробовать это упражнение для знаменателя (отрицательные показатели), но сначала пробовать его для числителей (положительные показатели).