下面的遞回函式的時間復雜度是多少？
我正在使用下面的 T(n) 但不確定我是否為此函式創建了正確的方程式
T(n)=T(n-1) n -> o(n^2)
public static int test2(int n){
if(n<=0){
return 0;
}
for(int i =0; i<=n; i ){
for(int j =0; j<=n; j ){
System.out.println(" in here " i j);
}
test2(n-1);
}
return 1;
}
uj5u.com熱心網友回復：
我認為函式是：T(n)=n(T(n-1)) n^2
uj5u.com熱心網友回復：
我將從數學的角度來解決這個問題。
首先，你的 T(n) 等式不正確，它應該是：
T(n) = n * (T (n-1) n)
原因是您有 n 次迭代，并且對于每次迭代（這就是產品的來源），您在進行 n 次迭代時進行遞回。所以基本上你會有：
T(n) = n * T(n-1) n^2
T(n-1) = (n-1) * T(n-2) (n-1)^2
T(n-2) = (n-2) * T(n-3) (n-2)^2
.
.
.
T(2) = 2 * T(1) 2^2
T(1) = 1 * T(0) 1^2
其中 T(0) = 1 基本上給出了您的定義。所以現在通過一些重新排序和乘法你將擁有：
T (n) = n^2 n*((n-1)^2) n*(n-1)*((n-2)^2) ... n*(n-1)*(n-2)*(n-3)*...*(n-(n-3))*(2^2) (2 * n!)
最后2 * n的原因！是 T(1) = 2 并通過乘法得到系數 n!。（對這個程序基本上從 T(n-1) 開始，然后將方程與 n 相乘并將其添加到 T(n) 的方程中，你就得到了 T(n-1)。但是你現在有 T( n-2)在T(n)的等式中所以重復這個程序)所以我認為（但不確定）時間復雜度將是n！而不是 n^2。我希望這是有幫助的。
uj5u.com熱心網友回復：
O(n^2)是單個非終止遞回呼叫的時間復雜度，但不是整體時間復雜度。
每次呼叫test(n)，如果它沒有達到遞回的基本情況，就會創建n 1遞回呼叫的分支。
例如，如果n = 2。遞回呼叫樹將是：
t(2)
/ | \
/ | \
t(1) t(1) t(1)
/ \ / \ / \
t(0) t(0) t(0) t(0) t(0) t(0)
所以呼叫test(2)導致9遞回呼叫。如果我們呼叫test(3)它會產生40遞回呼叫。
基本上我們有：
(n) * (n 1 - 1) * (n 1 - 2) * (n 1 - 3) * ... until `n` doesn't turn to 1
這類似于階乘，如果我們忽略 1它，它將大致是n!遞回呼叫。每個都有時間復雜度O(n^2)
所以整體的時間復雜度可以表示為：
O(n^2 * n!)
uj5u.com熱心網友回復：
這是一個相當復雜的功能。讓我們從下往上移動，也許我們可以看到一些東西。
T(0) = 1
T(1) = 2 * (2 T(0)) = 2 * (2 1) = 2 * 3 = 6
T(2) = 3 * (3 T(1)) = 3 * (3 6) = 2 * 9 = 27
T(3) = 4 * (4 T(2)) = 4 * (4 27) = 4 * 31 = 124
如果我們以不同的方式擴展它
T(1) = 2 * (2 T(0))
T(2) = 3 * (3 2 * (2 T(0)))
T(3) = 4 * (4 T(2)) = 4 * (4 3 * (3 2 * (2 T(0))))
...
T(n) = (n 1) * (n 1 T(n)) = (n 1) * (n 1 n * (n T(n -1))) =
(n 1) * (n 1 n * (n (n-1) * ((n-1) T(n-2))))
現在如果我們打開 T(n) 的括號
T(n) = (n 1)^2 (n 1)n*(n T(n-1)) = (n 1)^2 (n 1)n^2 (n 1)n(n-1)*((n-1) T(n-1)) = ...
= (n 1)^2 (n 1)n^2 ... (n 1)n(n-1)...2^2 (n 1)! = Sum[iProduct[j,{j,i,n}],{i,2,n}] (n 1)!
（我使用 wolfram alpha 作為總和，我希望它是正確的）
從最后的總和我們可以看出，總和中最大的成員是(n 1)!其他的都會變小，所以我們可以忽略那些。這 1也是毫無意義的，所以我們也可以放棄它。最終結果是你的遞回函式是o(n!).
如果有人問為什么，那是因為沒有n 1回圈條件。另外，我已經好幾年沒有做過這種型別的分析了，我希望我沒有犯任何重大錯誤。i<=ni < n
uj5u.com熱心網友回復：
按時間替換操作，您可以建立以下回圈：
T(0) = C0
T(n) =
Σ{i=0..n}
Σ{j=0..n}
C1
T(n-1)
C2
這可以重寫
T(n) = (n 1).((n 1).C1 T(n-1)) C2 = (n 1).T(n-1) (n 1)2.C1 C2
這個遞回的精確解有點技術含量。通過求解齊次方程，我們得到了解，C.(n 1)!并且通過我們設定的系數的變化
T(n) = (n 1)!.U(n)
然后
(n 1)!.U(n) = (n 1).n!.U(n-1) C1.(n 1)2 C2
或者
U(n) = U(n-1) C1/(n-2)! 2C1/(n-1)! C2/(n 1)!
我們認識到 e 的截斷級數，它很快收斂到一個常數并且
T(n) ~ C(n 1)! = O((n 1)!)
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/537818.html
標籤：爪哇算法递归大O