隨著使用電腦的經驗的增長，人們在使用電腦編寫程式的時候，不可避免的會發出這樣的疑問：
##我的程式運行一次需要多久？當我們開啟一個網頁或傳輸一個檔案或開啟一個播放器時，你也肯定問過自己上面的問題。但是在這種情況下估計時間和資料處理的複雜度太難太模糊了。相比較這種大型應用，我們能夠處理的是單一程式的複雜度和效率。如果每片程序的效率都是相對較優的，那麼我們也不用需要擔心最後組合的應用會過於臃腫緩慢。這篇文章會對程式的演算法時空複雜度，優化方法和等等一切瑣事做解釋，從3-sum和2-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問題的演算法時，我們記錄的是
的訪問次數
（訪問數組次數，無論讀寫）從成本模型出發優化程序
上面的暴力程式碼沒有任何在結果上的問題，在數據較少的情況下執行的還不算太慢。但是如果測試資料量是10的n次方級，那麼這種未經優化的程式碼在時間上會帶來很大的負面效果。我們說暴力的程式碼速度慢，那什麼樣的程式碼才算速度快呢？
成長數量級/時間複雜度我們要說的內容就是時間複雜度，但是我們給他換了個名字－成長數量級。除了不使用大O標記，其他的地方這兩種並沒有什麼差別。我們在實作演算法的時候使用了幾個結構性的原語，例如普通語句，循環，條件判斷，嵌套語句等等，所以成本成長的數量級一般都是
問題規模N的某個
函數#常數層級
#成長的數量級：
1 時間複雜度：
典型程式碼：
a = b + c;
對數層級
成長的數量級：
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，速度快于N2但是慢于线性级别。在归并排序中，按照类似二分的方法确定归并点，对归并到最底层的数据进行复杂度为O(N)的排序，时间复杂度为O(NlogN)。快速排序，归并排序都可以看作是线性对数级别。
增长的数量级： N2
时间复杂度： O(N2)
典型代码：
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
if (arr[i] == -arr[j])
count++;结构性原语：双层循环
举例：检查所有元素对
说明：平方级别的程序一般都是含有两个for循环，初级的排序算法选择排序和插入排序都是这种复杂度。
增长的数量级： N3
时间复杂度： O(N3)
典型代码：
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循环嵌套而成，我们日常的算法很少有这种运算时长。
增长的数量级： 2N
时间复杂度： O(2N)
典型代码：
穷举查找所有真子集
结构性原语：穷举法
举例：穷举查找所有真子集
说明：指数级别的增长在N较大时比较可怕，但是它确是某些问题看起来最优的解法，并不是很常用，等如果需要学习的时候可以专门研究。
先从2-sum问题入手，根据上述复杂度，2-sum问题的暴力解法复杂度为O(N2)，又根据我们的成本模型只考虑访问数组次数，所以我们要在O(N2)的复杂度之内寻求最优解法即可。
从上面得知，排序算法的复杂度是O(NlogN)快于O(N2)，而我们对排序之后的数据进行运算时，已经不是在排序内部进行处理。所以最后计算时间是用加法而不是乘法。所以我们最后的解决策略是：我们先对整个数组进行排序，然后从数组头部依次读取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(N2logN)，感兴趣的朋友可以自己试一试，或者有更简便算法的话，发在评论里我们交流一下。不胜感激。
在首項近似中，我們一般會忽略低階項中的常數係數，但這可能是錯的。例如，我們把函數2N2+cN的近似為 ~ 2N2時，我們的假設是c很小。但如果c可能是10的一個很高次方，該近似是錯誤的。我們要對可能很大的常數保持敏感。
內循環是決定性因素的假設不總是正確的。錯誤的成本模型可能無法得到真正的內循環，也有可能對循環中的某些語句沒有足夠的重視，導致時間估計的錯誤。總而言之，就是成本模型需要改進。
#以上是關於java時間計算的演算法與最佳化方法詳解的詳細內容。更多資訊請關注PHP中文網其他相關文章！
