排序算法中决策树分析

Question

在具有n个元素的排序算法中高度为h的决策树中：

我们有这样的东西：

n! <= 2^h

因此 h>=log(n!)

我知道 n^n 大于 n!，但这里我们讨论的是最坏情况的下限，log(n!) 的图形低于 (log n^n ).所以简单的答案应该是 Ω(log n!)，因为它不能低于那个值。

那么我们怎么能说 h= Ω(nlogn)..?

Answer 1

基本上这里是您的 log(n!) 的近似值：

您可以从 Stirling's approximation 证明它，它是 n!:

的近似值

在那里他们也给你一个不太严格的近似值：

如果您对如何证明它感兴趣，请仔细使用斯特林公式的对数。

Answer 2

你说得对！和 nⁿ 有不同的增长率，但它们的对数（log n! 和 log nⁿ）实际上有相同的增长率。 @Salvador Dali 指出斯特林近似是一种很好的观察方式，但这里有一种不同的观察方式。

首先，请注意 log nⁿ = n log n 通过对数的性质。就这么简单。

那 (log n!) 呢？首先，请注意

log n!

= log (n · (n-1) · (n-2) · .. · 2 · 1)

= log n + log (n-1) + log (n-2) + ... + log 2 + log 1

这又用到了对数的性质。由此可见，log n! = O(n log n)，因为

log n + log (n-1) + log (n-2) + ... + log 2 + log 1

≤ log n + log n + log n + ... + log n + log n (n times)

= n log n

我也要申请 log n! = Ω(n log n)。这是一种查看方式。看上面求和的第n/2项，也就是

log n + log (n-1) + log(n-2) + ... + log(n/2)

注意这个数量不小于

log (n/2) + log (n/2) + log(n/2) + ... + log(n/2) (n/2 times)

= (n/2) log (n/2)

最后一个数量是 Ω(n log n)，所以总的来说我们看到 log n！ = O(n log n) 和那个 log n! = Ω(n log n)，所以 n！ = Θ(n log n)。换句话说，log n!以与 log nⁿ 相同的速率渐近增长，即使原始函数 n!和 nⁿ 有不同的增长率。

希望对您有所帮助！

Analysis of decision tree in sorting algorithms