證明修改後快速排序的運行時間= O（Nk）

這是一個作業問題，我不是在找到complixity，而是在盡我所能！證明修改後快速排序的運行時間= O（Nk）

三路分區是對快速排序的修改，它將元素分成小於，等於和大於數據透視的組。只有更小和更大的元素組需要遞歸排序。顯示如果有N個項目但只有k個唯一值（換句話說，有許多重複項），則此修改爲快速排序的運行時間爲O（Nk）。

我嘗試：

樹子程序將在這些指數：

平均情況

我認爲是有重複的子程序項目將等於（NK）

第一：從0 - 至第（i-1）
二：I - （I +（ NK-1））
第三：（ⅰ+ NK） - （N-1）
比較次數=（NK）-1

所以，

T(n) = (n-k)-1 + Sigma from 0 until (n-k-1) [ T(i) + T (i-k)]

然後我「M不知道我怎麼我會繼續：S

這可能是一個非常糟糕的開局，但：$ 希望找到一個幫助

來源

2011-12-22 Sosy

你也可以試試這裏：[理論計算機科學（StackExchange）]（http://cstheory.stackexchange.com/）。 – Groo 2011-12-22 11:47:32

快速排序通常只分析一般情況。這是否也是這種情況，或者你說的是最壞的情況？ – 2011-12-22 12:07:30

@格羅，看來我正在尋找答案，但thnx！ – Sosy 2011-12-22 12:19:04

首先，你不應該看平均的情況下，因爲上界的O(nk)可以證明爲最壞的情況，這是一個強硬的聲明。

你應該看看遞歸的最大可能深度。在正常的快速排序中，最大深度爲n。對於每個級別，完成的操作總數爲O(n)，在最壞的情況下總計爲O(n^2)。

在這裏，不難證明最大可能的深度是k（因爲在每個級別將去除一個唯一值），這導致總共O(nk)。

來源

2011-12-22 12:28:53 interjay

太棒了！我試圖通過一個例子來證明深度：1 1 2 2 3 4. so level_2：2 2 3 4，level_3：3 4和level_5：4.這就是爲什麼我們說深度是正確的？嗯，我必須找到公式？我試圖和我得到T（n）= T（n-k）+ n，是嗎？非常感謝@ @ interjay！ – Sosy 2011-12-22 20:34:24

我沒有受過正規教育的複雜性。但是如果你把它看作一個數學問題，你可以證明它是一個數學證明。

對於所有的排序算法，在最好的情況下會一直O（n）的爲ň元素，因爲到ň元素進行排序，你必須要考慮每一個ATLEAST一次。現在，爲了對quicksort進行特別的優化，您所做的事情已經簡化了這個問題，因爲現在，您只是對唯一值進行排序：所有與pivot相同的值已經被認爲是排序的，並且憑藉其性質，quicksort將確保每個唯一的值將作爲操作中某個點的樞軸，因此這消除了重複。

這意味着一個ň大小列表，快速排序必須執行某些操作ñ次（一次在列表中的每個位置），因爲它試圖對列表進行排序，該操作是試圖找到該值在列表中的位置，但是因爲您正在有效地處理唯一值，並且其中有這些值，所以快速排序算法必須對每個元素執行比較。所以它執行Nk操作爲N大小列表與k獨特的元素。

總結：

該算法消除了檢查，對重複的值。
但是，所有排序算法都必須至少查看列表中的每個值。 N個操作
對於列表中的每個值，操作都是查找其相對於列表中其他值的位置。
因爲重複項被刪除，所以這隻保留k值來檢查。
O（NK）所有的

來源

2011-12-22 12:01:19 amnn

哇，當你這麼說的時候，這很清楚，非常感謝@asQuirreL！ – Sosy 2011-12-22 12:22:03

證明修改後快速排序的運行時間= O（Nk）

回答

相關問題