java - 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 NOT c ⁿ。