时间戳

首页 > 解决方案 > 具有分治法的数组和的复杂性

algorithm - 具有分治法的数组和的复杂性

问题描述

设以下算法为：

sum(v, i, j) {
    if i == j
        return v[i]
    else {
        k = (i + j) / 2
        return sum(v, i, k) + sum(v, k+1, j)
    }
}

该算法的时间复杂度为O(n)，但我如何（用自然语言）证明它的复杂度？问题总是被分成两个新的问题，这样就可以O(log n)了，但是其余的复杂性从何而来？

应用主定理产生预期的结果，O(n)。

谢谢。

标签： algorithmtime-complexity

解决方案

从高层次的角度来看，您的算法就像在遍历平衡二叉树一样，其中每个节点都覆盖一个特定的区间[i, j]。他们的孩子将区间分成 2 个大致相等的部分，即[i, (i+j)/2]和[(i+j)/2 + 1, j]。

让我们假设它们在这种情况下是相等的。（换句话说，为了证明，数组的长度n是2的幂）

请按照以下方式思考。n您的算法正在遍历这个平衡二叉树的叶子。每个都从长度为 1 的区间负责。n/2树的节点是这 n 个叶子的父节点。这些n/2节点有n/4父节点。这一直持续到你到达树的根节点，它覆盖了整个间隔。

想想这棵树中有多少个节点。n + (n/2) + (n/4) + (n/8) + ... + 2 + 1. 由于我们最初假设n = 2^k，我们可以将这个总和表示为指数的总和，求和公式是众所周知的。事实证明，2^(k+1) - 1 = 2 * (2^k) - 1 = 2n - 1那棵树中有节点。因此，显然遍历该树的所有节点需要O(n)时间。

推荐阅读