我被要求找出大小為g的組的中位數演算法的一般形式的運行時間。從常見的例子來看g=3,5,7，T(n)=T(n/5) T(2n/3) cn，T(n)=T(n/5) T(7n/10) cn。和T(n)=T(n/7) T(5n/7) cn，分別表示奇數的一般將是T(n)=T(n/g) T(1-(n/(2g)*(g 1)/2)) cn。
然而，我正在為如何使用偶數g的中位數而苦惱，因為中位數將存在于兩個元素之間，而不是實際存在于集合本身。有人告訴我，我可以忽略地板和天花板。直覺告訴我，它應該是T(n)=T(n/g) T(1-(n/(2g)*(g)/2)) cn，但我不禁覺得我錯過了什么。
有誰能就該演算法對偶陣列的作用給出建議嗎？我想，一旦我理解了這個演算法，我就應該能夠找到運行時間。
uj5u.com熱心網友回復：
你的分析是正確的；當g是偶數時，你可以將運行時間表示為T(n) = T(n/g) T(3n/4) cn，這是你簡化的表達方式；只要g > 4，無論g是偶數還是奇數，歸納證明都是O(n)。
要想知道為什么這個方程是真的，最簡單的方法是思考奇數g的T(n)的運算式是如何得出的。我們可以假設我們的輸入串列 A 沒有重復的元素，而不喪失一般性（通過稍微修改演算法，或者用元組（A[i]，i）替換每個元素 A[i]，并使用詞法比較）。這使得分析變得更加容易。
現在，Median-of-Medians Quickselect的運行時間是基于它所做的三件事：
。
- 在大小為
ceil(n/g)的'medians'串列上遞回呼叫自己，以找到median-of-mediansM cn作業，對專案進行分組，圍繞M對串列進行磁區，并找到每個小組-g的中位數，并且- 在所有元素小于
M的磁區、所有元素大于M的磁區上遞回呼叫自身，或者立即回傳。
忽略上限和一個加法O(1)常數，這就得到了T(n) = T(n/g) T(New Partition Size) cn。新磁區大小的最大值是多少？它是max(# elements less than M, # elements greater than M)。
當g是奇數時，我們有一半的n/g組的中位數小于M（所以（g-1）/2，加上1為中位數。該組中的元素小于M），而一半的中位數大于M（同樣，為每個這樣的組提供(g 1)/2'大于M'元素）。
由于你將偶數串列的中位數定義為中間兩個元素的算術平均值，這就變得更加簡單了：一半的n/g組的中位數小于M，而每組中正好有一半的元素小于其中位數，因此小于M；同樣的邏輯適用于大于。這意味著我們至少消除了（n/g的一半乘以g/2），或n/4元素，留下3n/4作為最大的新磁區大小和T（n）=T（n/g） T（3n/4） cn。
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/332566.html
標籤：
上一篇：Pymongo游標迭代瓶頸