复杂度（Complexity）

复杂度用来描述算法在输入规模增大时，时间或空间的增长趋势。

大 O 记号（Big O）

常见的几个量级：

• O(1)：常数时间
• O(log n)：对数时间
• O(n)：线性时间
• O(n log n)：常见排序复杂度
• O(n^2)：二次时间

一个直观例子

在数组中查找一个元素：

• 从头到尾扫描：O(n)
• 如果数组有序，可以用二分查找：O(log n)

为什么需要它

• 帮你判断算法在大输入下会不会变慢。
• 让你理解“为什么有些方法不可行”。

进一步阅读

复杂度是算法入门最重要的概念之一。