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

Question

这是一个作业问题，我不是在找到complixity，而是在尽我所能！

• 三路分区是对快速排序的修改，它将元素分成小于，等于和大于数据透视的组。只有更小和更大的元素组需要递归排序。显示如果有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

这可能是一个非常糟糕的开局，但：$ 希望找到一个帮助

Answer 1

首先，你不应该看平均的情况下，因为上界的O(nk)可以证明为最坏的情况，这是一个强硬的声明。

你应该看看递归的最大可能深度。在正常的快速排序中，最大深度为n。对于每个级别，完成的操作总数为O(n)，在最坏的情况下总计为O(n^2)。

在这里，不难证明最大可能的深度是k（因为在每个级别将去除一个唯一值），这导致总共O(nk)。

Answer 2

我没有受过正规教育的复杂性。但是如果你把它看作一个数学问题，你可以证明它是一个数学证明。

对于所有的排序算法，在最好的情况下会一直O（n）的为ň元素，因为到ň元素进行排序，你必须要考虑每一个ATLEAST一次。现在，为了对quicksort进行特别的优化，您所做的事情已经简化了这个问题，因为现在，您只是对唯一值进行排序：所有与pivot相同的值已经被认为是排序的，并且凭借其性质，quicksort将确保每个唯一的值将作为操作中某个点的枢轴，因此这消除了重复。

这意味着一个ň大小列表，快速排序必须执行某些操作ñ次（一次在列表中的每个位置），因为它试图对列表进行排序，该操作是试图找到该值在列表中的位置，但是因为您正在有效地处理唯一值，并且其中有这些值，所以快速排序算法必须对每个元素执行比较。所以它执行Nk操作为N大小列表与k独特的元素。

总结：

• 该算法消除了检查，对重复的值。
• 但是，所有排序算法都必须至少查看列表中的每个值。 N个操作
• 对于列表中的每个值，操作都是查找其相对于列表中其他值的位置。
• 因为重复项被删除，所以这只保留k值来检查。
• O（NK）所有的