这种复发的解决方案是什么？
T(n) = T(n/1000) + T(999n/1000) + cn。
我认为它的 O(n log n) 因为每个级别完成的工作将是 cn 并且树的高度将 log n 到 1000/999 的底，但我不确定推理是否有效。那是对的吗？
问问题
126 次
1 回答
0
需要注意的一点是，对于第一个 log 1000 n 层，递归的所有分支都将处于活动状态（即 n / 1000 个案例的分支不会触底）并且每层完成的工作将是 Θ(n ）。这为您提供了运行时的即时下限为 Ω(n log n)，因为有 Θ(log n) 层每个都在做 Θ(n) 工作。
对于低于此的层，工作开始下降，因为 n / 1000 案例的分支将触底。但是，您可以通过假设树中的每一层都会做 Θ(n) 的工作来限制所做的工作。在那种情况下，在 999n/1000 的情况触底之前会有 log 1000/999 n 层，所以你得到 O(n log n) 的上限，因为你有 Θ(log n) 层在做 Θ(n) 工作每个。
由于完成的工作是 Ω(n log n) 和 O(n log n)，因此运行时间是 Θ(n log n)。
希望这可以帮助！
于 2013-10-29T23:52:42.910 回答