插入排序下界以及为什么它与 1/(2^n) 相比？
insertion sort lower bound and why it compare to `1/(2^n)`?
I have one question:
- 我们知道
n!*(1/(2^n)) 与 2^n 相比，但为什么插入排序与 1/(2^n) 相比呢？
我的意思是为什么不像使用 2^n 的插入排序反向示例？
要对输入的 f(n) 部分进行最多 c(n) 次比较（具有两种可能的结果），我们需要 f(n) n！ ≤ 2^c(n)。在显示公式中，他们使用 c(n) = n（这有点太简单了，因为他们需要考虑渐近常数，但无论如何）和 f(n) = 1/2^n，产生所需的公式 n !/2^n ≤ 2^n <=> n! ≤ 4^n，对于大 n 失败。
大概教科书的参考部分已经过了，但是f(n) n！是我们需要区分的输入个数，2^c(n)是我们可以区分c(n)次比较的输入个数。
I have one question:
- 我们知道
n!*(1/(2^n))与2^n相比，但为什么插入排序与1/(2^n)相比呢？
我的意思是为什么不像使用 2^n 的插入排序反向示例？
要对输入的 f(n) 部分进行最多 c(n) 次比较（具有两种可能的结果），我们需要 f(n) n！ ≤ 2^c(n)。在显示公式中，他们使用 c(n) = n（这有点太简单了，因为他们需要考虑渐近常数，但无论如何）和 f(n) = 1/2^n，产生所需的公式 n !/2^n ≤ 2^n <=> n! ≤ 4^n，对于大 n 失败。
大概教科书的参考部分已经过了，但是f(n) n！是我们需要区分的输入个数，2^c(n)是我们可以区分c(n)次比较的输入个数。