歸并排序的遞歸過程如下，該遞歸樹的高度為log2n（計算過程：假設待排序的數組元素個數為n，設高度為x，x意味著n個元素需要連續二分x次才剩下1個元素，即n/2^x=1，x=log2n），每一層的總比較次數為n，所以時間復雜度為nlogn。

快速排序的分析過程類似。快速排序的平均時間復雜度同樣為nlogn。假設在平均情況下每次選取的基準值均為該數組的中間值，因此每次都將數組分成兩半，直到分割到只剩一個元素。假設n個元素平分了x次后只剩1個元素，則n/2^x=1，x=log2n。每次分割后的比較次數為n（參考上圖），所以時間復雜度為nlogn。

總結

以上是生活随笔為你收集整理的归并排序的时间复杂度为什么为nlogn的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。