簡評：任何讀過「編程珠璣」或任何其他計(jì)算機(jī)科學(xué)書籍的人都會遇到涉及O（N log N）或其他看似奇怪的語法的章節(jié)员凝，本文將幫助了解大 O 的基礎(chǔ)知識懒鉴。
大 O 表示法用來在計(jì)算機(jī)科學(xué)中描述算法的性能或復(fù)雜性盟萨，大 O 具體描述了最壞的情況鼓拧，并且可以描述算法所需的執(zhí)行時(shí)間或所使用的空間（內(nèi)存或磁盤）嗜傅。
作為程序員和數(shù)學(xué)家瘦锹，我發(fā)現(xiàn)了徹底理解大 O 的最好方法是在代碼中生成一些例子畦戒，下面是一些常見的增長順序以及可能的描述和示例方库。
O(1)
O(1) 描述了一種無論輸入數(shù)據(jù)集的大小如何總是在相同的時(shí)間（或空間）內(nèi)運(yùn)行的算法。
bool IsFirstElementNull(IList<String> elements)
{
return elements[0] == null;
}
O(N)
O(N) 描述了一種性能線性增長并且與輸入數(shù)據(jù)集的大小成正比的算法障斋。下面的示例還演示了大 O 如何支持最壞情況的性能方案纵潦，在循環(huán)的任何一個(gè)迭代期間都可以找到匹配的字符串，并且函數(shù)將提前返回垃环，但是大 O 表示法將始終假定算法將執(zhí)行最大的迭代次數(shù)邀层。
bool ContainsValue(IEnumerable<string> elements, string value)
{
foreach (var element in elements)
{
if (element == value) return true;
}
return false;
}
O(N2)
O(N2) 表示一種性能與輸入數(shù)據(jù)集大小的平方成正比的算法，常見于涉及數(shù)據(jù)集嵌套迭代的算法中遂庄。更深的嵌套迭代將導(dǎo)致 O(N3)寥院、O(N?) 等。
bool ContainsDuplicates(IList<string> elements)
{
for (var outer = 0; outer < elements.Count; outer++)
{
for (var inner = 0; inner < elements.Count; inner++)
{
// Don't compare with self
if (outer == inner) continue;
if (elements[outer] == elements[inner]) return true;
}
}
return false;
}
O(2^N)
O(2^N) 表示一種隨著對輸入數(shù)據(jù)集的每次加法而增長加倍的算法涛目。O(2^N) 函數(shù)的增長曲線是指數(shù) —— 從非常小的開始秸谢，然后是急劇上升。O(2^N) 函數(shù)的一個(gè)例子是 Fibonacci 數(shù)的遞歸計(jì)算：
int Fibonacci(int number)
{
if (number <= 1) return number;
return Fibonacci(number - 2) + Fibonacci(number - 1);
}
希望這有助于消除圍繞大 O 符號和許多常見增長函數(shù)的一些謎團(tuán)霹肝，在處理需要大規(guī)模操作的算法時(shí)估蹄，掌握大 O 是一個(gè)重要的工具，允許在處理不同的數(shù)據(jù)集時(shí)做出正確的選擇沫换。
原文鏈接：A beginner's guide to Big O notation
推薦閱讀：給 console 添加顏色
