递推关系：T(n) = n*T(n/2)

Question

我一直在努力解决这个问题，但我卡在了最后一点，我的大学讲师也不想帮助我:)

T(1) = 1

T(n) = n*T(n/2)

T(n/2) = n/2 * T(n/4);
T(n/4) = n/4 * T(n/8);
T(n/8) = n/8 * T(n/16);

The four forms:
1) T(n) = n * T(n/2);         k = 1
2) T(n) = (n^2)/2 * T(n/4);   k = 2
3) T(n) = (n^3)/8 * T(n/8);   k = 3
4) T(n) = (n^3)/64 * T(n/16); k = 4

T(n) = (n^k)/??? * T(n/k^2)

我能看出关系，但我不太清楚是什么？？？等于，也不知道如何继续。老实说，任何帮助将不胜感激。谢谢！

Answer 1

嗯，我的第一个猜测是“？？？”等于 2^(k-1), 因为那样的话序列就像 2^1-1=1、2^2-1=2 等等...

那么你的递归关系如下：

T(n)=(n^k)/(2^(k-1)) * T(n/k^2)

那么你可以通过归纳证明这对任何n都成立。我假设这是一个 algorithm-related 问题，这会给你一个运行时间的界限。

递推关系：T(n) = n*T(n/2)

Recurrence relation: T(n) = n*T(n/2)

recursion

recurrence

data-structures