请问有关时间复杂度的问题

Question

想问问
F(n)＝O(n²)g(n)＝O(n)
证明g(n)不等于O(f(n))
答案给的证明说是令f(n)等于logn＝O(n²)这样做，这样合理吗
这个时间复杂度的上界需要取最小上界吗？

Answer 1

关于证明 $g(n) ≠ O(f(n))$ 的问题，我们可以采用反证法来证明。

假设 $g(n)=O(f(n))$，也就是存在正常数 $C$ 和 $n_0$ 使得对于所有的 $n≥n_0$，都有 $g(n)≤Cf(n)$ 成立。

那么，我们可以将 $f(n)=n^2$ 代入上式，即可得到：

$$g(n)≤Cn^2 \quad\quad\quad\quad\quad\quad(1)$$

又因为 $g(n)=O(n)$，因此存在正常数 $C_1$ 和 $n_1$ 使得对于所有的 $n≥n_1$，都有 $g(n)≤C_1n$ 成立。

那么，我们可以将 $C$ 替换为 $C_1n_0^2$，$C_1$ 替换为 $C/n_1$，以及 $n_0=\max{n_1,n_2}$，其中 $n_2$ 是使得 $f(n)=n^2$ 在 $g(n)≤Cf(n)$ 式中成立的 $n$ 值，则有：

$$g(n)≤C_1n_0≤\frac{C}{n_1}n_0^2$$

化简后可以得到：

$$n≤\frac{C}{n_1}n_0 $$

但由于 $n_0$ 和 $n_1$ 都是常数，因此当 $n$ 很大时，上式就不再成立。也就是说，假设不成立，因此 $g(n) ≠ O(f(n))$。

至于您提到的时间复杂度的上界需要取最小上界吗，一般我们会取最紧的上界。这是因为如果一个算法复杂度的上界太宽松的话，我们无法准确地判断算法的复杂度情况，也无法对算法进行有效的优化。因此，我们通常会选取最紧的上界，以便更加准确地评估算法的复杂度。