关于算法复杂度表达式中主导项判定条件的推导疑问

嘿，我来帮你把这三个主导项的判定条件掰明白，其实核心就是两两比较复杂度项的大小，把每个项成为最大值的区间找出来就行，咱们一步步推：

首先回忆一下，我们要找的是渐近意义下的主导项——也就是当m和n都趋向无穷大时，哪个项能“压过”另外两个项，成为整个复杂度表达式里的核心部分。

Case 1：$m^{{\frac{2}{3}}n}{\frac{2}{3}}$ 成为主导项的条件 #

要让这个项主导，得同时满足它比m大，也比n大（渐近意义下）：

1. 先比它和m的大小：$m^{{\frac{2}{3}}n}{\frac{2}{3}} \geq m$
   两边同时除以$m$（m是正整数，没问题），得到 $n^{\frac{2}{3}} \geq m^{\frac{1}{3}}$
   两边同时立方（立方是单调递增操作，不改变不等式方向），就得到 $n^2 \geq m$，也就是 $m \leq n^2$
2. 再比它和n的大小：$m^{{\frac{2}{3}}n}{\frac{2}{3}} \geq n$
   两边同时除以$n$，得到 $m^{\frac{2}{3}} \geq n^{\frac{1}{3}}$
   同样两边立方，得到 $m^2 \geq n$，也就是 $m \geq \sqrt{n}$

把这两个条件合起来，就是 $\sqrt{n} < m < n^2$（用<而不是≤是为了更清晰区分区间边界，渐近情况下差异不大），这时候这个交叉项就是最大的主导项。

Case 2：$m$ 成为主导项的条件 #

要让m主导，得让m同时比另外两个项都大：

1. 先比m和$m^{{\frac{2}{3}}n}{\frac{2}{3}}$的大小：$m \geq m^{{\frac{2}{3}}n}{\frac{2}{3}}$
   两边除以$m^{\frac{2}{3}}$，得到 $m^{\frac{1}{3}} \geq n^{\frac{2}{3}}$
   立方后得到 $m \geq n^2$
2. 这时候你会发现，当$m > n^{2$时，m肯定比n大（因为n≥1时，$n}2 \geq n$），所以不需要额外再验证m≥n的条件。

所以只要$m > n^2$，m就是整个表达式里的主导项。

Case 3：$n$ 成为主导项的条件 #

要让n主导，得让n同时比另外两个项都大：

1. 先比n和$m^{{\frac{2}{3}}n}{\frac{2}{3}}$的大小：$n \geq m^{{\frac{2}{3}}n}{\frac{2}{3}}$
   两边除以$n^{\frac{2}{3}}$，得到 $n^{\frac{1}{3}} \geq m^{\frac{2}{3}}$
   立方后得到 $n \geq m^2$，也就是 $m \leq \sqrt{n}$
2. 同样，当$m < \sqrt{n}$时，m肯定比n小（因为n≥1时，$\sqrt{n} \leq n$），所以不需要额外验证n≥m的条件。

所以只要$m < \sqrt{n}$，n就是整个表达式里的主导项。

说白了就是通过不等式变形+立方操作把幂次拆开，把每个项成为最大值的区间找出来，你的教授给的条件就是这么推出来的～

备注：内容来源于stack exchange，提问作者user1326505