How to analyze the time complexity of recursive function?
- use recursion relationship
- if it's a bit complex, then use this function: O(构造解的复杂度 * 解的个数)
- O(branches ^ depth)
| Recurrence Relation | Time Complexity |
|---|---|
| T(n) = T(n - 1) + a | O(n) |
| T(n) = T(n - 1) + O(n) | O(n^2) |
| T(n) = T(n / 2) + a | O(logn) |
| T(n) = T(n / 5) + a | O(logn) |
| T(n) = 2*T(n / 2) + a | O(n) |
| T(n) = 2*T(n / 2) + O(n) | O(n * logn) |
| T(n) = 2 * T(n - 1) + a | O(2^n) |
| T(n) = n * T(n - 1) | O(n * n!) |
| T(n) = T(n - 1) + T(n - 2) + T(n - 3) + ... + T(0) | O(2^n) |
| T(n) = T(n - 1) + T(n - 2) | O(2^n) |
http://www.1point3acres.com/bbs/thread-117602-1-1.html
https://users.cs.duke.edu/~ola/ap/recurrence.html
T(n) = 每层的个数*层数
Recurrence Relation Tutorial
http://www.radford.edu/~nokie/classes/360/recurrence.eqns.revised.html