递归算法复杂度分析

Question

我正在尝试分析这个算法的复杂度，但我不确定它的递归方程是否为T(n / 2) + 2n，你能帮我吗？ v > 100

的大小

bool pareado(int v[], int left, int right) {
    bool b;
    if (left >= right)
        b = true;
    else {
        int m = (left + right) / 2;
        bool baux = (abs(contarPares(v, left, m) - contarPares(v, m + 1, right)) <= 1);
        if (baux == false)
            b = false;
        else
            b = pareado(v, left, m) && pareado(v, m + 1, right);
    }
    return b;
}

函数“contarPares”是这样的：

int contarPares(int v[], int i, int j) {
    int count = 0;
    for (int k = i; k <= j; k++) {
        if ((v[k] % 2) == 0)
            count++;
    }
    return count;
}

Answer 1

你的 pareado 函数的复杂度为 O(n) [ for n = right-left ] before recursing。鉴于在每个递归步骤中，您都对输入范围进行分区，并分别处理它们，因此在最坏的情况下，您仍然必须对整个范围进行一次迭代（对于任何迭代深度）。

有多少种递归深度？在最坏的情况下，你必须等到 contarPares returns 0 因为它没有剩余输入，即它的范围是空的。鉴于您总是输入范围的一半，这将需要 log(n) 次递归。

由于每个深度的成本为 O(n)，而您的深度为 O(log(n))，因此总共有 O(n*log(n)).

当然，根据您的输入数组，您可能会提前终止，但不会超过上面给出的限制。

递归算法复杂度分析

Recursive algorithm complexity analysis

c++

complexity-theory