java教程

关于java时间计算的算法与优化方法详解

黄舟

May 07, 2017 am 09:44 AM

随着使用计算机的经验的增长，人们在使用计算机编写程序的时候，不可避免的会发出这样的疑问：

我的程序运行一次需要多久？
我的代码是否可以再优化得更快更节省空间？

当我们打开一个网页或者传输一个文件或打开一个播放器时，你也肯定问过自己上面的问题。但是在这种情况下估计时间和数据处理的复杂度太难太模糊了。相比较这种大型应用，我们能够处理的是单个程序的复杂度和效率。如果每片程序的效率都是相对较优的，那么我们也不用需要担心最后组合的应用会过于臃肿缓慢。这篇文章会对程序的算法时空复杂度，优化方法和等等一切琐事做解释，从3-sum和2-sum这两个例子开始，从头到尾演示算法是怎么对我们的程序起作用的。

例子：3-sum与2-sum计算

3-sum
一个文件中有许多不重复整数，任意三个整数可组成一组，统计其中任意三个整数和为0的组数。

2-sum
一个文件中有许多不重复整数，统计其中和为0的整数对个数。

暴力算法（常规未优化算法）：

  public int threeSum(int[] arr) {
        int count = 0;
        int n = arr.length;
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++)
                for (int k = j + 1; k < n; k++)
                    if (arr[i] + arr[j] + arr[k] == 0)
                        count++;
        return count;
    }

<p style="margin-bottom: 7px;">  public int twoSum(int[] arr) {<br/>        int count = 0;<br/>        int n = arr.length;<br/>        for (int i = 0; i < n; i++)<br/>            for (int j = i + 1; j < n; j++)<br/>                if (arr[i] == -arr[j])<br/>                    count++;<br/>        return count;<br/>    }<br/></p>

成本模型

我们如果想要优化这段程序，首先要知道这段程序能优化的点在哪里，这就是评估成本模型。通过确定程序的成本模型来定义我们所研究的算法中的基本操作。

3-sum问题的成本模型
在研究解决3-sum问题的算法时，我们记录的是数组的访问次数（访问数组次数，无论读写）

换而言之，我们的目标就是尽量让我们评估出的成本模型变得更优。在3-sum问题中模型比较简单，但有些复杂的程序的成本模型需要谨慎确定，因为如果我们忽略了一些操作可能导致最后优化的结果并不是程序整体的最优情况。

从成本模型出发优化程序

上面的暴力代码没有任何在结果上的问题，在数据较少的情况下执行的还不算太慢。但是如果测试数据量是10的n次方级，那么这种未经优化的代码在时间上会带来很大的负面效果。我们说暴力的代码速度慢，那什么样的代码才算是速度快呢？

我们在3-sum的成本模型中已经确定了数组的访问次数是我们要研究和优化的内容。在java中，对数组的访问消耗的时间是常量级的（常量级就是几乎不消耗时间的意思）。那么在访问数组内容时间固定的情况下，让数组的访问次数变少，我们只需要让代码运行的时间变快即可。为了让代码速度变快，首先我们要了解增长数量级的分类和时间复杂度的概念。

增长数量级/时间复杂度

我们要说的内容就是时间复杂度，但是我们给他换了个名字——增长数量级。除了不使用大O标记，其他的地方这两种并没有什么区别。我们在实现算法的时候使用了几种结构性的原语，比如普通语句，循环，条件判断，嵌套语句等等，所以成本增长的数量级一般都是问题规模N的某个函数。问题规模N在这个例子中就是数组中数字的个数。

增长数量级/时间复杂度主要有以下7种：

常数级别

增长的数量级： 1
时间复杂度： O(1)
典型代码：

a = b + c;

结构性原语：普通语句
举例：将两个数相加
说明：运行时间的增长数量级为常数级别的程序完成他的任务需要的时间是固定的，和N无关。java中几乎所有的操作所需的时间都是常数级别的。常数级别的速度是所有时间复杂度中最快的。

对数级别

增长的数量级： logN
时间复杂度： O(logN)
典型代码：

