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.
首先我们要写出一个函数的递归表达式。
|
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:
|
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:
|
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:
LC 741 Cherry Pickup
|
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:
LC 312: Burst Balloon
|
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: