Week 2 - Unit 3 Flashcards
An algorithm’s careful use of time and space resources
efficiency
Running a program on many data sets to be sure its performance falls within required limits; timing the same algorithm on two different machines
Benchmarking
The study of the efficiency of algorithms
Analysis of algorithms
An algorithm that searches for a target value in a random list by checking each list item in turn
sequential search
The efficiency classification of an algorithm whose work varies as a constant times the input size n
order of magnitude n
The task of finding a specific value in a list of values, or deciding it is not there
searching
The task of putting a list of values into numeric or alphabetical order
sorting
A sorting algorithm that keeps moving larger items toward the back of the list
Selection Sort
The efficiency classification of an algorithm whose work varies as a constant times the square of the input size n
Order of magnitude n^2
floating-point operations per second
flops
An algorithm that searches for a target value in a sorted list by checking at the midpoint and then repeatedly cutting the search section in half
binary search
The efficiency classification of an algorithm whose work varies as a constant times log(n)
Order of magnitude log(n)
An algorithm that does less work than some polynomial expression of the input size n
polynomial bounded
An algorithm whose work varies as some constant to the power of the input size n
exponential algorithm
A problem for which no polynomial bounded solution exists
intractable
An algorithm that doesn’t give the exact answer to a problem, but provides a close approximation to a solution
approximation algorithm
A sorting algorithm that makes multiple passes through the list from front to back, each time exchanging pairs of entries that are out of order
Bubble sort
A variation of the bubble sort that stops when no exchanges occur on a given pass
smart bubble sort
A sorting algorithm that breaks the list to be sorted into smaller and smaller lists and then assembles the smaller sorted lists back into larger and larger sorted lists
Mergesort
A variation of the sequential search that requires a sorted list and stops once it has passed the place where the target could occur
short sequential search
