Tech

Algorithms

Last Updated: March 27, 2021, at 07:08 PM MST

TBD. All sort of fun algorithms, and a discussion of Big-O notation.

Big-O Notation

Big-O notation is a mechanism for describing the runtime or memory usage for an algorithm. These descriptions employ variables such as n representing the number if items used by the algorithms.

For example, a simple for loop, iterating over an array of size n demonstrates a linear (O(n)) piece of code:

for (int n = 0; n < 16; n++)
{
     std::cout << n << std::endl;
}

Big-O notation takes a simplified view. If there are a trillion items being evaluated, then any constant functionality (eg. initialization or takedown code, not dependent on the input), or constant repetitions (eg. scanning the input twice) are deemed inconsequential compared to the size of the input.

Note: This differs from general optimization approaches, which may look to improve many components -- especially useful in high performance settings, including video games, or large numerical problem solving.

Important ones to know:

  • O(1) - constant time (does not rely on the input at all; ideal)
  • O(1/n) - I'm not sure how you managed this, but good job
  • O(log(n)) - crops up for searching a sorted array
  • O(n) - linear time (commonly accepted for processing input - need to visit each item)
  • O(n log n) - commonly crops up for sorting a list of items (eg. worst case for merge sort)
  • O(nx) - for x > 0, polynomial (eg. quadratic; watch for it in nested for-loops)
  • O(xn), O(nn) - exponential (bad, real bad; avoid at all costs)
  • O(n!) - factorial (don't, just don't)

Sources and Supplemental:

Sorting

There are a whole barrel full of sorting algorithms out there, and some smart cookie researchers and grad students continuing to push the limits on this, and try to analyze the ideal sorting methods for given data sets. Sorting is essential for allowing rapid access to ordered data, and useful for a variety of other mechanisms, from displaying ordered lists to ranking property values.

Required viewing: "Sorting Out Sorting" (1981, University of Toronto):

Some well known sorting algorithms:

  • Quicksort
  • Mergesort
  • Insertion sort
  • Bubblesort (okay, its not popular in practise, but there's a video game - I thought Dr. Mario, but I'm not finding what I'm looking for - that can illustrate this swapping style)

Some important other sorting algorithms:

  • Heapsort
  • Bucketsort
  • * Radix Sort

Sources and Supplemental:

Searching

Given a set of data, searching is a means of retrieving information, or calculating a value within a searchable space. It is easiest to consider this being motivated by efficiently accessing data within a database, such as a specific banking transaction across millions of active accounts.

Optimization problems also fall under the realm of searching algorithms, such as finding the shortest path in a graph, or optimizing scheduling.

Often using specific data structures can improve the runtime, or even memory useage, for such algorithms. For example a search tree can be used to quickly find an item. Some examples include:

  • Tree search algorithms: traversal via depth-first and breadth-first search, tree-pruning such as in branch and bound
  • Graph algorithms: Dijkstra's algorithm, finding nearest neighbour

Sources and Supplemental:

P and NP Problems

P: a decision problem that can be solved quickly (polynomial time)

NP: a decision problem such that a solution to the problem verified quickly (polynomial time); "non-deterministic polynomial time"
NP-complete: an NP problem that can be reduced to another NP-complete problem

For example, solving a sudoku puzzle is NP, since given a solution to the puzzle, its easy to verify the solution; but finding the solution is difficult.

There are other complexity classes, but whether P = NP is a key computational complexity question, and impacts how we tell our customers that a problem is indeed "hard" to solve (computationally hard).

Sources and Supplemental:

BlogIt Side bar

Recently Written

erika: end hiding comments and categories

erika: end hiding comments and categories

Group-Specific Sidebar

Blix theme adapted by David Gilbert, powered by BlogIt