# 程序员必知的算法和数据结构：2500字性能总结

1科学方法(Scientific method)

2观察(Observations)

``` 1public class Stopwatch {
2
3    private final long start;
4
5    public Stopwatch() {
6        start = System.currentTimeMillis();
7    }
8
9    public double elapsedTime() {
10        long now = System.currentTimeMillis();
11        return (now - start) / 1000.0;
12    }
13
14    public static void main(String[] args) {
15        int n = Integer.parseInt(args[0]);
16
17        // sum of square roots of integers from 1 to n using Math.sqrt(x).
18        Stopwatch timer1 = new Stopwatch();
19        double sum1 = 0.0;
20        for (int i = 1; i <= n; i++) {
21            sum1 += Math.sqrt(i);
22        }
23        double time1 = timer1.elapsedTime();
24        StdOut.printf("%e (%.2f seconds)\n", sum1, time1);
25
26        // sum of square roots of integers from 1 to n using Math.pow(x, 0.5).
27        Stopwatch timer2 = new Stopwatch();
28        double sum2 = 0.0;
29        for (int i = 1; i <= n; i++) {
30            sum2 += Math.pow(i, 0.5);
31        }
32        double time2 = timer2.elapsedTime();
33        StdOut.printf("%e (%.2f seconds)\n", sum2, time2);
34    }
35} ```

3具体例子

``` 1public class ThreeSum {
2
3    // print distinct triples (i, j, k) such that a[i] + a[j] + a[k] = 0
4    public static void printAll(int[] a) {
5        int n = a.length;
6        for (int i = 0; i < n; i++) {
7            for (int j = i+1; j < n; j++) {
8                for (int k = j+1; k < n; k++) {
9                    if (a[i] + a[j] + a[k] == 0) {
10                        StdOut.println(a[i] + " " + a[j] + " " + a[k]);
11                    }
12                }
13            }
14        }
15    }
16
17    // return number of distinct triples (i, j, k) such that a[i] + a[j] + a[k] = 0
18    public static int count(int[] a) {
19        int n = a.length;
20        int count = 0;
21        for (int i = 0; i < n; i++) {
22            for (int j = i+1; j < n; j++) {
23                for (int k = j+1; k < n; k++) {
24                    if (a[i] + a[j] + a[k] == 0) {
25                        count++;
26                    }
27                }
28            }
29        }
30        return count;
31    }
32
33    public static void main(String[] args)  {
35        Stopwatch timer = new Stopwatch();
36        int count = count(a);
37        StdOut.println("elapsed time = " + timer.elapsedTime());
38        StdOut.println(count);
39    }
40} ```

``` 1public class DoublingTest {
2
3    public static double timeTrial(int n) {
4        int[] a = new int[n];
5        for (int i = 0; i < n; i++) {
6            a[i] = StdRandom.uniform(2000000) - 1000000;
7        }
8        Stopwatch s = new Stopwatch();
9        ThreeSum.count(a);
10        return s.elapsedTime();
11    }
12
13
14    public static void main(String[] args) {
15        StdOut.printf("%7s %7s %4s\n", "size", "time", "ratio");
16        double previous = timeTrial(256);
17        for (int n = 512; true; n += n) {
18            double current = timeTrial(n);
19            StdOut.printf("%7d %7.2f %4.2f\n", n, current, current / previous);
20            previous = current;
21        }
22    }
23}```

Log–logplot. 绘制log图也是衡量运行时间的一种方法，因为是log级别的，所以与上面说的经验公式没有本质区别，如下图右所示，取完对数后，输入数据大小与运行时间的对数变为线性关系。

• 执行每一个语句的成本
• 执行每一个语句的次数

4波浪线符号

5增长的阶数(order of growth)

6内存消耗

• 每一个实例的内存消耗
• 每一个对象关联的头部消耗，典型的是8个字节

378 篇文章98 人订阅

0 条评论

## 相关文章

36050

29330

44970

### HUST 1588 辗转数对

1588 - 辗转数对 时间限制：1秒 内存限制：128兆 155 次提交 27 次通过 题目描述假设当前有一个数对(a, b)，我们可以通过一步将这个数对...

34690

1.8K50

### 计算字符串相似度算法——Levenshtein

Levenshtein 距离，又称编辑距离，指的是两个字符串之间，由一个转换成另一个所需的最少编辑操作次数。

90810

470120

8310

12940

41370