Unit 1 - Section 3 Flashcards
Efficiency
the term used to describe an algorithm’s careful use of resources
Analysis of algorithms
the study of the efficiency of algorithms
Sequential Search
n/2 - not sufficiently time efficient for large values of n
** it is space efficient as it does not use more memory than the original input requires
O(n)
anything that varies as a constant times n ( and whose graph follows the basic shape of n)
Selection Sort algorithm
” grows” a sorted subsection of the list from back to the front.
(n-1/2) n
Order n²
The number of comparisons done by the selection sort algorithm grows at approximately the square of the problem size n²
An algorithm that does cn² work for any constant c is order of magnitude n² or O(n²)
Floating-point operations
Arithmetic operations such as additions and subtractions of real numbers
Data Clean-up Algorithms
Shuffle-left algorithm
Copy-Over algorithm
Converging-Pointers Algorithm
Binary Search
Only works on sorted lists
The number of times a number n can be cut in half and not go below 1 is called the logarithm of n to the base 2, which is abbreviated lgn ( also written log 2 n )
In general lgn = m is equivalent to 2 to the power of m = n
It is also space efficient as it requires only a small amount of additional storage to keep track of beginning, end and midpoint positions.
Algorithms of order of magnitude lgn
O(lgn) are like various modes of flying.
Pattern Matching
Usually involves a pattern lenght that is short compared with the text length, that is, when m is much less than n. In such cases, n-m+1 is essentially n.
The pattern matching algorithm is therefore 0(n) in the best case and 0(mxn) in the worst case.
Algorithms 0(lgn), O(n), and O(n²) are polynomialy bounded
in the amount of work they do as n increases
A collection of nodes and connecting edges is
called a graph
Hamiltonian Circuit
A path through a graph that begins and ends at the same node and goes through all other nodes exactly once
An O(2ⁿ) algorithm is called
an exponential algorithm
