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）指數時間複雜度

回答

相關問題