大O符號是算法複雜度的相對表示。它描述了時空複雜度.
大O符號是我在大學裡學過的東西之一,我了解過這個算法的概念。我知道的不算多,可以回答一些基本的問題,僅此而已。從大學畢業以後,我對這個算法的了解基本沒有改變,因為自從我開始工作以來,我沒有使用過它,也沒有聽到任何同事提到過它。所,我想我應該花點時間回顧一下它,並在這篇文章中總結大O符號的基礎知識,以及一些代碼示例來幫助解釋它。
什麼是大O符號?簡而言之
它是算法複雜度的相對表示。
它描述了一個算法如何執行和縮放。
它描述了函數增長率的上限,可以考慮最壞的情況。
現在快速看一下語法:O(n2)。
n是函數作為輸入接收的元素個數。這個例子是說,對於n個輸入,它的複雜度等於 n2。
共同複雜性的比較
從這個表中可以看出,隨著函數複雜度的增加,完成一個函數所需的計算量或時間可能會顯著增加。因此,我們希望將這種增長保持在儘可能低的水平,因為如果函數不能很好地伸縮而增加了輸入,可能會出現性能問題。
顯示操作數量如何隨複雜性增加的圖表。
一些代碼示例應該有助于澄清一些關於複雜性如何影響性能的問題。下面的代碼是用Java編寫的,但是很明顯,它可以用其他語言編寫。
O(1)public boolean isFirstNumberEqualToOne(List<Integer> numbers) {
return numbers.get(0) == 1;
}
O(1) 表示一個函數,無論輸入大小如何,該函數總是取相同的值。
O(n)public boolean containsNumber(List<Integer> numbers, int comparisonNumber) {
for(Integer number : numbers) {
if(number == comparisonNumber) {
return true;
}
}
return false;
}
O(n)表示一個函數的複雜度,該函數的複雜度與輸入的個數成線性正比增長。這是一個很好的例子,說明大O符號如何描述最壞的情況,因為函數在讀取第一個元素後返回true,或者在讀取所有n個元素後返回false。
O(n2)public static boolean containsDuplicates(List<String> input) {
for (int outer = 0; outer < input.size(); outer++) {
for (int inner = 0; inner < input.size(); inner++) {
if (outer != inner && input.get(outer).equals(input.get(inner))) {
return true;
}
}
}
return false;
}
O(n2) 表示一個函數,其複雜度與輸入大小的平方成正比。通過輸入添加更多的嵌套迭代將增加複雜性,然後可以用3次總迭代表示O(n3),用4次總迭代表示O(n4) 。
public int fibonacci(int number) {
if (number <= 1) {
return number;
} else {
return fibonacci(number - 1) + fibonacci(number - 2);
}
}
O(2n) 表示一個函數,其性能對輸入中的每個元素都加倍。這個例子是斐波那契數列的遞歸計算。函數屬於O(2n),因為函數對每個輸入數遞歸地調用自身兩次,直到該數小於或等於1。
O(log n)public boolean containsNumber(List<Integer> numbers, int comparisonNumber) {
int low = 0;
int high = numbers.size() - 1;
while (low <= high) {
int middle = low + (high - low) / 2;
if (comparisonNumber < numbers.get(middle)) {
high = middle - 1;
} else if (comparisonNumber > numbers.get(middle)) {
low = middle + 1;
} else {
return true;
}
}
return false;
}
O(log n)表示一個函數,該函數的複雜度隨輸入大小的增加呈對數增長。這使得O(log n)函數可以很好地伸縮,這樣處理較大的輸入就不太可能導致性能問題。上面的示例使用二分查找來檢查輸入列表是否包含某個數字。簡單地說,它在每次迭代中將列表一分為二,直到找到數字或讀取最後一個元素。此方法具有與O(n)示例相同的功能,儘管實現完全不同且更難於理解。但是,這樣做的回報是更大的輸入會帶來更好的性能(如表中所示)。
這種實現的缺點是二進位搜索依賴於元素已經處於正確的順序。如果在遍曆元素之前需要對元素進行排序,那麼這就增加了一些開銷。
關於大O符號還有很多內容要講,但希望你們現在對大O符號的含義有了一個基本的概念以及如何將它轉換成你寫的代碼。如果有必要,大O符號還有後續要講,若有不懂,歡迎下方留言關注,我會一一解答。
長按二維碼 ▲
訂閱「架構師小秘圈」公眾號
如有啟發,幫我點個在看,謝謝↓