algorithm - 与主定理相关的递归 T(n)=T(n^(1/2))+1

Question

在大师定理中，给出了一个“插件”公式来找到大 O，因为它满足某些条件。

但是，如果我们遇到如下问题怎么办？谁能告诉我如何一步一步地做公式。哪些主题可以帮助我更多地了解这些类型的问题。假设问这个问题的人对归纳一无所知。

T(n)=T(n^(1/2))+1
T(n)=T(n-1) + 1
T(n)=T(n-1) + n^c , c is a natural number >1
T(n)= T(n-1) C^n, c is a natural number >1

Answer 1

您可以扩展公式并对其进行处理：例如：

T(n) = T(n-1) + 1
T(n) = [T(n-2) + 1] + 1
...
T(n) = 1 + 1 + 1 ... (n times)

所以T(n) = O(n)。

Answer 2

您需要了解一些数学知识才能完成其中的一些操作。当您将递归一直扩展到基本情况时，您可以弄清楚递归是什么样子，例如对于 T(n) = T(n-1) + n^c 你得到 T(n) = 1^c + 2^c + ... + n^c，但是你需要知道一些数学才能知道这是 O(n^(c+1))。（看到这一点的最简单方法是根据 x^c 的积分限制上下总和）。同样对于 T(n) = T(n-1) + c^n 你很容易得到 T(n) = c^1 + c^2 + ... + c^n 但你再次需要使用一些微积分或其他东西弄清楚这是 T(n) = O(c^n)。

对于 T(n) = T(n^(1/2)) + 1，您需要计算在达到基本情况之前应用递归的次数。数学再次在这里有所帮助。当你取平方根时，对数会减半。因此，您想知道在达到基本情况之前，您可以将对数减半多少次。这是 O(log log n)。