按比較排序的最小比較

我讀here我們需要最小的log（n！）比較來使用任何類型的比較排序對n個元素進行排序，因爲我們得到的最大2^n個應該大於n的個案！（排列的數量）。我只是不明白這條線，如何比較導致2^t的情況。例如，當我做3次比較時，假設我得到1> 2，3 < 5，6> 9，我如何得到8個案例？按比較排序的最小比較

來源

2017-09-19 john doe

比較排序中比較次數的下限爲n * log（n）。請參閱https://cs.stackexchange.com/questions/32311/proving-the-lower-bound-of-compares-in-comparison-based-sorting。你認爲哪裏有2^n個案例？ –

@JimMischel我在這裏閱讀https://en.wikipedia.org/wiki/Comparison_sort#Number_of_comparisons_required_to_sort_a_list –

t如何比較導致2^t案件？

如果您將它視爲決策樹，如我在評論中提供的鏈接所示，它將變得更加清晰。

比較單一提供了兩種情況：

(a < b) 
true  false

隨着三個項目，你結束了：

     (a < b) 
      (a < c)     (a < c) 
    (b < c)  (b < c)  (b < c)  (b < c) 
    1  2 3  4 5  6 7  8

正如你可以看到，在兩個分支各比較結果。樹中有八條可能路徑。每個葉節點表示一個結果。

來源

2017-09-19 21:13:58

按比較排序的最小比較

回答

相關問題