我最近在分析了第k个最小元素算法之后写了一个程序，首先没有重复的情况。
但是，现在我想分析预期的渐近运行时间，以便在完全j重复时找到数组的中位数。我没有为此修改我的代码，因此由于j重复，性能会有所降低。
我不知道如何开始？谁能指出我这样的重复关系？
我推导出以下内容，其中 n 是输入数组的大小
T(n) <= 1/2*T(3/4*n) + 1/2*T(n)
但我很不清楚如何处理涉及的重复键。
谢谢
问问题
199 次
1 回答
0
这里展示的随机解决方案是
T(n) <= T(3/4*n) + n-1 => T(n) <= 4n
算法的复杂性可能取决于j但不要期望它会奇迹般地小于线性时间。为什么？取一个大小为 n/2 的随机数组，将其完全复制并针对重复问题运行理想算法。你会有
T(n) <= 4(n/2) => T(n) <= 2n
当每个元素重复两次时（完全n/2重复）
于 2012-04-23T08:50:16.297 回答