math - 如何计算递归给出的函数的确切最坏情况运行时间？

Question

我正在尝试计算一个函数在最坏情况下的运行时间值，该函数的最坏情况运行时间由这种重复给出：

T(0) = 0

T(n) = n + T(n - 1)（如果 n > 0）

有没有人有任何建议如何做到这一点？我不知道如何解决这个问题。

Answer 1

尝试扩展重复以查看是否发现模式可能会有所帮助：

• T(0) = 0
• T(1) = 1 + T(0) = 1 + 0
• T(2) = 2 + T(1) = 2 + 1 + 0
• T(3) = 3 + T(2) = 3 + 2 + 1 + 0

基于这种模式，它看起来像 T(n) = 0 + 1 + 2 + ... + n。这是 Gauss 得出的一个著名的求和，它求解为 n(n+1)/2。因此，我们可以推测 T(n) = n(n+1)/2。

你可以通过归纳证明这一点。作为基本情况，T(0) = 0 = 0(0+1)/2，所以一切都检查出来了。对于归纳步​​骤，假设 T(n) = n(n+1)/2。那么 T(n+1) = (n+1) + T(n) = (n+1) + n(n+1)/2 = (n+1) (1 + n / 2) = (n+ 1)(n+2)/2 = ((n+1))((n+1) + 1) / 2，这也检查出来了。

因此，您的确切值是 T(n) = n(n+1)/2。

希望这可以帮助！