我最近在分析了第k小元素算法后写了一个程序，首先没有重复的情况。
但是，现在我想分析预期的渐近运行时间，以便在恰好有 j 个重复项时找到数组的中值。我没有为此修改我的代码，因此由于 j 重复，性能会降低一点。
我不确定如何开始？任何人都可以指出这种递推关系吗？
我推导了以下内容，其中 n 是输入数组的大小
T(n) <= 1/2*T(3/4*n) + 1/2*T(n)
但我很不清楚如何处理涉及的重复键。
谢谢
最佳答案
随机解 as demonstrated here是
T(n) <= T(3/4*n) + n-1 => T(n) <= 4n
算法的复杂度可能取决于 j 但不要指望它会奇迹般地小于线性时间。为什么？取一个大小为 n/2 的随机数组，将其完全复制并运行针对重复问题的理想算法。你会有
T(n) <= 4(n/2) => T(n) <= 2n
当每个元素被复制两次时(恰好 n/2 重复)
关于algorithm - 有骗子的选拔程序？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/10274822/