Press "Enter" to skip to content

Huahua's Tech Road

花花酱 Time/Space Complexity of Recursion Functions SP4

 

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.

首先我们要写出一个函数的递归表达式。

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:

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:

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

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

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:

 

花花酱 LeetCode 773. Sliding Puzzle

题目大意:给你一个2×3的棋盘,放着0-5。每一步0可以和上下左右的一个数交换。问需要多少步可以构成123450的棋盘状态。

Problem:

On a 2×3 board, there are 5 tiles represented by the integers 1 through 5, and an empty square represented by 0.

A move consists of choosing 0 and a 4-directionally adjacent number and swapping it.

The state of the board is solved if and only if the board is [[1,2,3],[4,5,0]].

Given a puzzle board, return the least number of moves required so that the state of the board is solved. If it is impossible for the state of the board to be solved, return -1.

Examples:

Solution: BFS

Time complexity: O(6!)

Space complexity: O(6!)

C++

Simplified, only works on 3×2 board

 

 

花花酱 LeetCode 636. Exclusive Time of Functions

题目大意:给你一些函数的起始/终止时间的日志,让你输出每个函数的总运行时间。假设单核单线程,支持递归函数。

Given the running logs of n functions that are executed in a nonpreemptive single threaded CPU, find the exclusive time of these functions.

Each function has a unique id, start from 0 to n-1. A function may be called recursively or by another function.

A log is a string has this format : function_id:start_or_end:timestamp. For example, "0:start:0" means function 0 starts from the very beginning of time 0. "0:end:0" means function 0 ends to the very end of time 0.

Exclusive time of a function is defined as the time spent within this function, the time spent by calling other functions should not be considered as this function’s exclusive time. You should return the exclusive time of each function sorted by their function id.

Example 1:

Note:

  1. Input logs will be sorted by timestamp, NOT log id.
  2. Your output should be sorted by function id, which means the 0th element of your output corresponds to the exclusive time of function 0.
  3. Two functions won’t start or end at the same time.
  4. Functions could be called recursively, and will always end.
  5. 1 <= n <= 100

Solution: Simulate using stack

 

花花酱 LeetCode 464. Can I Win

题目大意:两个人从1到M中每次取出一个数加到当前的总和上,第一个达到或超过T的人获胜。问你第一个玩家能不能获胜。

In the “100 game,” two players take turns adding, to a running total, any integer from 1..10. The player who first causes the running total to reach or exceed 100 wins.

What if we change the game so that players cannot re-use integers?

For example, two players might take turns drawing from a common pool of numbers of 1..15 without replacement until they reach a total >= 100.

Given an integer maxChoosableInteger and another integer desiredTotal, determine if the first player to move can force a win, assuming both players play optimally.

You can always assume that maxChoosableInteger will not be larger than 20 and desiredTotal will not be larger than 300.

Example

 

 

Solution: Recursion with memoization 

Time complexity: O(2^M)

Space complexity: O(2^M)

C++

Java

Python3

 

花花酱 LeetCode 768. Max Chunks To Make Sorted II

题目大意:给你一堆数让你分块,每块独立排序后和整个数组排序的结果相同,问你最多能分为几块。

Problem:

This question is the same as “Max Chunks to Make Sorted” except the integers of the given array are not necessarily distinct, the input array could be up to length 2000, and the elements could be up to 10**8.


Given an array arr of integers (not necessarily distinct), we split the array into some number of “chunks” (partitions), and individually sort each chunk.  After concatenating them, the result equals the sorted array.

What is the most number of chunks we could have made?

Example 1:

Example 2:

Note:

  • arr will have length in range [1, 2000].
  • arr[i] will be an integer in range [0, 10**8].

Idea: 

Reduce the problem to 花花酱 769. Max Chunks To Make Sorted by creating a mapping from number to index in the sorted array.

arr = [2, 3, 5, 4, 4]

sorted = [2, 3, 4, 4, 5]

indices = [0, 1, 4, 2, 3]

Solution: Mapping

Time complexity: O(nlogn)

Space complexity: O(n)

C++

Python3