尋找關於如何計算O（n log n）的複雜度的例子？

我是數據結構的新手，一直在努力把握這些概念。我瞭解Big-O符號，並尋找與O（n log n）有關的示例。我搜索了互聯網，但沒有得到滿意的例子或實現 - 我可以看到O（n log n）的複雜性。有人可以指出一個更好的例子和實現嗎？尋找關於如何計算O（n log n）的複雜度的例子？

預先感謝

來源

2017-08-27 Hussain Patel

目前還不清楚你在問什麼。標題是「如何計算」，然後你說你在「尋找例子」，然後要求一個「滿意的例子或實現」，你可以「看到O（n log n）的複雜性」。函數f（n）= n log n，f（n）= n，f（n）= 1都是O（n log n）。許多有效的排序算法執行O（n log n）比較。你有什麼具體問題？ –

我正在學習，我發佈了這個問題。我正在尋找更多的O（n log n）的例子。謝謝我編輯了我的問題 –

複雜性理論中有一個衆所周知的定理，稱爲大師定理。它的具體情況說，如果一個算法的複雜性T(n)滿足方程

T(n) = a T(n/a) + b*n   (1)

然後

T(n) = O (n log n)    (2)

方程（1）中可以通過分割問題進行解釋，就好像算法作品爲a零件並分別應用於每個零件，然後在完整的輸入上做一些工作。這種算法模式有時被稱爲合併和重組。

考慮在Python

def f(x): 
    if len(x) > 1: 
     x1 = [z for z in x[1:] if z <= x[0]] 
     x2 = [z for z in x[1:] if z > x[0]] 
     return f(x1) + [x[0]] + f(x2) 
    else: 
     return x

此函數實現的遞歸算法，該算法將輸入列表分爲兩個部分，並且獨立地本身適用於每個部分中的以下示例中，然後串接結果。如果我們很幸運，並且x和y部分具有相同的長度，那麼算法的複雜度可以用上面的公式(2)和a = 2來計算。

如果您熟悉排序和Python語言，您會在這裏認識到一種模擬Quicksort的算法，但沒有執行就地排序的複雜性。在Christos給出的答案中提到的合併排序是一個更清晰的例子。

來源

2017-09-01 12:49:16

一個O(nlogn)算法的一個典型的例子是這樣的的Merge Sort。 Here你會發現它的複雜性的詳細計算。一般來說，有很多divide and conquer算法具有這種複雜性。

來源

2017-08-27 07:03:14 Christos

我會建議看看科爾的算法介紹 Page-151（Heapsort）和170（Quicksort）。這些在本書中有詳細的解釋。每種情況下的關鍵思想是，您需要了解正在進行的比較基本操作（在這兩種情況下），然後使用算法本身的特徵進行分析。用於快速排序轉移分析和堆積heapify部分。

本書涵蓋了分析複雜性所需的一切。

來源

2017-08-27 09:30:13 coderredoc

尋找關於如何計算O（n log n）的複雜度的例子？

回答

相關問題