java教程

關於java時間計算的演算法與最佳化方法詳解

黄舟

May 07, 2017 am 09:44 AM

隨著使用電腦的經驗的增長，人們在使用電腦編寫程式的時候，不可避免的會發出這樣的疑問：

##我的程式運行一次需要多久？
我的程式碼是否可以再優化得更快更節省空間？

當我們開啟一個網頁或傳輸一個檔案或開啟一個播放器時，你也肯定問過自己上面的問題。但是在這種情況下估計時間和資料處理的複雜度太難太模糊了。相比較這種大型應用，我們能夠處理的是單一程式的複雜度和效率。如果每片程序的效率都是相對較優的，那麼我們也不用需要擔心最後組合的應用會過於臃腫緩慢。這篇文章會對程式的演算法時空複雜度，優化方法和等等一切瑣事做解釋，從3-sum和2-sum這兩個例子開始，從頭到尾示範演算法是怎麼對我們的程式起作用的。

範例：3-sum與2-sum計算

#3-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)，感兴趣的朋友可以自己试一试，或者有更简便算法的话，发在评论里我们交流一下。不胜感激。