时间复杂度 - 大 O 符号

Question

def my_sum(i, j):
    if i == j:
        return i
    mid = (i + j) //2
    return my_sum(i, mid) + my_sum(mid + 1, j)

为什么是 O(j - i) 而不是 O(log n)？ (j >= i)

Answer 1

对于每个递归调用，该算法将 j-i 分成两半。递归深度将是获得 i == j 所需的递归调用数，每个分支将是 log2(j-i)。

因此该算法形成了一个递归树，其分支因子b 为2，深度d 为log2(j-i)。时间复杂度是树中的项数：

  b^d
= 2^log2(j-i)
= j-i