O(3^n) 指数时间复杂度

Question

 public void run(int n)
    {
        System.out.println(power(3, n));
    }
public int power(int c, int n)
{
    int result = 1;
    for (int i = 0; i < c; i++) {
        result *= n;
    }
    return result;
}

这段代码是否给了我一个 O(c^k( - 指数时间复杂度？

Answer 1

老实说，如果你想向教授你的课程的人展示他们的问题陈述可能不是他们想要的，我会这样做：

for(int i = 0; i < c; i++) { /*your code here*/}

这是在 O(c( 中，并且由于 O(c( 是 k> 1 的 O(c k( 的严格子集，因此它也在 O(c^k( 中。这可能不是教授您的课程的人的意图，他们可能希望您编写一个以 Θ(c^k 为单位(运行的循环。

---

另一方面：

c^k 和 3ⁿ 不是一回事。假设输入的长度为 n，c^k 是常量时间，而 3ⁿ 是指数时间。假设输入的长度为 c，c^k 是多项式，而 3ⁿ 是常数。假设输入的长度为 k，c^k 是指数，而 3ⁿ 是常数。

Answer 2

没有计算 3 的幂 n 不是复杂度 O(3^n(。您的算法复杂性仅为 O(c(，因为它仅迭代 c 次。要编写 O(3^n( 算法，一种方法是运行 for 循环 3^n 次。此类 for 循环的一个例子是：

for(long i = 0; i < Math.power(3, n); i++)

Answer 3

这段代码是否给了我一个 O(c^k( - 指数时间复杂度？

不。 power(c, N)执行循环的c乘法/迭代，因此它是O(C(。 这意味着(因为c是run(n)中的常数(，test(n)实际上是O(1)的。

需要注意的另一件事是，power(c, n)计算的是 n c 而不是^cn。