Algorithms
Big O Notation
Big O notation measures the complexity of an operation relative to the size
of its input.
O(1)
describes an algorithm whose complexity is independent of the input,
such as accessing an element in an array by its index.
O(n)
describes an algorithm whose complexity increases linearly, such as
iterating through an array.
O(n^2)
describes an algorithm whose complexity increases quadratically,
such as comparing every element in an array to every other element in an array.
O(log n)
describes an algorithm whose complexity increases logarithmically,
such as dividing an array in half until only one element remains.
O(n log n)
describes an algorithm whose complexity increases
linearithmically, such as dividing an array in half and iterating through each half.
Binary Search
Binary search is an O(log n) algorithm that is used to find a value in a sorted
list of items. It works by searching for a value in the middle of a list,
and recursively discarding whichever half of the list is out of range. The result
of a binary search is undetermined if the list is unsorted. Binary search
is available in the Arrays and Collections classes.
Insertion Sort
Insertion sort is an O(n^2) average-case sorting algorithm. It works
by traversing through a list and sorting the previous elements by swapping them
in place. Insertion sort is a stable algorithm, which means equal values will
maintain their relative order. Insertion sort performs well for small data sets
despite its complexity because it’s efficient for partially sorted lists and
it requires no extra memory.
|
