我正在看這個問題：
令 T(n) 為以下函式的最大堆疊深度，以 n 為單位。
double foo (int n) { int i; double sum; if (n == 0) return 1.0; else { sum = 0.0; for (i = 0; i < n; i ) sum = foo (i); return sum; } }找到 T(n) = O(?)
提供的答案是 O(n)，但我計算為 O(n!)。我不確定如何為此設計解決方案。
uj5u.com熱心網友回復：
堆疊深度可以表示為從某個點的單個遞回向下遞回呼叫的最大數量。foo(n)呼叫foo(0), foo(1), foo(2),..., foo(n - 1). 如果您跟蹤來自 的遞回呼叫foo(n-1)，您將看到它呼叫foo(n - 2)。在被呼叫之前它是這樣f(0)的。因此最大堆疊深度為O(n)。不是O(n!)。
時間復雜度如何？
T(n) = T(n-1) T(n-2) ... T(1) T(0)
T(1) calls T(0) 1 times. (2^0)
T(2) calls T(0) 2 times. (2^1)
T(3) calls T(0) 4 times. (from T(2) T(1) T(0))
T(4) calls T(0) 8 times.
T(5) calls T(0) 16 times. (2^4)
...
T(n-1) calls T(0) 2^(n-2) times.
In total T(0) is called [1 2 4 8 ... 2^(n-2)] 1 times.
等于2^(n-2) 2^(n-2)，可以表示為2^n / 2。因此它具有指數時間復雜度，即O(2^n)。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/435773.html
上一篇：使用后洗掉串列元素