求解递归 T(n) = T(6n/5) + 1
Solve recurrence T(n) = T(6n/5) + 1
所以我正在准备算法考试，我不知道如何解决这个重复问题T(n) = T(6n/5) + 1，因为b = 5/6 < 1 和Master theorem 不能应用。
我希望有人可以给我提示如何解决这个问题。 :)
仅给出该递归关系（并且没有其他信息，例如 T(x) = 1 当 x > 100 时），具有该关系所描述的时间复杂度的算法将永远不会终止，因为工作量会增加每次通话。
T(n) = T(6n/5) + 1
= T(36n/25) + 2
= T(216n/125) + 3
= ...
您可以看到每次调用都会增加工作量，而且增加的量没有限制。因此，函数的时间复杂度没有限制。
我们甚至可以（非正式地）争辩说这样的算法不存在 - 每次调用将输入的大小增加 1.2 倍至少需要 0.2n 的工作，这显然是 O(n) - 但据称每一步的实际成本为 1、O(1)，因此对于以下描述的算法来说是不可能的
这种精确的循环存在（但对于具有循环的算法很好，例如 T(n) = T(6n/5) + n）。
所以我正在准备算法考试，我不知道如何解决这个重复问题T(n) = T(6n/5) + 1，因为b = 5/6 < 1 和Master theorem 不能应用。
我希望有人可以给我提示如何解决这个问题。 :)
仅给出该递归关系（并且没有其他信息，例如 T(x) = 1 当 x > 100 时），具有该关系所描述的时间复杂度的算法将永远不会终止，因为工作量会增加每次通话。
T(n) = T(6n/5) + 1
= T(36n/25) + 2
= T(216n/125) + 3
= ...
您可以看到每次调用都会增加工作量，而且增加的量没有限制。因此，函数的时间复杂度没有限制。
我们甚至可以（非正式地）争辩说这样的算法不存在 - 每次调用将输入的大小增加 1.2 倍至少需要 0.2n 的工作，这显然是 O(n) - 但据称每一步的实际成本为 1、O(1)，因此对于以下描述的算法来说是不可能的
这种精确的循环存在（但对于具有循环的算法很好，例如 T(n) = T(6n/5) + n）。