Programming/Algorithms: Difference between revisions
Jump to navigation
Jump to search
| Line 74: | Line 74: | ||
|+ Array Sorting Algorithms | |+ Array Sorting Algorithms | ||
|- | |- | ||
! rowspan="2"| Data Structure !! colspan="3"| Time Complexity !! rowspan="2"| Space Complexity !! rowspan=" | ! rowspan="2"| Data Structure !! colspan="3"| Time Complexity !! rowspan="2"| Space Complexity !! rowspan="2"| Notes | ||
|- | |- | ||
! Best !! Average !! Worst | ! Best !! Average !! Worst | ||
| Line 89: | Line 89: | ||
|- | |- | ||
| Heapsort || Ω(n log(n)) || Θ(n log(n)) || O(n log(n)) || O(1) | | Heapsort || Ω(n log(n)) || Θ(n log(n)) || O(n log(n)) || O(1) | ||
|} | |||
{| class="wikitable" | |||
|+ Tree Traversing Algorithms | |||
|- | |||
! rowspan="2"| Data Structure !! colspan="3"| Time Complexity !! rowspan="2"| Space Complexity !! rowspan="2"| 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) | |||
|} | |} | ||
Revision as of 07:52, 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
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) | |||