嘿，我来帮你一步步拆解这两个大O符号的问题，找出满足$f(n) = \mathcal{O}(n^c)$的最小整数常数$c$～

首先得回忆大O符号的核心定义：$f(n) = \mathcal{O}(n^c)$意味着存在某个固定的正数$M$和某个起始值$n_0$，当$n \geq n_0$时，$|f(n)| \leq M \cdot n^c$永远成立。

我们来一步步试值：

• 先试$c=2$：把$f(n)$代入不等式，得到$\dfrac{n^2}{2} \leq M \cdot n^{2$。两边同时除以$n}2$（因为$n \geq 1$，$n^2$是正数，不等号方向不变），得到$\dfrac{1}{2} \leq M$。这太简单了，只要取$M=1$，$n_0=1$，所有$n \geq 1$时$\dfrac{n^2}{2} \leq 1 \cdot n^2$都成立，所以$c=2$是可行的。
• 那能不能取更小的整数$c=1$？代入后得到$\dfrac{n^2}{2} \leq M \cdot n$，化简为$\dfrac{n}{2} \leq M$。但当$n$越来越大时，$\dfrac{n}{2}$会无限增大，不可能被一个固定的$M$限制住，所以$c=1$不满足条件。

结论：第一部分的最小整数$c$是2。

这里要记住一个关键的增长速度规律：任何对数函数的任何次幂，增长速度都比任意正次幂的多项式慢。换句话说，不管你给对数加多少次幂（比如$(\log n)^3$、$(\log n)^{{100}$），它最终都会被$n}\epsilon$（$\epsilon$是任意小的正数，比如0.1、0.001）超过。

同样用定义来试值：

• 先试$c=1$：代入不等式得$n (\log_2 n)^3 \leq M \cdot n$，两边约掉$n$后得到$(\log_2 n)^3 \leq M$。但随着$n$增大，$\log_2 n$会无限变大，它的三次方也会无限增长，不可能被固定的$M$限制，所以$c=1$不行。
• 再试$c=2$：这时候看比值$\dfrac{f(n)}{n^2} = \dfrac{(\log_2 n)^3}{n}$。根据刚才说的规律，当$n$趋近于无穷大时，这个比值会趋近于0——因为$n$的增长速度远远快于$(\log_2 n)^3$。也就是说，我们总能找到一个足够大的$n_0$和固定的$M$（比如$M=1$），当$n \geq n_0$时，$\dfrac{(\log_2 n)^3}{n} \leq 1$，也就是$n (\log_2 n)^3 \leq 1 \cdot n^2$，满足大O的定义。

有没有更小的整数$c$？刚才已经排除了$c=1$，所以最小整数$c$只能是2。

举个直观的例子帮你理解：当$n=2^{100}$时，$(\log_2 n)^3 = 100^3 = 1000000$，而$n=2^{100}≈10{30}$，这时候$\dfrac{(\log_2 n)^3}{n}≈10{-24}$，远远小于1，完全符合我们的结论。

内容的提问来源于stack exchange，提问作者Human Cyborg Relations