从入门开始手把手搭建千万级Java算法测试-计算X的n次幂两种方法比较

  第六天开始呢，我们讲解计算X的n次幂两种方法，从算法思路，到算法伪代码实现，到复杂度分析，从这里开始我们手把手搭建一个测试平台的基础，根据你自身硬件水平可以对下列代码进行从1000，到千万级测试，其中算法测试时间与你的机器硬件水平和实现的算法有关系，下面是计算X的n次幂两种方法的具体讲解。
（1）排序算法的思路并且举例说明
利用用迭代算法计算x的n次幂；
利用用分治算法计算x的n次幂；（具体看代码过程）

比如2的10次方为1024

（2）算法伪代码

//X的n次幂
//迭代计算：
Sum=1
For n=1to n
Sum=sum*x

//分治法：
Divide:
If n==1
Retuen x
If(n%2==0){
	Sum=divide(x,n/2)^2
	Retuen sum
}
else{
	Sum=divide(x,n-1/2)^2*x
	Retuen sum
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

（3）复杂度分析

1、 每个算法时间复杂度分析
（1）迭代算法
算法循环体中的代码执行了n次，因此时间复杂度为O(n)
时间复杂度为： O（n）
（2）分治计算
O（递归深度 * 单层递归时间复杂度）
时间复杂度为：O（lgn）

2.结论
  分治算法的x的n次方的计算上远远快于迭代的算法，在进行此类计算时往往采用分治的算法最为妥当

（4）代码主体部分

package runoob;

import java.util.Scanner;

public class Power_reckon {
    public static long usual(long num, long power){
        long sum=1;
        for (long i = 0; i < power; i++) {
            sum=sum*num;
        }
        return sum;
    }
    public static long Merge_power(long num, long power){
        long sum=1;
        if (power==1){
            return num;
        }
        if((power%2)==0){
            sum= Merge_power(num,power/2);
            return sum*sum;
        }else {
            sum= Merge_power(num,(power-1)/2);
            return sum*sum*num;
        }
    }
    public static void reckon_text(long num) {
        System.out.println("输入参与算法的x的值");
        Scanner X_num= new Scanner(System.in);
        long x= X_num.nextInt();
        long power= num ;
        long start1 =System.nanoTime();
        long normal=usual(x,power);
        long end1 =System.nanoTime();
        long start2 =System.nanoTime();
        long Merge= Merge_power(x,power);
        long end2 =System.nanoTime();
        System.out.println("分治法计算结果为"+Merge+"总耗时为"+(end2-start2)/1000+"ms");
        System.out.println("常规方法计算结果为"+normal+"总耗时为"+(end1-start1)/1000+"ms");
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

  对应代码中的SortHelper类我们留一个小小的悬念，留到最后来进行叙说，其中目前来说他的方法generateRandomArray的参数为，（num，left，right）第一个参数参与算法生成的数量级，作为随机生成序列，它可以为千万，因为是long级别，left和right则为生成序列的大小范围，生成的序列为返回值类型为Integer[]。
（5）测试结果如下：

  笔者有兴趣可以尝试千万级的算法测试，这里便不在赘述。