COMP4133AADS 课程练习复习：Lecture 1 算法复杂度

Lecture 1 练习题与解析

在《算法复杂度》这一节中，教材举了两个关于大 O 符号的练习题。下面给出题目原文及详细解答，帮助大家理解如何使用大 O 记号证明函数的渐进增长率。

练习 1

题目： 证明函数 $2n+10$ 属于 $O(n)$。

思路

根据大 O 定义，如果存在常数 $c>0$ 和 $n_0$，使得对于所有 $n\ge n_0$，都有

$2n+10\le c\cdot n,$

则 $2n+10\in O(n)$。

证明

取常数 $c=3$，$n_0=10$。当 $n\ge 10$ 时，十可以用 $n$ 代替：

$2n+10 \le 2n + n = 3n \quad (n \ge 10).$

因此对于 $n\ge n_0$，恒有 $2n+10\le 3n$，从而满足大 O 定义。这说明 $2n+10$ 的增长速度不超过线性函数 $n$ 的常数倍，因此 $2n+10\in O(n)$。

解析

本题告诉我们，在大 O 分析中可以忽略常数项和常数系数。在严格证明时，通过选择适当的常数 $c$ 和阈值 $n_0$ 即可完成证明。

练习 2

题目： 函数 $n^2$ 是否属于 $O(n)$？说明理由。

思路

要检验 $n^2\in O(n)$ 是否成立，需判断是否存在常数 $c>0$ 和 $n_0$，使得当 $n\ge n_0$ 时 $n^2\le c\cdot n$。

证明（反证）

设想存在常数 $c$ 和 $n_0$ 满足上述不等式。将不等式两边同时除以 $n$，得到

$n \le c \quad (n \ge n_0).$

然而随着 $n$ 增大，$n$ 可以无限增长，而 $c$ 为常数，显然不可能满足 $n \le c$ 对所有大于某个阈值的 $n$ 都成立。因此不存在这样的 $c$ 和 $n_0$，所以 $n^2\notin O(n)$。

结论

由于二次函数的增长速度严格快于一次函数，没有常数倍可以将 $n^2$ 的增长率压在 $n$ 之下，因此 $n^2$ 不属于 $O(n)$。

小结

通过以上两题可以看到，大 O 分析强调的是函数增长率的上界。第一题利用不等式和恰当的常数证明了 $2n+10$ 与线性函数同阶；第二题则用反证法说明了二次函数的增长速度无法用一次函数的常数倍控制。熟练掌握这些证明技巧，有助于后续课程对复杂算法的渐进分析。