通过迭代算法和分治算法的比较理解如何利用分支思想设计一个高效算法。

1、编写函数实现用迭代算法计算x的n次幂；

2、编写函数实现用分治算法计算x的n次幂；

3、测试计算1的n次幂，分别令n取1000、1万、10万、100万、1000万的情况下两种算法各自的运行时间，通过对比分析研究哪个算法在数据量逐渐增大时效率高；

4、对两种算法进行理论分析哪个算法效率高；

5、与实验数据对照，检查是否实验结果验证了理论分析的结果。

迭代算法伪代码：

Iteration(x,n)

ans=1;

for i=1 to n

n=n*n;

分治算法伪代码：

Divide_Conquer(x,n)

If n=1

return x

then n>1

if n%2=0

Divide_Conquer(x,n/2)

return ans*ans;       

then

Divide_Conquer(x,(n-1)/2);

return ans*ans*x;

1、每个算法时间复杂度分析：

分治算法解递归式T(n)=T(n/2)+θ(n)可得T(n)=θ(lgn)。

迭代算法时间复杂度为O(n)。

2、结论：

分治法：将一个规模为n的问题分解为k个规模较小的子问题，这些子问题相互独立且与原问题相同，然后递归地解这些子问题,最后将各个子问题的解合并得到原问题的解。

迭代法:利用变量的原值推算出变量的一个新值。

迭代算法计算x^n就是x相乘n次 。分治法是将x^n分情况求，再递归。

综上所分析可知，分治算法时间复杂度远小于迭代算。

测试结果示例：(单位：微秒)

算法名称

运行时间

数据量

1000

1万

10万

100万

1000万

平均运行时间

分治算法递归

0．3

0.6

0．6

0.9

0.8

O(lgn)

迭代算法

3.5

42.1

421

4386.6

37833.1

O(n)