How to analyze the time and space complexity of a recursion function?
如何分析一个递归函数的时间/空间复杂度?
We can answer that using master theorem or induction in most of the cases.
在大部分时候我们可以使用主方法和数学归纳法来进行解答。
First of all, we need to write down the recursion relation of a function.
首先我们要写出一个函数的递归表达式。
1 2 3 |
def func(n): if n < 0: return 1 return func(n/2) + func(n/2) |
Let’s use T(n) to denote the running time of func with input size of n.
让我们用T(n)来表示func函数在输入规模为n的运行时间。
Then we have:
那么我们有:
T(n) = 2*T(n/2) + O(1)
a = 2, b = 2, c_crit = logb(a) = 1, f(n) = n^c, c = 0.
c < c_crit, apply master theorem case 1:
根据主方法第一条我们得到
T(n) = Θ(n^c_crit) = Θ(n)
Let’s look at another example:
1 2 3 4 5 6 |
def func(n): if n < 0: return 1 s = 0 for i in range(n): s += i return s + func(n/2) + func(n/2) |
T(n) = 2*T(n/2) + O(n)
a = 2, b = 2, c_crit = logb(a) = 1, f(n) = n^c, c = 1,
c = c_crit, apply master theorem case 2:
根据主方法第二条我们得到
T(n) =Θ(n^c_crit * (logn)^1)) = Θ(nlogn)
Cheatsheet
Equation | Time | Space | Examples |
---|---|---|---|
T(n) = 2*T(n/2) + O(n) | O(nlogn) | O(logn) | quick_sort |
T(n) = 2*T(n/2) + O(n) | O(nlogn) | O(n + logn) | merge_sort |
T(n) = T(n/2) + O(1) | O(logn) | O(logn) | Binary search |
T(n) = 2*T(n/2) + O(1) | O(n) | O(logn) | Binary tree traversal |
T(n) = T(n-1) + O(1) | O(n) | O(n) | Binary tree traversal |
T(n) = T(n-1) + O(n) | O(n^2) | O(n) | quick_sort(worst case) |
T(n) = n * T(n-1) | O(n!) | O(n) | permutation |
T(n) = T(n-1)+T(n-2)+…+T(1) | O(2^n) | O(n) | combination |
For recursion with memorization:
Time complexity: |# of subproblems| * |exclusive running time of a subproblem|
Space complexity:|# of subproblems| + |max recursion depth| * |space complexity of a subproblem|
Example 1:
1 2 3 4 5 |
def fib(n): if n < 1: return 1 if m[n]: return m[n] m[n] = fib(n - 1) + fib(n - 2) return m[n] |
To solve fib(n), there are n subproblems fib(0), fib(1), …, fib(n)
each sub problem takes O(1) to solve
Time complexity: O(n)
Space complexity: O(n) + O(n) * O(1) = O(n)
Example 2:
1 2 3 4 5 6 7 8 9 |
dp(x1, y1, x2): if min(x1, y1, x2) < 0: return 0 if m[x1][y1][x2]: return m[x1][y1][x2] ans = max(dp(x1 - 1, y1, x2 - 1), dp(x1, y1 - 1, x2), dp(x1, y1 - 1, x2 - 1), dp(x1 - 1, y1, x2)) m[x1][y1][x2] = ans return m[x1][y1][x2] |
To solve dp(n, n, n), there are n^3 subproblems
each subproblem takes O(1) to solve
Max recursion depth O(n)
Time complexity: O(n^3) * O(1) = O(n^3)
Space complexity: O(n^3) + O(n) * O(1) = O(n^3)
Example 3:
1 2 3 4 5 6 |
dp(i, j): if m[i][j]: return m[i][j] for k in range(i, j + 1): ans = max(ans, dp(i, k - 1) + C + dp(k + 1, j)) m[i][j] = ans return m[i][j] |
To solve dp(0, n), there are n^2 subproblems dp(0, 0), dp(0, 1), …, dp(n-1, n)
each subproblem takes O(n) to solve
Max recursion depth O(n)
Time complexity: O(n^2) * O(n) = O(n^3)
Space complexity: O(n^2) + O(n) * O(1) = O(n^2)
Slides:
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment