求a^n的O(nlgn)算法

求a^n的O(nlgn)算法：

 

分治思想：

 

a^n = a^(n/2) *a^(n/2)                              n为偶数

          a^( (n-1)/2 ) * a^((n-1)/2 ) * a           n为奇数

 

 

T（n） = T（n/2）+ O（1）    =>      T（n） = O（nlgn）

 

代码：

 

#include <iostream>

using namespace std;

int multip(int a , int n)

{

    int mid;

    int x;

 

    if(n == 1)

        returna;

 

if(mid%2 == 1){

        mid =n/2;

        x =multip(a , mid);

        returnx*x;

    }else{

        mid =(n-1)/2;

        x =multip(a , mid);

        returnx*x*a;

    }

}

 

int main()

{

    int n , a;

 

    cout<< "请输入a^n中的a和n：";

    cin >>a >> n;

 

    cout << multip(a ,n) << endl;

    return 0;

}