为什么不是堆排列的lg（n！）？

我阅读CLRS和它说的堆排序是为什么不是堆排列的lg（n！）？

HEAPSORT(A): 
BUILD-MAX-HEAP(A); 
for (i = A.length; i >= 1; i++) 
{ 
    exchange A[1] with A[i]; 
    A.heap-size = A.heap-size - 1; 
    MAX-HEAPIFY(A,1); 
}

MAX_HEAPIFY是O(lg n)。这本书说它运行MAX-HEAPIFY n次，因此它是O(n lg n)时间。

但是如果堆的大小缩小1倍，每次迭代不应该是O(lg n!)？

这将是lg 1 + lg 2 ... + lg(n-1) + lg (n) = lg(n!)，对吧？

来源

2014-04-07 user3504876

在这种情况下，我加入基地2的对数，这样才能保证对数的参数会一起 – user3504876

O（N日志n）和O（日志乘n！）是一样的... –

'n！ = n *（n-1）*（n-2）... * 1' =>'n！ 'n！= O（n^n）'=>'O（lg（n！）= O（nlogn）' – arunmoezhi

其实这是Stirling's Approximation：

O(log(n!)) = O(nlogn)

来源

2014-04-07 00:59:09 chrk

因此我的说法是否有意义？我开始认为我只是不明白教科书 – user3504876

是的，你的陈述是正确的。 – chrk

为什么不是堆排列的lg（n！）？

回答

相关问题