Please enable JavaScript.
Coggle requires JavaScript to display documents.
Algorithms (Collections (Arrays (Set Size
Access by indices.
Hard to add…
Algorithms
Collections
Arrays
Set Size
Access by indices.
Hard to add and delete from middle, and change array size if already filled up.
LinkedList
No indices, but links
Adding and removing elements easier
Saves a reference to next element.
Stacks
LIFO
Put on top, access to top
Push and Pop: when order matters.
-
-
Sorting
Bubble
Compare with next and switch if applicable.
n-1 comparisons for finding biggest element.
n-1 again for next one.
n-1 iterations, each with n-1 comparison
(n-1)(n-1) = O(n^2) = worst case.
O(n) = Best case when already sorted.
InSpace sorting so S = O(1)
Merge
Divide and Conquer.
Sort and Merge back.
The number of comparison at each steps remain at most as n, in Log(n) steps.
O(n)= nlog(n)
Space efficiency S = O(n) As you can get rid of the old ones after each step
Quick
Pick a pivot, and put lower before and greater after it, keep picking pivots recursively.
Worst case: All the comparisons every time (if pivots already in right place) = O(n^2)
Average and best case = nlog(n)
InPlace S = O(1)
Search
Binary Search
On sorted array
if n = 8, then steps needed are
2 power 3 = 8
3+1 = 4
log2 of 8 = 3
fo efficiency = log2 of N = O(log(n))
BINARY IS LogN
-
-
-
Sets
No Ordering, no repetitions
Graph: like networks
Nodes are connected by edges, edges are weighted.
Edges can have directions.
DFS: Stacks
BFS: Queues.
-
Dijkstra: Greedy, take the shortest weighted path.
O(|V|^2)
-