如何找到以下代码的时间复杂度？

Question

您能解释一下如何计算以下代码的时间复杂度吗？任何帮助表示赞赏。

int boo(n) {
    if (n > 0)
    {
         return 1 + boo(n/2) + boo(n/2);
    }
    else 
    {
         return 0;
    }
}

Answer 1

有时候写下来也挺好的。当你开始时，它求和 1 + boo(n/2) + boo(n/2)，它在第二行。

每个n/2也是运行

等等等

所以最后，虽然调用次数呈指数增长，但重复次数仅为对数，最后相互删除，得到 O(N)。

PS ：倒数最后一行就够了，整棵树总是只有一次多节点（减一），这在复杂性理论中可以忽略不计（你不关心常量，它乘以二是)