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

Question

我只是在尝试掌握 Master Theorem，当我尝试评估 T(n) = T(n/2) + n 时有点困惑。使用主定理，答案计算为 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)