一、理解時間複雜度
了解nlogn需要先理解時間複雜度的概念，時間複雜度是演算法的一種度量方式，表示運行時間和數據規模之間的增長關係。例如當n的規模增大時，O(n)的時間複雜度表示演算法運行時間增長的比較快，而O(logn)和O(nlogn)的時間複雜度則增長得更慢，也就是效率更高。
二、nlogn的產生
在計算機科學領域，首先提出計算機運算的次數和輸入變數之間的關係是 R. Hamming。在1960s，D. Knuth 進一步發展了這個概念，並在其著作The Art of Computer Programming 中系統講解了這個主題。
在排序演算法領域，有很多複雜度優秀的演算法，但quicksort、歸併排序和heapsort分別使用快排、歸併和堆排序來保證O(nlogn)的時間複雜度。
三、nlogn常見應用場景
1.排序演算法：如上所述，快速排序、歸併排序和堆排序都是O(nlogn)時間複雜度的經典演算法。
2.搜索演算法：二分查找在有序序列中的時間複雜度也是O(logn)，可看做O(nlogn)的特殊情況。
3.動態規劃：自底向上的斐波那契數列演算法時間複雜度也是O(nlogn)。
四、從代碼實現看nlogn
/**
* 快速排序
* @param {Array} arr 待排序數組
*/
function quickSort(arr) {
if (arr.length <= 1) return arr;
const base = arr[0];
const left = [], right = [];
for (let i = 1; i < arr.length; i++) {
arr[i] < base ? left.push(arr[i]) : right.push(arr[i]);
}
return quickSort(left).concat([base], quickSort(right));
}
以上是一個經典的快速排序實現，利用分治思想不斷遞歸劃分左右子序列直到長度為1，時間複雜度為O(nlogn)。
五、總結
nlogn演算法作為一種高效的演算法設計思想，在計算機科學領域被廣泛應用。我們應該在實際問題中掌握nlogn的原理和實現方法，以便提高演算法效率，為軟體工程帶來更多的價值。
原創文章，作者：小藍，如若轉載，請註明出處：https://www.506064.com/zh-tw/n/233694.html
微信掃一掃 
支付寶掃一掃 