O（3^n）指数时间复杂度

-7

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） - 指数时间复杂度？O（3^n）指数时间复杂度

来源

2013-06-23 benjamin tan

简答题，没有。计算'3^n'不需要'O（3^n）'。 –

没有冒犯，但不是一个一个地发布你的作业阅读并尝试自己的...你连续发布几乎相同的3个问题 – stinepike

'for（int i = 0; i mah

没有计算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++)

来源

2013-06-23 12:14:43

public void run（int n） { （long i = 1; i <= power（3，n）; i ++）System.out。的println（ⅰ）; } } public int power（int c，int n） { int result = 1; for（int i = 0; i

任何运行3^n次迭代的算法都会产生相同的复杂度。因此，这个公共无效运行（int n）{for（long i = 1; i <= power（3，n）; i ++）{System.out.println（i）; }}，生成O（3^n）。但是这个public int power（int c，int n）{int result = 1; for（int i = 0; i

@benjamintan - 不...因为你的'power（c，n）'不计算'c^n'。 –

这段代码给我一个O（C 1-6 K） - 指数时间复杂性？

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

另外要注意的是，power(c, n)是计算ñ^Ç不是C ^ñ。

来源

2013-06-23 12:16:15

说实话，如果你觉得自己教出你的课程，他们的问题陈述可能不是他们打算什么球员，我只想做这种方式：

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

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

在另一方面：

Ç^ķ和3 ^ñ是不一样的东西。假设您输入的长度为n，则c ^k是恒定时间，而3 ⁿ是指数时间。假设输入的长度为c，则c ^k是多项式，而3 ⁿ是恒定的。假设你输入的长度是k，c ^k是指数，而3 ⁿ是恒定的。

来源

2013-06-23 13:56:08

O（3^n）指数时间复杂度

回答

相关问题