Press "Enter" to skip to content

Posts published in “SP”

花花酱 SP5 Binary Search

Template:

Time complexity: O(log(r-l)) * O(f(m) + g(m))

Space complexity: O(1)

 

Slides:

Lower Bound / Upper Bound

Mentioned Problems

花花酱 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:

 

花花酱 Fenwick Tree / Binary Indexed Tree / 树状数组 SP3

本期节目中我们介绍了Fenwick Tree/Binary Indexed Tree/树状数组的原理和实现以及它在leetcode中的应用。
In this episode, we will introduce Fenwick Tree/Binary Indexed Tree, its idea and implementation and show its applications in leetcode.

Fenwick Tree is mainly designed for solving the single point update range sum problems. e.g. what’s the sum between i-th and j-th element while the values of the elements are mutable.

Init the tree (include building all prefix sums) takes O(nlogn)

Update the value of an element takes O(logn)

Query the range sum takes O(logn)

Space complexity: O(n)


Applications:

Implementation:

C++

Java

Python3

Applications

花花酱 LeetCode Input Size V.S. Time Complexity SP2

本期节目介绍了输入数据规模和时间复杂度上限的关系,可以通过数据规模推算使用算法的类型。

 

  • < 10: O(n!) permutation
  • < 15: O(2^n) combination
  • < 50: O(n^4) DP
  • < 200: O(n^3) DP, all pairs shortest path
  • < 1,000: O(n^2) DP, all pairs, dense graph
  • < 1,000,000: O(nlogn), sorting-based (greedy), heap, divide & conquer
  • < 1,000,000: O(n), DP, graph traversal / topological sorting (V+E), tree traversal
  • < INT_MAX: O(sqrt(n)), prime, square sum
  • < INT_MAX: O(logn), binary search
  • < INT_MAX: O(1) Math

花花酱 LeetCode Disjoint set / Union Find Forest SP1

Disjoint-set/Union-find Forest

Find(x): find the root/cluster-id of x

Union(x, y): merge two clusters

Check whether two elements are in the same set or not in O(1)*.

Find: O(ɑ(n))* ≈ O(1)

Union: O(ɑ(n))* ≈ O(1)

Space: O(n)

Without optimization: Find: O(n)

Two key optimizations:

  1. Path compression: make tree flat
  2. Union by rank: merge low rank tree to high rank one

*: amortized

ɑ(.): inverse Ackermann function

 

Implementations:

C++

Java

Python

Union-Find Problems

References