大 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 == '[=10=]')
        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

考虑以下情况。

A = "ab"
B = "aa"
C = "aa"

现在递归将执行如下，

fn(ab, aa, aa)
=> fn(b, aa, a) + fn(ab, a, a)
=> false + fn(b, a, null) + fn(b, null, a) + fn(ab, null, null)

函数调用次数为6次

现在，如果您在所有的开头添加一个 a，例如

A = "aab"
B = "aaa"
C = "aaa"

你会看到这次函数调用的次数是 14。

类似的加一个。那么它将是30.. 然后 62 然后... 你可以简单地看到它 2^n - 2。或者像这样。

所以这里的实际复杂度是 2^n 而不是 n^2。

发生这种情况是因为您在这里没有使用记忆。

Answer 2

看看是否可以通过将 return 分成更多行来减少问题，

// 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 == '[=10=]')
        return false;

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

"Factor out"B产生两种方法

bool isInterleavedA(char *A, char *C)
{
    // Base Case: If all strings are empty
    if (!(*A || *C))
        return true;

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

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

bool isInterleavedB(char *A, char *B, char *C)
{
    bool result = isInterleavedA(A, C);
    if (!(*B) && result)
        return true;
    return (*C == *B) && isInterleavedB(A, B+1, C+1);
}

现在我们可以看到 isInterleavedA 是 O(n) BigOh isInterleavedB 将与 isInterleaved 相同，这将是.. N + MN？

Answer 3

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

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

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

((*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).

您可以浏览其中的大部分内容 'there exists a constant such that...'；要进行的主要观察是（使用 '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 留作 reader !

的练习

大 O 表示法 - 递归

Big O notation - recursion

algorithm

complexity-theory