Programming/Algorithms: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
== Pseudocode == | |||
=== Binary Tree Search === | |||
<pre> | |||
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 | |||
</pre> | |||
[https://en.wikipedia.org/wiki/Binary_search_tree#Iterative_search Source] | |||
== Big O Notation == | |||
{{Note|Adapted from [https://www.bigocheatsheet.com/ Big-O Cheat Sheet] }} | |||
{| class="wikitable" | {| class="wikitable" | ||
Revision as of 16:32, 18 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
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) | |