Programming/Algorithms: Difference between revisions
Jump to navigation
Jump to search
| Line 16: | Line 16: | ||
[https://en.wikipedia.org/wiki/Binary_search_tree#Iterative_search Source] | [https://en.wikipedia.org/wiki/Binary_search_tree#Iterative_search Source] | ||
=== BFS === | |||
<pre> | |||
procedure BFS(G, root) is | |||
let Q be a queue | |||
label root as explored | |||
Q.enqueue(root) | |||
while Q is not empty do | |||
v := Q.dequeue() | |||
if v is the goal then | |||
return v | |||
for all edges from v to w in G.adjacentEdges(v) do | |||
if w is not labeled as explored then | |||
label w as explored | |||
w.parent := v | |||
Q.enqueue(w) | |||
</pre> | |||
[https://en.wikipedia.org/wiki/Breadth-first_search#Pseudocode Source] | |||
=== DFS === | === DFS === | ||
Revision as of 07:54, 19 January 2023
Pseudocode
Binary Tree Search
Iterative-Tree-Search(x, key)
while x ≠ NIL and key ≠ x.key then
if key < x.key then
x := x.left
else
x := x.right
end if
repeat
return x
BFS
procedure BFS(G, root) is
let Q be a queue
label root as explored
Q.enqueue(root)
while Q is not empty do
v := Q.dequeue()
if v is the goal then
return v
for all edges from v to w in G.adjacentEdges(v) do
if w is not labeled as explored then
label w as explored
w.parent := v
Q.enqueue(w)
DFS
procedure DFS(G, v) is
label v as discovered
for all directed edges from v to w that are in G.adjacentEdges(v) do
if vertex w is not labeled as discovered then
recursively call DFS(G, w)
procedure DFS_iterative(G, v) is
let S be a stack
S.push(v)
while S is not empty do
v = S.pop()
if v is not labeled as discovered then
label v as discovered
for all edges from v to w in G.adjacentEdges(v) do
S.push(w)
Big O Notation
Adapted from Big-O Cheat Sheet
| Data Structure | Time Complexity | Space Complexity | Notes | |||
|---|---|---|---|---|---|---|
| Average -> Worst | ||||||
| Access | Search | Insertion | Deletion | |||
| Array | Θ(1) -> O(1) | Θ(n) -> O(n) | Θ(n) -> O(n) | Θ(n) -> O(n) | O(n) | |
| Stack | Θ(n) -> O(n) | Θ(n) -> O(n) | Θ(1) -> O(n) | Θ(1) -> O(n) | O(n) | |
| Queue | Θ(n) -> O(n) | Θ(n) -> O(n) | Θ(1) -> O(n) | Θ(1) -> O(n) | O(n) | |
| Linked List | Θ(n) -> O(n) | Θ(n) -> O(n) | Θ(1) -> O(n) | Θ(1) -> O(n) | O(n) | |
| Double Linked List | Θ(n) -> O(n) | Θ(n) -> O(n) | Θ(1) -> O(n) | Θ(1) -> O(n) | O(n) | |
| Hash Table | N/A | Θ(1) -> O(n) | Θ(1) -> O(n) | Θ(1) -> O(n) | O(n) | |
| Binary Search Tree | Θ(log(n)) -> O(n) | Θ(log(n)) -> O(n) | Θ(log(n)) -> O(n) | Θ(log(n)) -> O(n) | O(n) | |
| B Tree | Θ(log(n)) -> O(log(n)) | Θ(log(n)) -> O(log(n)) | Θ(log(n)) -> O(log(n)) | Θ(log(n)) -> O(log(n)) | O(n) | Self-balancing |
| Data Structure | Time Complexity | Space Complexity | Notes | ||
|---|---|---|---|---|---|
| Best | Average | Worst | |||
| Bubble Sort | Ω(n) | Θ(n^2) | O(n^2) | O(1) | |
| Quicksort | Ω(n log(n)) | Θ(n log(n)) | O(n^2) | O(log(n)) | |
| Mergesort | Ω(n log(n)) | Θ(n log(n)) | O(n log(n)) | O(n) | |
| Insertion Sort | Ω(n) | Θ(n^2) | O(n^2) | O(1) | |
| Timsort | Ω(n) | Θ(n log(n)) | O(n log(n)) | O(n) | Combination of Mergesort and Insertion Sort made for Python |
| Heapsort | Ω(n log(n)) | Θ(n log(n)) | O(n log(n)) | O(1) | |
| Data Structure | Time Complexity | Space Complexity | Notes | ||
|---|---|---|---|---|---|
| Best | Average | Worst | |||
| BFS | O(V + E) = O(b^d) | O(V) = O(b^d) | |||
| DFS | O(b^d) | O(E) = O(bd) | |||
| DFS, recursive | O(V + E) | O(V) | |||