c++ - 递归公式

Question

首先，是的，它是 HW - 确实尝试过，但不确定是否有什么，如果你能帮助我，我会很高兴:)

我有这个代码:

void func(int A[], int start, int n)
{
    int p = n/2;
    if ( 1 < n )
    {
        func(A, start, p);
        func(A, start + p, n-p);
        for (i=0; i<n; i++)
            cout << A[start+i];
    }
}

func(A, 0, n);

我需要给这段代码一个递归公式。我所做的是 - 第一个递归调用是 T(n/2)。 第二——这就是问题所在!真的与添加'p'混淆......是那个 T(n/2) 也是？？ 三 - 因为在 theta(n) 上运行 并且外部递归调用是 T(n)...

你能帮我得到最终的公式吗？？

谢谢

Answer 1

如果我没看错，你想要运行时复杂度的重复。

对于 n > 1，您重复使用参数 floor(n/2) 和参数 n-floor(n/2) ，然后输出 n 项。因此你有

T(n) = T(cost of first recursive call) + T(second rec. call) + extra work

您现在应该将其转化为适合应用主定理的形式。