时间电源的复杂性（） [英] Time complexity of power()

问题描述

我实现了这个功能电源（）这两个参数 A 和 B 并计算 ^B 。

I implemented this function power() which takes two arguments a and b and computes a^b.

typedef long long int LL;

LL power(int a,int b)
{
   int i = 1;
   LL pow = 1; 
   for( ; i <= b ; ++i )
     pow *= a;
   return pow;
}

假设：一个 ^B 落在的范围内得到long long int 。
问题：如何降低我的算法的时间复杂度

Given : a^b falls in the range of long long int.
Problem : How to reduce the time complexity of my algorithm?

推荐答案

幂的平方。

一个非递归执行

LL power(int a, int b)
{
  LL pow = 1;
  while ( b ) 
  {
         if ( b & 1 ) 
         {
           pow = pow * a;
           --b;
         }
         a = a*a;
         b = b/2;
  }
  return pow;
}

此算法需要的日志 ₂ B squarings，最多的日志 ₂ B 乘法。

This algorithm requires log₂b squarings and at most log₂b multiplications.

运行时间为 O（日志B）

这篇关于时间电源的复杂性（）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！