简评：任何读过「编程珠玑」或任何其他计算机科学书籍的人都会遇到涉及O（N log N）或其他看似奇怪的语法的章节，本文将帮助了解大 O 的基础知识。
大 O 表示法用来在计算机科学中描述算法的性能或复杂性，大 O 具体描述了最坏的情况，并且可以描述算法所需的执行时间或所使用的空间（内存或磁盘）。
作为程序员和数学家，我发现了彻底理解大 O 的最好方法是在代码中生成一些例子，下面是一些常见的增长顺序以及可能的描述和示例。
O(1)
O(1) 描述了一种无论输入数据集的大小如何总是在相同的时间（或空间）内运行的算法。
bool IsFirstElementNull(IList<String> elements)
{
return elements[0] == null;
}
O(N)
O(N) 描述了一种性能线性增长并且与输入数据集的大小成正比的算法。下面的示例还演示了大 O 如何支持最坏情况的性能方案，在循环的任何一个迭代期间都可以找到匹配的字符串，并且函数将提前返回，但是大 O 表示法将始终假定算法将执行最大的迭代次数。
bool ContainsValue(IEnumerable<string> elements, string value)
{
foreach (var element in elements)
{
if (element == value) return true;
}
return false;
}
O(N²)
O(N²) 表示一种性能与输入数据集大小的平方成正比的算法，常见于涉及数据集嵌套迭代的算法中。更深的嵌套迭代将导致 O(N³)、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) 表示一种随着对输入数据集的每次加法而增长加倍的算法。O(2^N) 函数的增长曲线是指数 —— 从非常小的开始，然后是急剧上升。O(2^N) 函数的一个例子是 Fibonacci 数的递归计算：
int Fibonacci(int number)
{
if (number <= 1) return number;
return Fibonacci(number - 2) + Fibonacci(number - 1);
}
希望这有助于消除围绕大 O 符号和许多常见增长函数的一些谜团，在处理需要大规模操作的算法时，掌握大 O 是一个重要的工具，允许在处理不同的数据集时做出正确的选择。
原文链接：A beginner's guide to Big O notation
推荐阅读：给 console 添加颜色
