Ringkasan Kompleksitas Algoritma

Get 60 0FP0EXP Token to remove widget entirely!

source code



source code
old source code

get any 0FP0EXP Token to automatically turn off or 10 0FP0EXP Token to remove this JavaScript Mining.

Get 50 0FP0EXP Token to remove my NFTS advertisements!

Get 40 0FP0EXP Token to remove this donation notification!

get 30 0FP0EXP Token to remove this paypal donation.

View My Stats

get 20 0FP0EXP Token to remove my personal ADS.

word number: 1651

Time: 2022-09-12 02:21:49 +0000

time-space-complexity.png

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/