pepper's questions

ALGO(A,s,d)
    m=d-s+1
    if m>=2 then
        q=⌊m/2⌋
        return 2ALGO(A, s, s+q-1) + 3ALGO(A, s+q, d);
    else
        return 1
    endif

我有这段代码，我必须找到 函数中的递归关系n。问题指出该算法最初用 调用ALGO(A, 1, n)。A 是一个大小为 的数组n，s并且d是整数，q是 的 floor 函数m/2。

我想到的解决方案是：

T(n) = 1 if n<2

T(n) = T(⌊n/2⌋) + T(⌈n/2⌉) + theta(1) if n>=2.

我的理由是if s=1，在第一个递归调用中，我有d=n，所以，对于第二个调用，所以，因为在 if 中我计算了哪些成本。我不知道我想出的解决方案是否正确m=n，也不知道如何解决它。对于解决方案，我不知道我是否可以说。q=⌊n/2⌋s=1d=⌊n/2⌋m=⌊n/2⌋s=s+q=1+⌊n/2⌋ d=nm=⌈n/2⌉T(⌊n/2⌋) + T(⌈n/2⌉) + theta(1)q1T(⌊n/2⌋) + T(⌈n/2⌉) = T(n)