为什么此代码对计算功率不利（效率较低）？

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