隨著使用電腦的經驗的增長,人們在使用電腦編寫程式的時候,不可避免的會發出這樣的疑問:
##我的程式運行一次需要多久?當我們開啟一個網頁或傳輸一個檔案或開啟一個播放器時,你也肯定問過自己上面的問題。但是在這種情況下估計時間和資料處理的複雜度太難太模糊了。相比較這種大型應用,我們能夠處理的是單一程式的複雜度和效率。如果每片程序的效率都是相對較優的,那麼我們也不用需要擔心最後組合的應用會過於臃腫緩慢。這篇文章會對程式的演算法時空複雜度,優化方法和等等一切瑣事做解釋,從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中文網其他相關文章!