-3

我正在为考试而学习，我遇到了这个问题，我对这门课程不太擅长，我完全被它难住了。我真的很感激一些帮助！

假设您可以访问在时间 O(n) 中运行的算法 isprime(n)（例如，蛮力检查所有小于 n 的数的可分性）。以下代码计算小于或等于其输入参数的素数。

boolean numprimes(int n) {
    if (n == 1) {
        return 0;
    } else if (isprime(n)) {
        return numprimes(n − 1) + 1;
    } else {
        return numprimes(n − 1);
    }
}

目标是分析 num primes 的运行时间。通过执行以下操作来实现此目标：

(a) 写一个递归定义 T (n) 算法在大小为 n 的实例上的运行时间。

(b) 求解T(n) 的递归定义，通过重复代入、猜测、归纳证明猜测、最后根据你的猜测推导出封闭形式的方法得到一个封闭形式。或者，您可以使用重复替换来猜测封闭形式，并通过归纳证明您的封闭形式正确。

非常感谢，我将非常感谢任何帮助！

4

2 回答 2

1

a) 由于素数的测试是在 O(n) 时间内执行的，因此递归将是

T(n) = T(n-1) + O(n)

b) 解决了 a 部分，剩下的应该很容易了。如果您向我展示您为解决此问题所做的工作，我可以为您提供更多帮助。

于 2013-10-16T01:59:36.270 回答
1

作为提示，以下是重复出现的样子：

T(1) = 1

T(n) = T(n - 1) + O(n)

这是因为总是有一个递归调用（在 size 的输入上n - 1），并且每个单独的调用都做了 O(n) 的工作。

如果您将其重写为

T(1) ≤ 1

T(n) ≤ T(n - 1) + kn

您可以开始迭代。作为提示，最终结果应该是 O(n 2 ); 我会把细节留给你。

希望这可以帮助！

于 2013-10-16T01:59:36.777 回答