3

我正在尝试学习 Big-O 表示法，但在计算递归函数的时间复杂度时遇到了困难。

您能帮我理解以下示例的时间复杂度吗？

public int recursiveFunction(int n) {
    if (n == 0) {
        return 0;
    }

    return Math.max(recursiveFunction(rand(n)) + 2,recursiveFunction(n - 1));
}

public int rand(int n) {
    return new Random().nextInt(n - 1);
}

谢谢。

4

4 回答 4

5

时间将取决于rand(n)返回的内容，但如果您采取最坏的情况，这将是n-2. 所以代码简化为：

public int recursiveFunction(int n) {
    if (n == 0) {
        return 0;
    }

    return Math.max(recursiveFunction(n - 2) + 2,recursiveFunction(n - 1));
}

它的渐近上界等于：

public int recursiveFunction(int n) {
    if (n == 0) {
        return 0;
    }

    recursiveFunction(n-1);
    recursiveFunction(n-1);

    return 0;
}

这是一个深度为n且分支因子为 的递归2，因此 O(2^n) 时间复杂度。

于 2013-01-02T14:18:11.010 回答
3

递归函数不是开始学习复杂性的好地方。即使是相对简单的递归函数也可能需要相当复杂的计算来确定复杂性。

For recursiveFunction(n), you call recursiveFunction(n-1)and recursiveFunction(a)where a < n-1，所以最坏的情况是recursiveFunction(n-1)一次recursiveFunction(n-2)又一次。这与斐波那契数列具有相同的复杂性，它的复杂性是 O(2^n)。您会注意到链接中的算法看起来与您的非常相似。

于 2013-01-02T14:14:53.890 回答
0

您不了解代码的问题。因为您的代码会创建随机值，所以无法确定其运行时复杂度。由于您的“+2”和“-1”，程序也有可能永远不会结束。然而，这不太可能但可能，因此只能说它是 O(infinite)。

bigO 表示法的常见情况：

你只有一个循环：

for(int k=0;k<n;++k) {}

这是 O(n)，因为你有 n 次迭代

依次循环两个或多个循环：

for(int k=0;k<n;++k) {}
for(int l=0;l<n;++l) {}

来到 O(2*n)，但常数在 bigO 上无关紧要，所以它是 O(n)

纠缠循环：

for(int k=0;k<n;++k) {
    for(int l=0;l<n;++l) {
    }
}

是 O(n²),

for(int k=0;k<n;++k) {
    for(int l=0;l<n;++l) {
        for(int m=0;m<n;++m) {
        }
    }
}

是 O(n³) 等等

对于搜索/比较算法，您将遇到的最常见的复杂性是

for(int k=0;k<n;++k) {
    for(int l=k;l<n;++l) {// note here: l=k instead of l=0
    }
}

是 O(n*log(n))

有关更多详细信息，请使用谷歌。

于 2013-01-02T14:20:48.440 回答
0

你在这里选择了一个相当棘手的问题。Math.Max 的计算并不重要，重要的是两个递归调用。

当 n == 1 时出现问题，因为您调用 rand (1)，它调用未定义的 Random().nextInt (0) - 它应该返回 >= 0 且 < 0 的随机整数不可能。让我们希望它返回 0 - 如果不是，我们就有麻烦了。

recursiveFunction (n) 调用 recursiveFunction (n - 1)，并使用随机 i 再次调用 recursiveFunction (i)，0 <= i <= n - 2。让我们制作一个最大调用次数表，计数1 用于初始调用（假设 rand (1) 返回 0，并且每隔一个调用返回 n - 2）：

n = 0: 1 calls
n = 1: 1 + 1 + 1 = 3 calls
n = 2: 1 + 1 + 3 = 5 calls
n = 3: 1 + 3 + 5 = 9 calls
n = 4: 1 + 5 + 9 = 15 calls
n = 5: 1 + 9 + 15 = 25 calls
n = 6: 1 + 15 + 25 = 41 calls
n = 7: 1 + 25 + 41 = 67 calls
n = 8: 1 + 41 + 67 = 109 calls
n = 9: 1 + 67 + 109 = 177 calls
n = 10: 1 + 109 + 177 = 287 calls

调用的数量增长很快，但不如 2^n 快。我会说它是 O (c^n)，c = sqrt (1.25) + 0.5。这是最坏的情况；平均要少很多。

于 2014-03-23T09:10:39.243 回答