在《算法导论》第一部分练习中,有这样一道算法题:
1.2-3 对于一个运行时间为100n*n的算法,要使其在同一台机器上,在比一个运行时间为2^n的算法运行的很快,n的最小值是多少?
下面给出我自己的解题思路:
对于100n^2和2^n两个算法进行比较,我们可以这样做:对100n^2-2^n操作,如果结果小于0,那么此时的n就是我们所求的值。
针对这一思路给出以下算法实现:
1 /**
2 *
3 */
4 package com.b510.algorithms;
5
6 /**
7 * 《算法导论》第一部分:练习1.2-3:对于一个运行时间为100n^2的算法,要使其在同一台机器上,比一个运行时间为2^n的算
8 * 法运行得更快,n的最小值是多少?
9 *
10 * @author hongten(hongtenzone@foxmail.com)<br>
11 * @date 2013-6-6
12 */
13 public class PartOneOfAlgorithms {
14
15 public static void main(String[] args) {
16 getSum();
17 }
18
19 /**
20 * 对于100n^2和2^n两个算法进行比较,我们可以这样做:对100n^2-2^n操作,如果结果小于0,那么此时的n就是我们所求的值。
21 * java中求一个数的n次方,方法为Math.pow(x,y);即x的y次方
22 */
23 public static void getSum() {
24 int n = 1;
25 long sum = 0;
26 boolean flag = true;
27 while (flag) {
28 sum = (long) (100 * (Math.pow(n, 2)) - Math.pow(2, n));
29 System.out.println("第" + n + "次计算结果为:" + sum);
30 if (sum < 0) {
31 flag = false;
32 break;
33 }
34 n = n + 1;
35 }
36 System.out.println(n);
37 }
38 }
运行效果:
第1次计算结果为:98
第2次计算结果为:396
第3次计算结果为:892
第4次计算结果为:1584
第5次计算结果为:2468
第6次计算结果为:3536
第7次计算结果为:4772
第8次计算结果为:6144
第9次计算结果为:7588
第10次计算结果为:8976
第11次计算结果为:10052
第12次计算结果为:10304
第13次计算结果为:8708
第14次计算结果为:3216
第15次计算结果为:-10268
15