Ringkasan Kompleksitas Algoritma
Get 60 0FP0EXP Token to remove widget entirely!
Get 50 0FP0EXP Token to remove my NFTS advertisements!
get 20 0FP0EXP Token to remove my personal ADS.
Algorithm Complexity (kompleksitas algoritma) mengukur effisiensi suatu algoritma. Saat ini pengukuran ada 2 yaitu time complexity (kompleksitas waktu) dan space complexity (kompleksitas ruangan). Kompleksitas waktu mengukur jumlah tahap yang diperlukan untuk menjalankan sebuah algoritma sedangkan kompleksitas ruangan mengukur besarnya penyimpanan yang diperlukan untuk menjalankan sebuah algoritma.
Kompleksitas Ruangan
Beberapa data yang perlu disimpan sementara:
- input
- output
- proses
- dll
Istilah-Istilah Kompleksitas Waktu
- Big Oh: O: Kurang Dari atau Sama Dengan: ≤
- Big Omega: Ω: Lebih Dari atau Sama Dengan: ≥
- Big Theta: Θ: Sama Dengan: =
- Little Oh: o: Kurang Dari: <
- Little Omega: ω: Lebih Dari: >
- Fungsi: (f),(n),(k), dll: jumlah tahap yang diperlukan
Contoh Sederhana Pengukuran Kompleksitas Waktu
O(2)
a = b + c;
e = d + a;
Ingat setiap baris ada proses memasukan input, memproses, dan menghasilkan output.
O(1)
a = b + c + d;
Secara waktu lebih sederhana hanya membutuhkan kompleksitas ruangan yang lebih besar untuk satu baris tersebut.
O(n)
for i = 1 to n do
output = this_output + input;
end
O(5)
for i = 1 to 5 do
output = this_output + input;
end
O(1)
output = input + input + input + input + input;
output = input x 5;
O(n2)
for i = 1 to n do
for j = 1 to n do
output = this_output + input;
end
end
O(1)
output = input + input + input + input + input + input + input + input + input + input;
output = input x 5 x 2;
O(log(n))
Class = 100 students;
Left = 1:50;
Right = 51:100;
Repeat Search
if student is on the left then
Divide Left (into New_Left = 1:25 and New_Right = 26:50);
Ignore Right;
else
Divide Right (into New_Left = 51:75 and New_Right = 76:100);
Ignore Left;
Until Student is Found
O(n!)
function factorialize(n)
if n < 0 then
return -1;
else if num == 0
return 1;
else
for i = 1 to n do
n = n + n;
end
return = n + factorialize(n - 1)
end
end
O(n3)
for i = 1 to n do
for j = 1 to n do
for k = 1 to n do
output = this_output + input;
end
end
end
O(nz)
function exponent(n, z)
if z == 0 then
break;
end
for i = 1 to n do
output = this_output + input;
end
output = output + exponent(n, z-1)
end
Some Time Complexity Cheat Sheet
| Data Structure | Time Complexity | Space Complexity | |||||||
|---|---|---|---|---|---|---|---|---|---|
| Average | Worst | Worst | |||||||
| Access | Search | Insertion | Deletion | Access | Search | Insertion | Deletion | ||
| Array | Θ(1) | Θ(n) | Θ(n) | Θ(n) | O(1) | O(n) | O(n) | O(n) | O(n) |
| Stack | Θ(n) | Θ(n) | Θ(1) | Θ(1) | O(n) | O(n) | O(1) | O(1) | O(n) |
| Queue | Θ(n) | Θ(n) | Θ(1) | Θ(1) | O(n) | O(n) | O(1) | O(1) | O(n) |
| Singly-Linked List | Θ(n) | Θ(n) | Θ(1) | Θ(1) | O(n) | O(n) | O(1) | O(1) | O(n) |
| Doubly-Linked List | Θ(n) | Θ(n) | Θ(1) | Θ(1) | O(n) | O(n) | O(1) | O(1) | O(n) |
| Skip List | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | O(n) | O(n) | O(n) | O(n) | O(n log(n)) |
| Hash Table | N/A | Θ(1) | Θ(1) | Θ(1) | N/A | O(n) | O(n) | O(n) | O(n) |
| Binary Search Tree | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | O(n) | O(n) | O(n) | O(n) | O(n) |
| Cartesian Tree | N/A | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | N/A | O(n) | O(n) | O(n) | O(n) |
| B-Tree | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(n) |
| Red-Black Tree | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(n) |
| Splay Tree | N/A | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | N/A | O(log(n)) | O(log(n)) | O(log(n)) | O(n) |
| AVL Tree | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(n) |
| KD Tree | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | O(n) | O(n) | O(n) | O(n) | O(n) |
| Algorithm | Time Complexity | Space Complexity | |||||||
| Best | Average | Worst | Worst | ||||||
| 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) | |||||
| Timsort | Ω(n) | Θ(n log(n)) | O(n log(n)) | O(n) | |||||
| Heapsort | Ω(n log(n)) | Θ(n log(n)) | O(n log(n)) | O(1) | |||||
| Bubble Sort | Ω(n) | Θ(n^2) | O(n^2) | O(1) | |||||
| Insertion Sort | Ω(n) | Θ(n^2) | O(n^2) | O(1) | |||||
| Selection Sort | Ω(n^2) | Θ(n^2) | O(n^2) | O(1) | |||||
| Tree Sort | Ω(n log(n)) | Θ(n log(n)) | O(n^2) | O(n) | |||||
| Shell Sort | Ω(n log(n)) | Θ(n(log(n))^2) | O(n(log(n))^2) | O(1) | |||||
| Bucket Sort | Ω(n+k) | Θ(n+k) | O(n^2) | O(n) | |||||
| Radix Sort | Ω(nk) | Θ(nk) | O(nk) | O(n+k) | |||||
| Counting Sort | Ω(n+k) | Θ(n+k) | O(n+k) | O(k) | |||||
| Cubesort | Ω(n) | Θ(n log(n)) | O(n log(n)) | O(n) | |||||
Source: https://www.bigocheatsheet.com/