瞭解大哦

Question

我很難理解大哦。

我很確定下面的代碼是O（N）。

public static int two1 (int n) { 
    if (n == 0) { 
    return 1; 
    } else { 
    return 2 * two1(n - 1); 
    } 
} 

在第二個例子中，我完全迷失了。有人可以向我解釋這將是什麼符號嗎？

public static int two2 (int n) { 
    if (n == 0) { 
    return 1; 
    } else { 
    return two2(n - 1) + two2(n - 1); 
    } 
} 

Answer 1

當n = 0時，需要1步。 當n = 1時，需要1 + t（0）+ t（0）= 1 + 1 + 1 = 3步。 當n = 2時，需要1 + t（1）+ t（1）= 1 + 3 + 3 = 7步。 當n = 3時，需要1 + t（2）+ t（2）= 1 + 7 + 7 = 15步。 O（2^n）。這只是2^n - 1，所以O（2^n）。

Answer 2

O符號等於答案。 O(fib(n))您最終將1 + 1 + 1 + 1 + 1 + .... 1中的所有計算結果作爲答案，這也是順序。

fib（n）大約是golden ratio^n或(1+sqrt(5))/2^n。

Answer 3

它會是O（2^n）

想一想。第一個，接受輸入的n。假設你輸入了k。這將需要k個步驟。如果輸入2 + 1，則需要k + 1個步驟。如果您輸入2k，則需要兩倍的時間。

在第二個例子中，如果你輸入3例如，你將不得不計算two2（2）+ two2（1）。如果你輸入4，你將不得不完成所有的2（2）和2（2）的所有工作。

爲了更好地說明，請考慮two2（100）。這將需要two2（99）+ two2（98）。雙方的規模相似。如果你必須做兩個（101），你將不得不做大約兩倍的工作。

這有幫助嗎？

另請參閱：Computational complexity of Fibonacci Sequence