📖
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
  • Asymptotic Notations
  • Randomized Algorithms and Average-case Analysis
  • Amortized Analysis

Was this helpful?

  1. Algorithm
  2. Computer Science

Analysis

PreviousSortingNextComplexity Classes (P, NP)

Last updated 3 years ago

Was this helpful?

Asymptotic Notations

  • formal definition: f(n)=O(g(n))f(n) = O(g(n))f(n)=O(g(n))if there exists positive constantscccandn0n_0n0​such that 0≤f(n)≤cg(n)0 \le f(n) \le cg(n)0≤f(n)≤cg(n)for all n≥n0n \ge n_0n≥n0​.

  • lim⁡n→∞f(n)g(n)≤constant\lim_{n\to\infty} \frac{f(n)}{g(n)} \le constantlimn→∞​g(n)f(n)​≤constant

notation

(literal) meaning

example 1

example 2

example 3

more reference:

Randomized Algorithms and Average-case Analysis

Examples

  • the hiring problem: in average O(log(n)) instead of O(n)

  • quicksort: the cost is O(n log(n)) on average

  • hash table: expected O(1)

  • Rabin-Karp: sub-string matching

Amortized Analysis

Though the algorithm is deterministic, the cost of each step may be different

Examples

  • Binary Counter and Piggy Bank

    • pay only when a bit changes from 0 to 1

  • Hash Table

    • load factor better to be 1/2

    • need to resize when full

      • worst case cost: O(n)

      • amortized to O(1)

  • Union-find with path-compression: O(log* n) per union or per find

  • Weight balanced tree with rebuilding

    • O(log n) cost per insertion

      • O(1) cost for rebalance per insertion

      • O(log n) cost for insertion itself

Three ways for amortized analysis

  • Direct: count the total cost from an empty state all the way to the n-th operation O(f(n))

    • then the total cost of each operation is O(f(n)n)O(\frac{f(n)}{n})O(nf(n)​)

  • Piggy bank: pay O(k) “dollars” per operation

    • show that even though some of the operations are more expensive, the total cost of all n elements are no more than O(nk)

  • Potential function: design a potential functionΦ(s)\Phi (s)Φ(s)for a certain state, and analyze the change ofΦ\PhiΦ, from which we can derive the amortized cost

f(n)=O(g(n))f(n) = O(g(n))f(n)=O(g(n))
f(n)≤g(n)f(n) \le g(n)f(n)≤g(n)
n=O(n2)n = O(n^2)n=O(n2)
n2=O(n2)n^2 = O(n^2)n2=O(n2)
n3≠O(n2)n^3 \neq O(n^2)n3=O(n2)
f(n)=Ω(g(n))f(n) = \Omega(g(n))f(n)=Ω(g(n))
f(n)≥g(n)f(n) \ge g(n)f(n)≥g(n)
n≠Ω(n2)n \neq \Omega(n^2)n=Ω(n2)
n2=Ω(n2)n^2 = \Omega(n^2)n2=Ω(n2)
n3≠Ω(n2)n^3 \neq \Omega(n^2)n3=Ω(n2)
f(n)=Θ(g(n))f(n) = \Theta(g(n))f(n)=Θ(g(n))
f(n)=g(n)f(n) = g(n)f(n)=g(n)
n≠Θ(n2)n \neq \Theta(n^2)n=Θ(n2)
n2=Θ(n2)n^2 = \Theta(n^2)n2=Θ(n2)
n3≠Θ(n2)n^3 \neq \Theta(n^2)n3=Θ(n2)
f(n)=o(g(n))f(n) = o(g(n))f(n)=o(g(n))
f(n)<g(n)f(n) < g(n)f(n)<g(n)
n=o(n2)n = o(n^2)n=o(n2)
n2≠o(n2)n^2 \neq o(n^2)n2=o(n2)
n3≠o(n2)n^3 \neq o(n^2)n3=o(n2)
f(n)=ω(g(n))f(n) = \omega(g(n))f(n)=ω(g(n))
f(n)>g(n)f(n) > g(n)f(n)>g(n)
n≠ω(n2)n \neq \omega(n^2)n=ω(n2)
n2≠ω(n2)n^2 \neq \omega(n^2)n2=ω(n2)
n3=ω(n2)n^3 = \omega(n^2)n3=ω(n2)
Orders of common functions