从n²<8nlog₂(n)推导至n≤43的过程（插入排序vs归并排序）

嘿，我来一步步拆解这个推导过程，帮你彻底弄明白这个临界值怎么来的～

首先，先简化原不等式：
我们从n² < 8n log₂(n)开始，因为输入规模n一定是正整数（不可能有0个或负数个输入元素），所以可以安全地在不等式两边同时除以n（正数，不等号方向不变），得到：
n < 8 log₂(n)

接下来问题就变成了：找到最大的正整数n，使得这个不等式成立。这里要注意，n < 8 log₂(n)是个超越不等式——没法用常规的代数方法直接算出精确的解析解，所以我们得用试值法来找到临界的n值：

我们可以逐个计算不同n对应的8 log₂(n)值，和n本身做比较：

• 当n=40时：8 log₂(40) ≈ 8 * 5.32 = 42.56，40 < 42.56，不等式成立
• 当n=43时：8 log₂(43) ≈ 8 * 5.43 = 43.44，43 < 43.44，不等式依然成立
• 当n=44时：8 log₂(44) ≈ 8 * 5.46 = 43.68，44 > 43.68，不等式不成立

再用实际步数验证一下临界值：

• n=43时，插入排序步数：8*(43)² = 8*1849 = 14792；归并排序步数：64*43*log₂(43) ≈ 14943，显然14792 < 14943，插入排序更快。
• n=44时，插入排序步数：8*(44)² = 8*1936 = 15488；归并排序步数：64*44*log₂(44) ≈ 15375，这时候15488 > 15375，归并排序开始反超。

所以综合下来，满足n² < 8n log₂(n)的最大正整数n就是43，也就是当n ≤ 43时，插入排序的性能优于归并排序。

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