if-else 循环的最坏情况运行时间

Question

问题是问g(n)的最坏情况时间复杂度，我很困惑为什么第二个方程是c1n，而不是c1n^2。

我认为最坏的情况应该有更大的复杂性吧？或者是因为 if-else 的第二个分支中的“b”是有界的，因此被视为常量？如果有，复发情况如何？递归是否也具有恒定的复杂性，因为在这种情况下 n 变为常数？

Answer 1

这里的技巧是几乎从未选择过 else 分支。

你可以计算出前几个值：

g(0) == 1
g(1) == 1

g(2) == 4
g(3) == 4

g(4) == 16
g(5) == 16
g(6) == 16

then for every n >= 4:
g(n) >= 16 > 5.

因此对于每个 n >= 12、g(n/3) > 5。

所以在任何一次执行中，else分支最多被选择两次，在最后两次递归调用中，n的值小于11。

为了完全迂腐，我认为答案应该是恒定成本 c0 适用于 n <= 11.

worst case runtime for if-else recurrence