algorithm - 大 O 表示法 - 递归

Question

在网上找到这个算法，我不知道如何做数学来找到它的复杂性。我知道它的最坏情况是 2^n

// A simple recursive function to check whether C is an interleaving of A and B
bool isInterleaved(char *A, char *B, char *C)
{
    // Base Case: If all strings are empty
    if (!(*A || *B || *C))
        return true;

    // If C is empty and any of the two strings is not empty
    if (*C == '\0')
        return false;

    // If any of the above mentioned two possibilities is true,
    // then return true, otherwise false
    return ( (*C == *A) && isInterleaved(A+1, B, C+1))
           || ((*C == *B) && isInterleaved(A, B+1, C+1));
}

Answer 1

将复杂性视为数字的函数 n C 中的字符数.我们称之为f(n) .

第一个if block 无论如何都只是在做简单的检查，所以我们现在可以忽略它们(恒定的复杂性)。

算法的核心当然是这些行:

((*C == *A) && isInterleaved(A+1, B, C+1)) || ((*C == *B) && isInterleaved(A, B+1, C+1));

支票 (*C == ...)又是常数时间复杂度。现在，isInterleaved(..., ..., C+1)正在使用 C 调用算法缩短 1:因此它的复杂度是 f(n-1) .

然后我们可以把它们放在一起:

f(n) = k1 + (k2 + f(n-1)) + (k3 + f(n-1))

与 k1 , k2和 k3是一些常数。重新排序条款，我们得到: f(n) = 2 * f(n-1) + k

在哪里k又是一些常数。现在，展开递归，我们得到:

f(n) = 2 * (2 * ( 2 * (... f(0) + k0) + k1) + k2) + ... + k_n) = 2 * (2 * (2 * (... 2*(2*(f(0) + k0) + k1) + k2) + ... + k_n) = 2 * (2 * (2 * (... 2*(2^2*(f(0) + k0) + 2*k1) + k2) + ... + k_n) = 2 * (2 * (2 * (... 2*(2^3*(f(0) + k0) + 2^2*k1 + 2*k2) + ... + k_n) f(n) = 2^n * (f(0) + k0) + 2^(n-1) * k1 + 2^(n-2) * k2 + ... 将其全部除以 2^n ，我们得到:

f(n) / 2^n = (f(0) + k0) + k1 / 2 + k2 / 4 + ... + k_n / 2^n 所有这些项都是有界的:它是 2^{-n} 之和的属性。无论您求和多少项，它都会接近 2 而永远不会达到它。现在，因为你所有的k常量只是简单的检查，它们也是有界的。因此，我们知道存在一些常数K这样 k0 < K, k1 < K, ..., k_n < K .你的f(n)/2^n然后变成:

f(n) / 2^n < f(0) + K * (1 + 1/2 + 1/4 + ... + 1/2^n)

现在，前两项检查确保 f(0)也是常数，因此您已经证明该函数的复杂度除以 2^n 确实是有界的，这足以说明 f(n) is O(2^n) .

你可以略过其中的大部分“存在一个常量使得……”；要进行的主要观察是(使用“handwavily equivalent-ish”符号 ~ ):

f(n) ~ f(n-1) + f(n-1) f(n) ~ 2 * f(n-1) f(n) ~ O(2^n) 我也从假设 C 的长度开始稍微作弊。是计算复杂度的唯一重要参数，但是如何严格证明 A 的各种长度的复杂度是等效的？和 B留给读者作为练习!