Algorithms Flashcards
Big 0 - Sequential
O (n)
Loops n times
What is a Sequential Search?
Searches each element one by one until the search term is found, or the list is exhausted
What is a Selection Sort?
Starting from the first element, find the smallest number and swap it with the first item in the list.
Starting from the second element, find the smallest number and swap it with the second item in the list.
Repeat until you reach the final element.
Big O - Selection Sort
O (n2)
Loop inside a loop
What is a Binary Search?
- Compare k with the middle element of the list .
- If k is smaller than the middle element, disregard the second half of list. If k is greater than the middle element, disregard the second half of list.
(Reduces the size of the list at each step by half)
Big O - Binary Search
O (log n)
What is a Merge Sort
Divide the list (or array) of numbers into two halves. Recursively solve the two halves. Merge the two halves into a single sorted list
Big O - Merge Sort
O (n log n)
What is Kruskals Algorithm?
A greedy algorithm designed to find a minimal spanning tree from a graph.
Continue picking the minimal cost “fringe” edges so long as no cycles are formed.
What is Prim’s algorithm?
A greedy algorithm designed to find a minimal spanning tree from a graph.
Start from a random vertex, pick the lowest cost fringe vertex.
What is the difference between algorithms and programs?
▶ An algorithm is free from grammatical rules and content.
▶ A computer program must obey very stringent syntax rules
What is Euclid’s algorithm?
Finds the greatest common divisor where
GCD (m, n) = GCD (n, m mod n).
Repeat this sum until the answer is 0.
