Use LEFT and RIGHT arrow keys to navigate between flashcards;
Use UP and DOWN arrow keys to flip the card;
H to show hint;
A reads text to speech;
22 Cards in this Set
- Front
- Back
|
Insertion |
n^2 |
|
|
bubble |
n^2 |
|
|
merge sort |
nlogn |
|
|
quick |
nlogn unstable |
|
|
counting sort |
n+k |
|
|
radix sort |
nk where k is max number of digits |
|
|
build heap |
O(n) |
|
|
heapsort |
O(nlogn) |
|
|
heapify |
O(logn) |
|
|
Adjacency list size |
tight v + e |
|
|
adjacent matrix size |
tight V^2 |
|
|
DFS |
Depth first search. Keep iterating until we hit a node that has no more children that are unvisited then go back one and repeat until ever node is visited. |
|
|
BFS |
Breath first search. all node children get visited at the same time. then lexographicaly a new node from the children is visited. |
|
|
MST |
minimum spanning tree. We use this method to reduce the number of edges that we visit only once, and try to maintain the lowest cost to any individual node from the first node. Prim (nodal), Krushals (edge). |
|
|
SSSP |
Single Source Shortest Path. Given the a single source find the smallest path possible to each other node while reading an edge more than once. Dijkstras and Bellman Ford |
|
|
APSP |
ALL pairs shortest paths. Use Floyd which is a dynamic programming approach. |
|
|
Dijstra Runtime |
tight V^3 improved by binary heap ( E lg V) |
|
|
Bellman Ford Runtime |
tight VE |
|
|
Prim |
Runtime O(V^2) or O(ElgV) with binary heap. Uses the next cheapest branch from the node and then all grey nodes until all nodes are grey. |
|
|
Krushals |
Runtime O(E lg V). Compares edges by least value but prevents any cycles from being created. |
|
|
NP Vs P |
NP non polynomial. P polynomial time. |
|
|
Np Rules |
|
