擅长:python、mysql、java
<p>对数组进行分区后,中位数的位置<code>p</code>介于<code>0.3*n</code>和{<cd3>}之间。在</p>
<p>一轮之后,我们有三种可能:</p>
<ol>
<li><code>p == n-k</code>,纯属运气,第一个支点是第<code>k</code>第二大元素,在O(n)中发现(中位数和分区都是O(n))。在</li>
<li><p><code>p > n-k</code>,那么<code>k</code>-第1个最大元素比第一个轴小,我们需要找到第一个部分的第<code>k - (n-p)</code>-第三个最大元素,它最多有<code>0.7*n</code>个元素,因此找到<code>k</code>-第个最大元素的总成本为</p>
<pre><code>T(n) <= T(0.7*n) + C*n
</code></pre></li>
<li><p><code>p < n-k</code>,那么我们需要找到第二部分的第<code>k</code>-第二个最大的元素(在轴之后),该部分最多也是<code>0.7*n</code>个元素大,所以我们再次得到估计值</p>
<pre><code>T(n) <= T(0.7*n) + C*n
</code></pre></li>
</ol>
<p>迭代,我们发现</p>
<pre><code>T(n) <= T((0.7)^k * n) + C*(1 + 0.7 + ... + (0.7)^(k-1))*n
<= T(1) + C/(1 - 0.7)*n
</code></pre>
<p>显然是O(n)。在</p>