大O符號是算法復(fù)雜度的相對表示，它描述了時空復(fù)雜度（時間復(fù)雜度/空間復(fù)雜度）蜓陌。
大O符號是我在大學(xué)里學(xué)過的東西之一觅彰，我了解過這個算法的概念。我知道的不算多钮热，可以回答一些基本的問題填抬，僅此而已。從大學(xué)畢業(yè)以后隧期，我對這個算法的了解基本沒有改變飒责，因為自從我開始工作以來，我沒有使用過它仆潮，也沒有聽到任何同事提到過它宏蛉。所以我想我應(yīng)該花點時間回顧一下它，并在這篇文章中總結(jié)大O符號的基礎(chǔ)知識性置，以及一些代碼示例來幫助解釋它拾并。
什么是大O符號?簡而言之:
它是算法復(fù)雜度的相對表示。
它描述了一個算法如何執(zhí)行和縮放鹏浅。
它描述了函數(shù)增長率的上限嗅义，可以考慮最壞的情況。
現(xiàn)在快速看一下語法:O(n2)隐砸。
n是函數(shù)作為輸入接收的元素個數(shù)芥喇。這個例子是說，對于n個輸入凰萨，它的復(fù)雜度等于n2。
共同復(fù)雜性的比較
從這個表中可以看出械馆，隨著函數(shù)復(fù)雜度的增加胖眷，完成一個函數(shù)所需的計算量或時間可能會顯著增加。因此霹崎，我們希望將這種增長保持在盡可能低的水平珊搀，因為如果函數(shù)不能很好地伸縮而增加了輸入，可能會出現(xiàn)性能問題尾菇。
一些代碼示例應(yīng)該有助于澄清一些關(guān)于復(fù)雜性如何影響性能的問題境析。下面的代碼是用Java編寫的囚枪，但是很明顯，它可以用其他語言編寫劳淆。
O(1)
public boolean isFirstNumberEqualToOne(List<Integer> numbers) {
return numbers.get(0) == 1;
}
O(1) 表示一個函數(shù)链沼，無論輸入大小如何，該函數(shù)總是取相同的值沛鸵。
O(n)
public boolean containsNumber(List<Integer> numbers, int comparisonNumber) {
for(Integer number : numbers) {
if(number == comparisonNumber) {
return true;
}
}
return false;
}
O(n)表示一個函數(shù)的復(fù)雜度括勺，該函數(shù)的復(fù)雜度與輸入的個數(shù)成線性正比增長。這是一個很好的例子曲掰，說明大O符號如何描述最壞的情況疾捍，因為函數(shù)在讀取第一個元素后返回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) 表示一個函數(shù)乱豆，其復(fù)雜度與輸入大小的平方成正比。通過輸入添加更多的嵌套迭代將增加復(fù)雜性吊趾，然后可以用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) 表示一個函數(shù)趾徽，其性能對輸入中的每個元素都加倍续滋。這個例子是斐波那契數(shù)列的遞歸計算。函數(shù)屬于O(2n)孵奶，因為函數(shù)對每個輸入數(shù)遞歸地調(diào)用自身兩次疲酌，直到該數(shù)小于或等于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)表示一個函數(shù)了袁，該函數(shù)的復(fù)雜度隨輸入大小的增加呈對數(shù)增長朗恳。這使得O(log n)函數(shù)可以很好地伸縮，這樣處理較大的輸入就不太可能導(dǎo)致性能問題载绿。
上面的示例使用二分查找來檢查輸入列表是否包含某個數(shù)字粥诫。簡單地說，它在每次迭代中將列表一分為二崭庸，直到找到數(shù)字或讀取最后一個元素怀浆。此方法具有與O(n)示例相同的功能，盡管實現(xiàn)完全不同且更難于理解怕享。但是执赡，這樣做的回報是更大的輸入會帶來更好的性能(如表中所示)。
這種實現(xiàn)的缺點是二進(jìn)制搜索依賴于元素已經(jīng)處于正確的順序函筋。如果在遍歷元素之前需要對元素進(jìn)行排序沙合，那么這就增加了一些開銷。
