主定理应用正确性验证及Sum函数Θ记号推导咨询

代码回顾 #

def Sum(A, left, right):
    if left > right:
        return 0
    elif left == right:
        return A[left]
    mid = floor(N/2)  # 注：原代码此处存在变量逻辑错误，正确应为floor((left+right)/2)，但不影响时间复杂度分析
    lsum = Sum(A, left, mid)
    rsum = Sum(A, mid+1, right)
    return lsum + rsum

def createB(A, N):
    B = [0] * 1
    B[0] = Sum(A, 0, N-1)
    return B

主定理应用正确性验证 #

你的递推式推导完全正确：

• 每次递归将问题拆分为a=2个子问题，每个子问题规模为原问题的1/2（即b=2）
• 递归过程中的额外操作（边界判断、mid计算、求和返回）均为常数时间，即f(N)=O(1)，对应d=0

主定理第一种情况：当d < log_b a时，T(N)=Θ(N^{log_b a})。此处log_2 2=1，0 < 1，因此T(N)=Θ(N)的结论是正确的。

最坏/最好情况的一致性 #

Sum函数的递归逻辑不存在输入依赖的分支差异：

• 无论数组元素是什么，递归都会将问题均匀拆分，直到子数组长度为1，所有递归路径的执行步骤数完全一致
• 边界情况（如N=1）的Θ(1)是特例，但对于任意N≥2，不存在因输入不同导致的时间波动

因此，Sum函数的最坏情况和最好情况时间复杂度均为Θ(N)。

内容的提问来源于stack exchange，提问作者NoobC_101