Ultimele insemnari
- Lot Informatică 2023
- "Adolescent Grigore Moisil" International Programming Contest
- Nitro NLP Hackaton - 2023
- Fmi No Stress11
- Retrospectiva Anului 2021
- Zilele Algoritmice Romanesti 2021
- "Adolescent Grigore Moisil" International Programming Contest
- Retrospectiva Anului 2020
- 98
- Nave Ordonate
Categorii
- algoritmiada (7)
- algoritmica (1)
- concursuri (11)
- doi la suta (1)
- Evenimente (7)
- facebook (1)
- Features (3)
- girl camp (2)
- Girls (2)
- Girls camp (2)
- girls programming camp (3)
- google (1)
- infoarena (6)
- internships (1)
- interviu (12)
- life the universe and everything (7)
- organizare (3)
- potw (31)
- preoni 2008 (3)
- probleme (9)
- Selectie Girls Programming Camp (1)
- statistici (1)
- stiri (76)
- video (6)
Blogroll
Revizia anterioară Revizia următoare
Numbers everyone should know
Jeff Dean , a famous Google engineer, popularized a list of latency numbers everyone should know. The list is a great resource for designing infrastructure system.
Algorithms and their complexity occur often in critical parts of computer systems, but I find that a lot of even experienced engineers don't have a good understanding about how a n log n algorithm compares to a n^5 one.
In the coding contest world competitors think of these tradeoffs all the time. No wonder, there's a set of numbers every algorithm designer should know.
The table below shows the limits that can be reached in a few seconds by algorithms of different complexities. I've also added a few examples of algorithms or problems and data structures that may occur in those complexity classes.
| size of n | complexity | algorithms | data structures |
|---|---|---|---|
| 8 | nn | brute force, cartesian product | |
| 9-10 | n! | brute force, backtracking, next_permutation | |
| 13-17 | 3n | dynamic programming with exponential states | hash_map (to store the states) |
| 15 - 20 | n2 2n | dynamic programming with exponential states | bitsets, hash_map |
| 15 - 25 | 2n | subset enumeration, brute force, dynamic programming with exponential states | |
| 25 - 40 | 3n/2, 2n/2 | meet in the middle | hash tables (for set intersection) |
| 30-50 | n4, n5, n6 | ||
| 300-500 | n3 | all pairs shortest paths, largest sum submatrix, matrix multiplication, matrix chain multiplication, network flow | |
| 1000 - 10000 | n2 | largest empty rectangle, Dijkstra, Prim (on dense graphs) | |
| 30000 | n sqrt n | square root trick | two level tree |
| 60000 | n log2 n, nlog~2~3 | divide and conquer, Karatsuba | 2d range trees |
| 100000 | n log n | divide and conquer, sweep line, Kruskal, Dijkstra | segment trees, range trees, heaps, treaps, binary indexed trees, suffix arrays |
| 1000000 | n, n log log n, n log* n | set intersection, Eratosthenes sieve, radix sort, KMP, topological sort, euler tour, strongly connected components, 2sat | disjoint sets, tries, hash_map, rolling hash |
| 1000000000 | log(n), sqrt(n) | binary search, ternary search, fast exponentiation, euclid algorithm |
