文件名称：Performance Measurement
文件大小：2KB
文件格式：C
更新时间：2016-05-10 13:38:20
浙大 数据结构 project
There are at least two different algorithms that can compute XN for some positive integer N. Algorithm 1 is to use N – 1 multiplications. Algorithm 2 works in the following way: if N is even, XN = XN / 2 XN / 2; and if N is odd, XN = X(N – 1) / 2 X(N – 1) / 2 X. Figure 2.11 in your textbook gives the recursive version of this algorithm. Your tasks are: (1) Implement Algorithm 1 and an iterative version of Algorithm 2; (2) Analyze the complexities of the two algorithms; (3) Measure and compare the performances of Algorithm 1 and the iterative and recursive implementations of Algorithm 2 for X=1.0001 and N = 1000, 5000, 10000, 20000, 40000, 60000, 80000, 100000.