在T(n)= T(n/2)+ n上应用主定理

Question

当我试图评估T(n)= T(n/2)+ n时,我只是尝试使用Master Theorem并且有点困惑.使用Master定理,答案评估为O(n).

但只需通过以下代码:

fun(n)
{
    if(n == 1)
        return ;
    for(int i=1;i<=n;i++)
    {
        printf("*");
    }
    fun(n/2);
}

上述代码的递归方程是T(n)= T(n/2)+ n.因此,上述程序的时间复杂度必须为O(n).

但是如果按逻辑思考,程序运行的次数是:n + n/2 + n/4 + n/8 + ...... = nlogn.因此,从逻辑上讲,上述程序的时间复杂度必须为O(nlogn).

我现在非常困惑.有人可以帮我解决我弄错的地方吗？

Answer 1

不,系列评估为2n.

n + n/2 + n/4 + n/8 + ...... = 2n

但如果你有T(n)= 2T(n/2)+ n,那么它将是O(n log n)