Comment on page

Divide and Conquer

Three Steps
Divide the problem into multiple subproblems in smaller size.
Conquer the subproblems recursively; set a straight forward way for base case.
Combine the solutions to the subproblems into the solution for the original problem.
Master Theorem
recurrence relation: T(n)=aT(nb)+f(n)T(n)=a T\left({\frac{n}{b}}\right)+f(n)T(n)=aT(bn​)+f(n)
​
​a>1a>1a>1
the number of subproblems in the recursion
​b>1b>1b>1
the factor by which the subproblem size is reduced in each recursive call
andfff
is asymptotically positive (positive for sufficiently largennn
)
base case: T(c)T(c)T(c)
is a constant whenccc
is a constant
compare nlog⁡ban^{\log_{b}{a}}nlogb​a
with f(n)f(n)f(n)
and this will lead to three regimes (>, =, <)
in recursion tree, compare root with leaves and see which part dominates
more reference: CLRS book page 94
Example Code: Merge Sort
#include <iostream>
#include <vector>
​
int merge(std::vector<int>& A, int start, int end, int middle, std::vector<int>& B){
  // combine 
  int i = start;
  int j = middle;
  for (int k = start; k<= end; ++k){
    if (i < middle && (j > end || A[i] <= A[j]))
      B[k] = A[i++];
    else
      B[k] = A[j++];
  }
  for (int k = start; k<= end; ++k){
    A[k] = B[k];
  }
}
​
int mergeSort(std::vector<int>& A, int start, int end, std::vector<int>& B){
  // divide and conquer
  if (end == start)
    return 0;
  int middle = (start + end + 1) / 2;
  mergeSort(A, start, middle - 1, B);
  mergeSort(A, middle, end, B);
  merge(A, start, end, middle, B);
}
​
int main(){
  int n;
  std::cin >> n; 
  std::vector<int> score(n);
  std::vector<int> temp(n);
  for (int k = 0; k < n; ++k)
    std::cin >> score[k];
​
  mergeSort(score, 0, n-1, temp);
​
  std::cout << n << std::endl;
  for (int k = 0; k < n; ++k)
    std::cout << score[k] << std::endl;
​
  return 0;
}
​

Complexity Classes (P, NP)

Greedy Algorithm

Last modified 2yr ago