证明修改后快速排序的运行时间= O(Nk)

Question

这是一个家庭作业的问题,我不是那个找到复杂性但是我正在尽我所能!

• 三向分区是对快速排序的修改,它将元素分成小于,等于和大于枢轴的组.只需要递归地对较小和较大元素的组进行递归排序.显示如果有N个项目但只有k个唯一值(换句话说有很多重复项),则对quicksort的此修改的运行时间为O(Nk).

我的尝试:

平均情况:

树子例程将在以下索引处:

我假设具有重复项的子例程将等于(nk)

• 第一:从0到(i-1)
• 第二:我 - (i +(nk-1))
• 第三名:(i + nk) - (n-1)
• 比较次数=(nk)-1

所以,

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

然后我不确定我将如何继续:S

这可能是一个非常糟糕的开始:$希望找到帮助

Answer 1

首先,你不应该看一下平均情况,因为O(nk)在最坏的情况下可以证明上限,这是一个更强有力的陈述.

您应该查看最大可能的递归深度.在正常的快速排序中,最大深度为n.对于每个级别,完成的操作总数是O(n),O(n^2)在最坏的情况下给出总数.

在这里,不难证明最大可能的深度是k(因为每个级别将删除一个唯一值),这导致O(nk)总数.