算法分析 - Algorithms, Part I, week 1 ANALYSIS OF ALGORITHMS

前言

在算法性能上我们常常面临的挑战是我们的程序能否求解实际中的大型输入：

--为什么程序运行的慢?

--为什么程序耗尽了内存?

没有理解算法的性能特征会导致客户端的性能很差，为了避免这种情况的出线，需要具备算法分析的一些知识。

此篇主要涉及一些基础数学知识和科学方法，以及如何在实践应用中使用这些方法理解算法的性能。我们的重点放在获得性能的预测上。

主要分为5部分：

• 观察特点 (observations)
• 数学模型 (mathematical models)
• 增长阶数分类 (order-of-growth classifications)
• 算法理论 (theory of algorithms)
• 内存使用 (memory)

我们将从多种不同的角色思考这些问题：

• 程序员：解决一个问题，让算法能够工作，并部署它
• 用户：完成某项工作，但不关心程序做了什么
• 理论家：想要理解发生的事情
• 团队：可能需要完成以上角色的所有工作

关于算法分析需要集中考虑的关键是运行时间。运行时间也可以理解为完成一项计算我们需要进行多少次操作。

这里主要关心：

• 预测算法的性能
• 比较完成同一任务不同算法的性能
• 在最坏情况下算法性能的底线
• 理解算法如何运行的一些理论基础

算法分析的科学方法概述：

• 从自然界中观察某些特征(程序在计算机上的运行时间)
• 提出假设模型(与观察到的现象相一致的模型)
• 预测(利用上边的假设做出合理的预测，一般用来预测更大问题规模，或者另一台计算机上的运行时间)
• 验证(作更多的观察来验证我们的预测)
• 证实(重复地验证直到证实我们的模型和观察的特征吻合，证实我们的模型假设是正确的)

使用科学方法有一些基本原则：

• 别人做同样的实验也会得到相同的结果
• 假设必须具备某个特殊性质：可证伪性

(可证伪性：指从一个理论推导出来的结论（解释、预见）在逻辑上或原则上要有与一个或一组观察陈述与之发生冲突或抵触的可能。

可证伪，不等于已经被证伪;可证伪，不等于是错的。)

观察

第一步是要观察算法的性能特点，这里就是要观察程序的运行时间。

给程序计时的方法：

• 看表(你没看错，简单粗暴)
• 利用API：很多第三方或者 Java 标准库中有一个秒表类，可以计算用掉的时间
  (如apache commons lang,springframework的 工具 包都有，这里使用 stdlib库中的Stopwatch API 进行时间监控)

我们将使用 3-SUM 问题作为观察的例子。

3-SUM问题描述

三数之和。如果有N个不同的整数，以 3个整数划为一组 ，有多少组整数只 和为0 .

如下图，8ints.txt 有8个整数，有四组整数和为0

目标是编写一个程序，能对任意输入计算出3-SUM整数和为0有多少组。

这个程序实现的算法也很简单，首先是第一种，“暴力算法”

"暴力算法"

EN：brute-force algorithm

这里使用第三方API的方法测量程序运行的时间。

import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.Stopwatch;

    public class ThreeSum {
        public static int count(int[] a) {
            int N = a.length;
            int count = 0;
            //三重的for循环，检查每三个整数组合
            for (int i = 0; i < N; i++)
                for (int j = i + 1; j < N; j++)
                    for (int k = j + 1; k < N; k++)
                    //为了方便观察算法的性能问题，这里忽略了整型溢出问题的处理
                        if (a[i] + a[j] + a[k] == 0)
                            count++;
            return count;
        }
        /**
         * 读入所有整数，输出count的值
         * 利用StopWatch执行时间监控
         * @param args
         */
        public static void main(String[] args) {
            int[] a = StdIn.readAllInts();
            Stopwatch stopwatch = new Stopwatch();
            StdOut.println(ThreeSum.count(a));
            double time = stopwatch.elapsedTime();
        }
    }

实证分析

测试数据可以用越来越大的输入来运行。每次将输入的大小翻倍，程序会运行得更久。通过类似的测试，有时能相当方便和快速地评估程序什么时候结束。

