unit 5 - 8 Flashcards
fibonacci algo
returns f(n - 1) + f(n - 2) if n > 1
fibonacci algo: runtime
O(2^n) without memoization; O(n) with memoization
fibonacci algo: memoization
checks for n in array; if not in, compute and store array[n] = f(n - 1) + f(n - 2); returns f(n - 1) + f(n - 2) if n > 1
tabulation
bottom-up; solve small problems first, then the original problem
dynamic programming
storing previously calculated values for better runtime and allow for quick retrievals as well as using smaller values to solve for even larger ones
bubble sort algo
quadratic / O(n^2); swap two items if the next item is larger thsn the previous
bubble sort; iterating over i and j
the algorithm iterates over both i and j to check multiple times and sort the entire list, not just items in relation to each other
selection sort algo
quadratic, O(n) best case; sets a ‘largest’ index, checks for larger values while iterating. picks smallest (2nd, 3rd smallest, etc,) value and places it at the beginning
merge sort
cuts a list in half while len >= 2; separates them to be sorted
merge
end of mergesort algorithm; checks which items are bigger before sorting items from smaller lists into a bigger one
binary search
O(logn); a list is broken in half. the median is checked. if != target value, search the sides depending on if the target is < or > than the median
tail recursion
the recursive call is the last statement executed by the function
recursion
breaking problems into subproblems, combining solutions;
function call within a function, using a base case
factorial algo
returns x * fact(x - 1)
factorial algo; runtime
O(n) without memoization
memoization
top-down; function checks to see if a value has been calculated and stored already or not. if not, perform recursive call
quicksort pivot
+- 1/2 of largest element
naive partition
store elements < pivot, then store elements > pivot
partition
ensures elements from 0 - i-1 are < pivot
ensures elements from I - j are => pivot
quicksort
matches the pivot’s value to its index, then switches the first, next, etc lowest value to the front
naive fibonacci: calls made
T(0), T(1),
T(n) = T(n1) + T(n2) + 1