public static int rank(int key, int[] a, int lo, int hi) {
        if (hi < lo)
            return -1;
        int mi = lo + (hi - lo) / 2;
        if (key < a[mi])
            return rank(key, a, lo, mi - 1);
        else if (key > a[mi])
            return rank(key, a, mi + 1, hi);
        else
            return mi;
    }

结构性原语：二分策略
举例：二分查找
说明：速度稍微慢于常数级别，但快于O(N)最典型的对数级别的例子就是二分查找，log下面的底数可能是变化的，但是因为只是一个常数对整体和N的影响不大，所以我们一般表示成logN的形式。

线性级别

增长的数量级： N
时间复杂度： O(N)
典型代码：

for (int i = 0; i < n; i++)
        if(arr[i] == 0)
            count++;

结构性原语： 一层循环
举例： 找出最大元素
说明： 线性级别稍慢于对数级别，但快于线性对数级别。他的运行时间和N成正比。在有些情况下，我们只需要进行一半的数组遍历，理论上可以将时间除以2，但是仍旧与N的一次方有关，所以我们把此类都算作线性级别。

线性对数级别

增长的数量级： NlogN
时间复杂度： O(NlogN)
典型代码：
归并排序
结构性原语： 分治
举例： 归并排序
说明： 线性N乘以对数logN，速度快于N²但是慢于线性级别。在归并排序中，按照类似二分的方法确定归并点，对归并到最底层的数据进行复杂度为O(N)的排序，时间复杂度为O(NlogN)。快速排序，归并排序都可以看作是线性对数级别。

平方级别

增长的数量级： N²
时间复杂度： O(N²)
典型代码：

for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++)
                if (arr[i] == -arr[j])
                    count++;

结构性原语：双层循环
举例：检查所有元素对
说明：平方级别的程序一般都是含有两个for循环，初级的排序算法选择排序和插入排序都是这种复杂度。

立方级别

增长的数量级： N³
时间复杂度： O(N³)
典型代码：

for (int i = 0; i < n; i++)  for (int j = i + 1; j < n; j++)
        for (int k = j + 1; k < n; k++)
            if (arr[i] + arr[j] + arr[k] == 0)
                count++;

结构性原语：三层循环
举例：对数组中的三个数据进行操作
说明：立方级别的代码一般都是三个for循环嵌套而成，我们日常的算法很少有这种运算时长。

指数级别

增长的数量级： 2^N
时间复杂度： O(2^N)
典型代码：
穷举查找所有真子集
结构性原语：穷举法
举例：穷举查找所有真子集
说明：指数级别的增长在N较大时比较可怕，但是它确是某些问题看起来最优的解法，并不是很常用，等如果需要学习的时候可以专门研究。

优化2-sum问题

先从2-sum问题入手，根据上述复杂度，2-sum问题的暴力解法复杂度为O(N²)，又根据我们的成本模型只考虑访问数组次数，所以我们要在O(N²)的复杂度之内寻求最优解法即可。

从上面得知，排序算法的复杂度是O(NlogN)快于O(N²)，而我们对排序之后的数据进行运算时，已经不是在排序内部进行处理。所以最后计算时间是用加法而不是乘法。所以我们最后的解决策略是：我们先对整个数组进行排序，然后从数组头部依次读取a[i]，在数组中检索是否存在-a[i]。这种检索采用了二分查找的方法，复杂度为O(logN)。为了避免重复查找，如果查找到-a[i]的位置在a[i]之前，就说明该元素对已经被查找过，不计入次数。这样整体的算法复杂度是NlogN+N*logN（不知道这样写是否规范）。两项合并系数忽略，所以最后算法整体的复杂度为O(NlogN)。

public int twoSum(int[] arr) {
        int count = 0;
        Arrays.sort(arr);
        for (int i = 0; i < arr.length; i++)
            if (Arrays.binarySearch(arr, -arr[i]) > i)
                count++;
        return count;
    }

2-sum问题已经成功的进行了优化，3-sum问题也可以通过这种方式进行优化，但是最后优化的复杂度为O(N²logN)，感兴趣的朋友可以自己试一试，或者有更简便算法的话，发在评论里我们交流一下。不胜感激。