在计算中位数时，我们知道如果将输入数组分成 5 个子组并递归求解，我们将得到 O(n) 复杂度，但如果将数组分成 3 个，则不会返回 O(n ) 复杂性。
有人知道如何证明吗？
问问题
2621 次
2 回答
2
会nlg(n)的
试着画出它的递归树：每一层的总成本等于n，这棵树的深度是lg(n)。
注意：实际上它的深度在log(n)底数 3 和log(n)底数 3/2 之间，但由于所有底数的对数顺序相同，我们可以将其视为lg(n)。
于 2013-09-25T06:50:50.673 回答
0
看起来标题中的递归是错误的，但我认为解决递归的主定理会很方便。你可以证明，从一个分母到另一个分母会让你陷入另一种情况，O(n)从而变得更糟。
于 2013-09-25T06:37:27.367 回答