涉及平方根的递归函数的运行时?

这里的其他答案给出了这个问题的代数直觉和解决方案。这是从递归树的角度来看这一点的另一种方法。

当你有一个递归关系时,画一张递归树的图来看看它是什么样子通常很有用。在这里,递归树如下所示:

                        +-------+
                        |   n   |
                        +-------+
         /       /          |          \           \
     +-------+ +-------+ +-------+           +-------+
     |n^(1/2)| |n^(1/2)| |n^(1/2)|    ...    |n^(1/2)| 
     +-------+ +-------+ +-------+           +-------+
       ...        ...       |                   ...
         /       /          |          \           \
     +-------+ +-------+ +-------+           +-------+
     |n^(1/4)| |n^(1/4)| |n^(1/4)|    ...    |n^(1/4)| 
     +-------+ +-------+ +-------+           +-------+

让我们想想这棵树。顶层由一个执行O(n)工作的调用组成。在下一个层面上√n个递归调用,每个调用√n工作。这是O(n)个总功的总和。在低于该级别时,每个√n递归调用将进行 ^4. √n递归调用大小问题 ^{4. 4.} √n重复呼叫正在进行 ^4. √n每个工作。那是√n组递归调用√n相互做功-另一个O(n)总功。

更一般地说,当你沿着递归树走下去时,你会发现每个级别都是O(n)工作的。这意味着递归调用完成的总工作量将等于树中的层数的O(n)倍。现在我们只需要弄清楚。

事实证明 the number of times you can take the square root of a number before it drops down to a constant is O(log log n) . (链接的答案已经解决了背后的数学问题)。这意味着我们期望完成的总功为O(n log log n)-树中有O(log log n)层,每个层都做O(n)功。

其他答案包含的数学形式化了这个推理,但我认为这样看可能会有帮助,这样你就可以看到答案的来源。