如果选用蛮力算法对a进行n-1次相乘，算法的时间复杂度为O(n)

采用分治算法，将a^n看作两部分幂的乘积，每一部分都是一个子问题,即

                         n为偶数

      n为奇数

该情况下的时间复杂度W(n)为:

W(n) = W(2/n) + O(1)

W(1) = 0

于是得到

C语言程序实现如下：

//例2.2(分治算法)
//输入：n、a,a为给定的实数，n为自然数
//输出：a^n的结果
#include<stdio.h>
#include<stdlib.h>
int fun(int a,int n)
{
	int result;
	if(n==1)
	{
		return a;
	}
	else if(n==0)
	{
		return 1;
	}
	else if(n%2==0)
	{
		result = fun(a,n/2) * fun(a,n/2);
		return result;
	}
	else
	{
		result = fun(a,(n-1)/2) * fun(a,(n-1)/2) * a;
		return result;
	}
}

int main()
{
	int a,n,result;
	printf("请输入a的值：");
	scanf("%d",&a);
	printf("请输入n的值："); 
	scanf("%d",&n);
	result=fun(a,n);
	printf("a^n = %d",result);
}