Algorithms reference data
Classic algorithms, strategies, and complexity.
Topic guide
What Algorithms covers
Algorithm reference data is organized by design strategy rather than by application: searching and sorting, dynamic programming, greedy methods, backtracking and graph traversal, topped by the complexity classes that say which problems are efficiently solvable at all. An algorithm entry gives its idea and its cost, and the cost is the part that decides whether it is usable: an O(n log n) sort handles millions of items, an exponential search does not. The recurring skill is recognizing the structure of a problem (overlapping subproblems, a greedy-choice property, a need to explore all possibilities) and picking the matching strategy.
Key ideas
- Time and space complexity
- How running time and memory grow with input size, in Big-O terms. The same problem can have algorithms with very different growth rates.
- Divide and conquer
- Split a problem into smaller independent parts, solve them and combine the results. Merge sort and binary search are examples.
- Dynamic programming
- Solve a problem with overlapping subproblems by storing the results of subproblems so each is computed once.
- Greedy algorithm
- Make the locally best choice at each step. It is correct only when the problem has the greedy-choice property.
- Backtracking
- Build a solution step by step and abandon a partial solution as soon as it cannot lead to a valid one.
- P versus NP
- P is the class of problems solvable in polynomial time; NP those whose solutions can be verified in polynomial time. Whether they are equal is open.
- Stable sort
- A sort that keeps equal elements in their original order, which matters when sorting by several keys in turn.
Common pitfalls
- Choosing an algorithm by its best-case bound. Quicksort's worst case is O(n^2) and linear search's best case is O(1), but average and worst cases decide the experience.
- Applying a greedy method without proving it correct; many problems that look greedy are not (the 0/1 knapsack).
- Treating Big-O as a speed measurement. It compares growth rates, not the time of one run on one machine.
- Assuming NP-hard means impossible. Approximation, heuristics and exact methods on small instances are often practical.
Using it from an agent
- State the input assumptions (sorted, non-negative weights, bounded range) when recommending an algorithm.
- Explain the key idea in one sentence, give the complexity and mention a common library implementation.
- For optimization problems, say whether the algorithm is exact or approximate.
Start with: Sorting Algorithms · Complexity Classes
Datasets in Algorithms
-
Backtracking Algorithms
Algorithms that explore candidates and abandon partial solutions.
12 entries -
Complexity Classes
Key computational complexity classes and the problems they contain.
13 entries -
Dynamic Programming Patterns
Classic problems solved with dynamic programming.
15 entries -
Graph Traversal Algorithms
Fundamental algorithms for navigating graphs.
12 entries -
Greedy Algorithms
Algorithms that make locally optimal choices at each step.
11 entries -
Search Algorithms
Reference comparison of fundamental search algorithms.
9 entries -
Sorting Algorithms
Comparison of fundamental sorting algorithms with time and space complexity.
12 entries
Fetch this category
One request returns the category with all of its dataset summaries. Append
?format=yaml or ?format=toon for the other encodings.
GET https://yjtoon.com/api/category/algorithms?format=json