SWE

less than 1 minute read

  • https://leetcode.com/
  • https://www.oreilly.com/library/view/algorithms-in-a/9781491912973/

Big O

  • O(1): Constant, primitive operations
  • O(log n): Logarithmic, reducing the size about half each time
  • O(nd) for d < 1: Sublinear
  • O(n): Linear
  • O(n log n): Linearithmic, divide in subproblems and merge in linear time
  • O(n2): Quadratic, nested for loops
  • O(2^n): Exponential, every subset, bruteforce numerical password O(10^n)
  • O(n!): Factorial, bruteforce TSP

Approaches

Greedy

Solve in steps making the best local decision. If the subproblem can be completed in O(log n), then the Greedy strategy will be O(n logn) (sort and grab). If the subproblem is O(n) then we have O(n^2) (selection sort).

Divide and Conquer

Often recursive, O(n) when the resolution is constant, if the resolution step is O(n) then we have O(n logn).

Dynamic Programming

Subdividing in simpler subproblems that are solved in a specific order and storing the results for future use. In many cases the solution is optimal.

Sorting

TODO

Searching

TODO

Graph

TODO

Path Finding

TODO

Network Flow

TODO

Computational Geometry

TODO

Spatial Tree Structures

TODO

Emerging Algorithm Categories

TODO

Principles of Algorithms

TODO

Leave a comment