基础与复杂度
时间复杂度
时间复杂度回答一个很实用的问题：当输入变大时，运行时间是怎样增长的？我们不用秒表去掐你的程序——那会受你的笔记本、所用语言、甚至机器有多忙的影响——而是把算法执行的基本步骤数，写成输入规模（通常记作 n）的一个函数。秒表上的秒数会因机器而异；增长的「形状」却不会。我们在意的正是这个形状，因为它能预测当 n 是一千、一百万、十亿时会发生什么。
我们用大 O 记号来描述这个形状，只保留最主导的那一项，并丢掉常数。扫一遍列表去找最大值，会把每个元素碰一次，所以是 O(n)——线性：输入翻倍，工作量大致翻倍。把每一对元素都比一遍是 O(n^2)——平方级：输入翻倍，工作量翻成四倍。二分查找每一步把搜索范围砍半，所以是 O(log n)——几乎不怎么涨。而无论集合多大、耗时都一样的查找（比如一个好的哈希表），是 O(1)——常数。
之所以要紧，是因为一笔残酷的算术。当 n = 1,000,000 时，一个 O(n) 的算法大约做一百万步；一个 O(n^2) 的算法要做一百万乘一百万——一万亿步——这能把一项一秒的任务变成跑上好几天的任务。所以一个谨慎的程序员对一个算法问的第一个问题，不是「它能用吗？」，而是「它的时间是怎么随规模放大的？」。我们通常报告最坏情况（在规模为 n 的所有输入里算法最慢能慢到什么程度），因为那是你能依赖的保证；不过平均情况分析和摊还分析会把故事的其余部分讲完。
int pairs = 0;
for (int i = 0; i < n; ++i) // runs n times
for (int j = i + 1; j < n; ++j) // ~n times each
if (a[i] == a[j]) ++pairs; // O(n^2) comparisons total对 n 个元素的两层嵌套循环，做的比较数量在 n^2 量级——平方时间。
又称
另见