Flashcards › Technology & Coding › Computer Science
Algorithms and Big-O
Classic algorithms, how fast they are, and strategies for solving problems.
0 of 63 known
63 cards
- AlgorithmTermA finite list of steps that solves a problem
- Big-O notationTermDescribes how running time or memory grows as input grows
- O(1)TermConstant time; stays the same as input grows
- O(log n)TermLogarithmic time; grows slowly, like binary search
- O(n)TermLinear time; grows in proportion to input size
- O(n log n)TermTypical of efficient sorting like merge sort
- O(n squared)TermQuadratic time; typical of simple nested loops
- O(2 to the n)TermExponential time; becomes huge very quickly
- Time complexityTermHow running time grows with input size
- Space complexityTermHow memory use grows with input size
- Linear searchTermCheck each item in order until found; O(n)
- Binary searchTermRepeatedly halve a sorted list to find an item; O(log n)
- Binary search requirementTermThe data must be sorted
- Bubble sortTermRepeatedly swaps adjacent items that are out of order; O(n squared)
- Selection sortTermRepeatedly picks the smallest item and places it first; O(n squared)
- Insertion sortTermBuilds a sorted list one item at a time; good for small or nearly sorted lists
- Merge sortTermSplits the list, sorts the halves, then merges; O(n log n)
- Quick sortTermPicks a pivot and partitions around it; average O(n log n)
- Heap sortTermSorts using a heap; O(n log n)
- PivotTermThe element used to partition in quick sort
- Stable sortTermA sort that keeps equal items in their original order
- Divide and conquerTermSplit a problem, solve the parts, combine the answers
- RecursionTermA function calling itself on smaller input
- Base caseTermThe stopping point of a recursion
- Dynamic programmingTermSolve overlapping subproblems once and store the results
- MemoizationTermCaching results of function calls
- Greedy algorithmTermPick the best choice at each step
- Brute forceTermTry every possibility
- BacktrackingTermTry choices and undo them when they fail
- Breadth-first search (BFS)TermExplore a graph level by level using a queue
- Depth-first search (DFS)TermExplore a graph as deep as possible using a stack or recursion
- Dijkstra's algorithmTermFinds shortest paths in a weighted graph with non-negative weights
- A* searchTermA pathfinding algorithm that uses a guess of distance to the goal
- Minimum spanning treeTermA tree connecting all nodes with smallest total weight
- Kruskal's and Prim'sTermAlgorithms for finding minimum spanning trees
- Topological sortTermOrdering tasks so each comes after its prerequisites
- HashingTermTurning data into a fixed-size number for fast lookup
- CollisionTermWhen two keys hash to the same spot
- Euclid's algorithmTermFinds the greatest common divisor using repeated remainders
- Sieve of EratosthenesTermFinds all primes up to a number by crossing out multiples
- Fibonacci sequenceTermEach number is the sum of the two before: 0, 1, 1, 2, 3, 5...
- FactorialTermn! is the product of all whole numbers from 1 to n
- Tower of HanoiTermA puzzle that is a classic recursion example
- Traveling salesman problemTermFind the shortest route visiting every city once; very hard
- NP-completeTermA class of hard problems with no known fast solution
- P vs NPTermA famous open question about whether hard-to-solve problems are also easy to check
- HeuristicTermA practical shortcut that finds a good answer, not always the best
- PseudocodeTermPlain-language description of an algorithm
- InvariantTermA condition that stays true during an algorithm
- Best caseTermThe fastest an algorithm can run
- Worst caseTermThe slowest an algorithm can run
- Average caseTermTypical running time over many inputs
- In-place algorithmTermUses very little extra memory
- Two pointersTermA technique using two positions that move through data
- Sliding windowTermA technique moving a fixed range along data
- PageRankTermGoogle's algorithm that ranks pages by links to them
- Compression algorithmTermMakes data smaller, like ZIP or JPEG
- Lossless compressionTermCompression that can be exactly reversed
- Lossy compressionTermCompression that discards some data, like JPEG
- Random number generatorTermAn algorithm that makes numbers that look random
- Machine learning algorithmTermAn algorithm that learns patterns from data
- Al-KhwarizmiTermPersian mathematician whose name gave us the word algorithm
- Algorithm originTermNamed after a 9th-century scholar al-Khwarizmi
Download this deck
- CSVExcel, Google Sheets, Numbers
- Anki / Quizlet (tab-separated)Import straight into Anki or Quizlet
- JSONFor programmers and apps
- Plain textOne card a line, “front : back”, ready for Peabody's flashcard maker to print
Want paper cards? Paste the plain-text download into the flashcard maker.