📖
Wiki
Back to my personal website
  • Home
  • Equipment and Devices
    • 3D Printer
    • Laser Cutter
    • Motion Capture System
    • Sensors
      • RGB-D Cameras
      • Velodyne LiDAR
      • Zed Camera
      • RealSense D435i
      • IMU
    • eGPU
    • Nvidia AGX Xavier
    • CPU Benchmark
    • Installation Checklist
  • Development
    • Linux
      • Shell
      • GDB
      • Git
      • Tmux
      • Network
      • Tricks
      • Debug FAQ
    • CMake
      • Catkin Tools
      • CMakeLists
      • CMake Variables
      • CMake Commands
      • CMake: find_package()
    • ROS
      • Gazebo
      • wstool
      • roslaunch
      • rosbag
      • multi-threaded spinner
    • ROS2
      • Convert ROS1 bag to ROS2 bag
    • C++
      • C++ 11
      • C++ Examples
      • C++ Debug
      • Factory Method
      • Timing
    • Google Tools
      • GLog
      • GFlags
      • GTest
      • Style Guide
      • Clang Format
    • PCL
      • Point Type
      • Methods
      • Architecture
      • Code Explained
    • Open3D
      • Python API
      • Registration
      • Visualization
      • Tools
    • OpenCV
      • Documentation
      • Modules
    • Other Libraries
      • Eigen
      • Ceres
      • g2o
      • GTSAM
    • Website
  • Algorithm
    • SLAM
      • K-D Tree
      • Octree
      • Bag of Words
      • Distance Measures
      • Coordinate Systems
      • LOAM
      • Iterative Closest Point
      • Generalized ICP
      • Mahalanobis Distance
    • Computer Science
      • Computational Model
      • Sorting
      • Analysis
      • Complexity Classes (P, NP)
      • Divide and Conquer
      • Greedy Algorithm
      • Dynamic Programming
      • Tree
      • Graph
    • Computer Vision
      • Camera Models
      • Distortion
      • Motion Models
      • Shutter
      • Image Sensors
      • Epipolar Geometry
      • Multiple-View Geometry
    • Datasets
      • RGB-D Datasets
      • Point Cloud Datasets
      • LiDAR SLAM Datasets
  • Math
    • Optimization
      • Convex Optimization
      • Descent Methods
    • Probability
      • Moment
      • Covariance Matrix
      • Stochastic Process
    • Topology
      • References
      • Concepts
      • Topological Spaces
      • Representation of Rotations
      • Representation of 3-sphere
    • Algebra
      • Linear Algebra
      • Matrix Factorization
      • Condition Number
      • Matrix Lie Group
    • Differential Geometry
      • Manifold
      • Submanifold
      • Quotient Manifolds
      • Tangent Space
  • Quadrotor
    • PX4 Development
    • Companion Computer
    • Drone Hardware
    • Propeller Lock
    • Debug
  • Favorites
    • Bookmarks
Powered by GitBook
On this page
  • Three Steps
  • Master Theorem
  • Example Code: Merge Sort

Was this helpful?

  1. Algorithm
  2. Computer Science

Divide and Conquer

PreviousComplexity Classes (P, NP)NextGreedy Algorithm

Last updated 3 years ago

Was this helpful?

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>1the number of subproblems in the recursion

  • b>1b>1b>1the factor by which the subproblem size is reduced in each recursive call

  • andfffis asymptotically positive (positive for sufficiently largennn)

  • base case: T(c)T(c)T(c)is a constant whencccis a constant

  • compare nlog⁡ban^{\log_{b}{a}}nlogb​awith 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;
}