数据分析

通过实证得出的数据，可以建立图像，使观察跟直观：

• 标准坐标 ：Y轴：运行时间；X轴：输入大小

• 双对数坐标：Y轴：取运行时间的对数；X轴：取问题输入大小的对数

(lg以2为底)

使用双对数坐标通常情况下是得到一条直线，这条直线的斜率就是问题的关键。

这个例子(3-SUM 暴力算法)的斜率是3

--通过对数坐标的方法得出公式： lg(T(N)) = blgN + c (可看做 y = b*x + c，其中 y = lg(T(N))，x = lgN)

--通过图中两点可求出b,c值，如果等式两边同时取2的幂，就得到 T(N) = 2c*N^b, 其中 2c 为一个常数，可记作 a

由此，从这个模型的 观察 中我们就得到了程序的运行时间，通过一些数学计算(在这里是回归运算)，我们就知道得出了运行时间：

T(N) = a*N^b (b为双对数坐标中直线的斜率，同时 b 也是这个算法的增长量级，第三点会讲到)

预测和验证

假设

通过上述的数据分析，我们得出 假设 ：

运行时间看起来大约是 1.006 × 10^–10 × N^2.999 (秒)

预测

可以运用这个假设继续做 预测 ，只要带入不同的N值，就能计算出需要的大致时间。

・51.0 seconds for N = 8,000.

・408.1 seconds for N = 16,000.

验证

通过对比 程序实际运行时间(下图) 和 通过我们的假设模型预测的时间上一步) 可以看出结果非常相近

这个模型帮助我们在不需要花时间运行试验的前提下做一些预测。实际上这个情形中存在幂定律(a*N^b).实际上绝大多数的计算机算法的运行时间满足幂定律。

下边介绍一种求解 符合幂定律 运行时间中的增长量级值(b)的方法

Doubling hypothesis 方法

• 计算b值

这里可以通过 Doubling hypothesis 的方法可以快速地估算出幂定律关系中的 b 值：

运行程序，将每次输入的大小翻倍( doubling size of the input)，然后计算出N和2N运行时间的比率。主要看下图的后几行运算时间比率，前几行的输入值小，以现在的计算机运算能力处理起来，立方级别的增量级运算速度快也相差无几。

ratio ≈ T(2N)/T(N).

至于为什么 0.8/0.1≈7.7 或其他看起来 "运算错误" 类似的情况，是因为图上的运行时间的记录是简化精确到了小数点后一位，实际运算比率值是使用了实际运行时间(精确到小数点后几位)去计算的，所以会出现0.8/0.1≈7.7。

通过不断地进行双倍输入实验，可以看到比率会收敛到一个常数(这里为8)，而实际上比率的对数会收敛到N的指数，也就是 b 的值，这里粗暴算法的 b 值就等于3

通过Doubling hypothesis方法我们又能提出假设：

此算法的运行时间大约是 a*N^b, 其中 b = lg ratio

注意：Doubling hypothesis 不适用于识别对数因子

• 计算a值

得出 b 的值后，在某个大的输入值上运行程序，就能求出 a 值。

由此得出 假设 ：运行时间 ≈ 0.998 × 10^–10 × N^3 (秒)

我们通过作图得出的模型( ≈ 1.006 × 10^–10 × N^2.999 )和我们通过Doubling hypothesis方法得出的模型是很接近的。

计算机中有很多的因素也会影响运行时间，但是关键因素一般和计算机的型号无关。

影响因素

关键的因素即为你使用的算法和数据.决定幂定律中的 b 值

还有很多与系统相关的因素：

• 硬件配置：CPU，内存，缓存...
• 软件环境：编译器，解析器，垃圾回收器...
• 计算机的系统：操作系统，网络，其它应用...

以上所有因素，包括关键因素，都决定了幂定律中的 a 值

现代计算机系统中硬件和软件是非常复杂的，有时很难获得非常精确的测量，但是另一方面我们不需要像其他科学中需要牺牲动物或者向一颗行星发射探测器这些复杂地方法，我们只需要进行大量的实验，就能理解和得到我们想要知道的影响因子(的值)。

数学模型

待更新。。。