如何证明线性搜索最坏情况下的比较次数属于Θ(n)？

别慌，你已经抓对了核心——要证明2n+2属于Θ(n)，确实就是要分别证明它属于O(n)和Ω(n)，我给你一步步拆解，用最直白的方式讲清楚：

第一步：证明2n + 2 ∈ O(n) #

先回忆大O的定义：如果能找到两个常数——一个正数c，一个正整数n₀——使得当所有n ≥ n₀时，2n + 2 ≤ c * n，那我们就说2n+2是O(n)的。

那怎么找这两个常数呢？其实很简单：

• 我们可以选c = 4，n₀ = 1。
• 验证一下：当n≥1时，2n + 2 ≤ 4n吗？
  把不等式变形一下：2 ≤ 4n - 2n → 2 ≤ 2n → 1 ≤ n，这正好符合n≥1的条件！所以对于所有n≥1，2n+2 ≤4n都成立，满足大O的定义。

当然你也可以选其他常数组合，比如c=3，n₀=2：当n≥2时，2n+2 ≤3n → 2 ≤n，n≥2时显然成立，也是完全没问题的。

第二步：证明2n + 2 ∈ Ω(n) #

再看大Ω的定义：同样找两个正数c和n₀，使得*当所有n ≥n₀时，2n +2 ≥ c n。

这一步更简单：

• 选c=1，n₀=1。
• 验证：2n+2 ≥1*n → n +2 ≥0，对于所有正整数n来说，这显然永远成立。
• 或者选更“紧”的常数，比如c=2，n₀=1：2n+2 ≥2n → 2≥0，同样对所有n≥1都成立，完全符合大Ω的定义。

第三步：结合起来得到Θ(n) #

因为我们已经证明了2n+2既属于O(n)（它的增长速度不会比n快），又属于Ω(n)（它的增长速度不会比n慢），根据大Θ的定义——同时满足大O和大Ω的函数就属于Θ(g(n))——所以2n+2 ∈ Θ(n)。

说白了，大Θ就是在说：当n足够大时，2n+2的增长速度和n是“同阶”的，前面的系数2和常数项2在n趋向无穷大时，对整体增长趋势的影响可以忽略不计，所以我们可以用Θ(n)来描述它的时间复杂度。

内容的提问来源于stack exchange，提问作者user20984724