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

你能解释一下如何找到下面代码的时间复杂度吗？任何帮助赞赏。如何找到下面代码的时间复杂度？

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

2016-11-29 Yazgan

这可以帮助你http://stackoverflow.com/questions/13467674/determining-complexity-for-recursive-functions-big-o-notation –

@DanielCorzo谢谢丹尼尔，我已经看到了这一点。这里的情况有点不同。 – Yazgan

有时候这是好事，把它写下来。当你开始时，它总结1 + boo（n/2）+ boo（n/2），它在第二行。

并且每个是n/2也被运行

等等，等等

所以在最后的同时呼叫的数量被exponencially生长，repetions的数量仅为logharitmic，其在最后移除对方，你得到了O（N）。 PS：对最后一行进行倒数就足够了，整个树总是只有一次更多的节点（减1），这在复杂性理论中是可以忽略的（你不关心常量，它乘以2）

2016-11-29 16:37:14 libik

非常感谢很多朋友（： – Yazgan

这个确切的问题来考试LOL再次感谢@libik – Yazgan

@Yazgan - 哇，我希望我是正确的：D ... – libik

回答