生长决定的顺序

Question

我正在练习增长顺序，但我在确定以下函数的增长顺序时遇到了问题：

def ri(na):
    if na <= 1:
         return na
    def han(na):
         i = 1
         while i < na:
             i *= 2
         return i
    return ri(na/2) + ri(na/2) + han(na-2)

我相信函数han有一个增长的顺序$\Theta(n) = log(n)$，但我不确定在添加ri(na/2)时如何考虑这个问题。如果有人能帮我弄清楚如何计算运行时间，我将不胜感激。非常感谢！

Answer 1

han函数的时间复杂度为Theta(log(n)) (每次i乘以2)。因此，ri的时间复杂度是T(n) = 2T(n/2) + Theta(log(n))。使用the master theorem，我们可以说T(n) = Theta(n)。