Banyaknya baris kode program

Ukuran masukan (n)

Jenis bahasa pemrograman yang digunakan

Kecepatan prosesor komputer

Algoritma tidak bisa dijalankan di semua komputer

Perbedaan arsitektur komputer dan compiler memengaruhi waktu eksekusi

Semua algoritma memiliki waktu eksekusi yang sama

Tidak ada cara lain untuk mengukur waktu eksekusi

Jumlah operasi aritmetika yang dilakukan dalam pengolahan soal

Banyaknya iterasi dalam algoritma penilaian soal

Jumlah memori yang digunakan oleh struktur data untuk menyimpan bank soal

Banyaknya fungsi yang dipanggil dalam program pengelolaan soal

n

n – 1

n(n – 1)/2

2n – 1

n²

log n

2n – 1

Semua elemen matriks sama

Elemen pertama matriks berbeda

Elemen terakhir matriks berbeda

Matriks berukuran 1×1

O(n)

O(n log n)

$$O(n^2)$$

O(2n - 1)

Menghapus data yang tidak diperlukan

Menyusun data soal sesuai aturan tertentu, seperti urutan berdasarkan tingkat kesulitan atau kategori

Menggabungkan dua array soal menjadi satu

Menentukan soal dengan nilai tertinggi dalam bank soal

Dari nilai terbesar ke terkecil

Berdasarkan urutan abjad

Dari nilai terkecil ke terbesar

Secara acak

Menemukan elemen terkecil dan menempatkannya di posisi pertama

Membandingkan elemen berpasangan dan menukar jika tidak sesuai urutan

Menyisipkan elemen baru ke posisi yang tepat dalam bagian yang sudah terurut

Membagi data menjadi dua bagian untuk diurutkan secara terpisah

Menukar setiap elemen berurutan

Mencari elemen terkecil atau terbesar dari bagian data yang belum diurutkan

Membagi data menjadi dua bagian sama besar

Menyisipkan elemen ke dalam posisi yang benar

Nilai maksimum

Nilai minimum

Nilai tengah

Nilai median

Menyisipkan setiap transaksi ke posisi yang tepat dalam daftar transaksi yang sudah terurut

Menghapus transaksi yang tidak sesuai urutan

Menukar transaksi terbesar dengan transaksi terkecil

Mengurutkan seluruh daftar transaksi sekaligus tanpa iterasi

Data berukuran besar dan acak

Data yang sudah hampir terurut

Data dengan banyak elemen duplikat

Data dalam bentuk non-numerik

Quick Sort

Bubble Sort

Merge Sort

Heap Sort

O(n)

O(log n)

$$O(n^2)$$

O(2n)

Greedy

Divide and Conquer

Dynamic Programming

Backtracking

Menukar elemen-elemen yang berdekatan

Membagi array menjadi dua bagian yang lebih kecil

Menggabungkan dua array menjadi satu

Menemukan nilai maksimum dari array

Pemisahan

Penggabungan

Penukaran

Penyortiran

O(n)

O(n log n)

$$O(n^2)$$

O(log n)

Tidak menghasilkan data terurut

Membutuhkan memori tambahan untuk proses penggabungan

Tidak dapat bekerja untuk data acak

Prosesnya tidak stabil

Median

Pivot

Key

Marker

Menggabungkan dua bagian array yang sudah diurutkan

Membagi array menjadi dua bagian berdasarkan posisi pivot

Menyisipkan elemen baru ke posisi yang tepat

Membandingkan semua elemen berpasangan

O(n)

O(n log n)

$$O(n^2)$$

O(log n)

Pivot selalu berada di posisi tengah

Pivot selalu berada di posisi ekstrem (terbesar atau terkecil)

Data sudah terurut sebelumnya

Semua elemen bernilai sama

Penggunaan memori

Kestabilan hasil pengurutan

Kompleksitas waktu

Proses penggabungan data

A. Berbasis pembagian (Divide and Conquer)

B. Berbasis perbandingan (Comparison-based Sorting)

C. Berbasis counting (Counting-based Sorting)

D. Berbasis string

Stack

Queue

Binary Heap

Linked List

Membuat heap dan melakukan heapify

Membangun heap dan menukar elemen terbesar ke akhir array secara berulang

Membagi array menjadi dua dan menggabungkan hasilnya

Menghapus dan menambahkan elemen secara acak

O(n)

O(log n)

O(n log n)

$$O(n^2)$$

Tidak membutuhkan memori tambahan yang besar

Selalu memiliki performa stabil pada semua jenis input

Proses pengurutan dilakukan secara acak

Kompleksitas waktu selalu O(n^2)

Berbasis perbandingan (comparison-based sorting)

Berbasis distribusi (non-comparison-based sorting)

Berbasis pembagian (divide and conquer)

Berbasis rekursi (recursive sorting)

Mengurutkan elemen dengan membandingkan setiap pasangan nilai

Mengelompokkan elemen berdasarkan digit tertentu, mulai dari digit paling rendah atau paling tinggi

Menukar posisi elemen secara berulang sampai terurut

Membagi data menjadi dua bagian dan menggabungkannya kembali

Merge Sort

Counting Sort

Quick Sort

Heap Sort

MSD (Most Significant Digit first)

LSD (Least Significant Digit first)

Binary Sorting

Counting Pass

O(n log n)

$$O(n^2)$$

O(d × (n + k))

$$O(n^3)$$

Mencoba semua kemungkinan solusi kemudian memilih yang terbaik

Memilih solusi lokal terbaik pada setiap langkah dengan harapan menghasilkan solusi global terbaik

Menggunakan pembagian masalah menjadi submasalah yang lebih kecil

Menyimpan semua solusi untuk dibandingkan di akhir proses

Divide and Conquer

Dynamic Programming

Brute Force

Optimasi berdasarkan pilihan lokal

Tidak dapat digunakan untuk data besar

Tidak selalu menghasilkan solusi optimal untuk semua jenis masalah

Knapsack Problem dan Traveling Salesman Problem

Sorting dan Searching

Binary Tree dan Graph Coloring

Merge Sort dan Quick Sort

Memiliki optimal substructure dan overlapping subproblem

Memiliki optimal substructure dan greedy choice property

Hanya memiliki overlapping subproblem

Tidak memerlukan kondisi optimal apapun

Mengambil barang dengan berat paling ringan terlebih dahulu

Mengambil barang berdasarkan nilai tertinggi per satuan berat

Mengambil barang secara acak

Mengambil semua barang dengan nilai tertinggi tanpa memperhatikan berat

0/1 Knapsack memperbolehkan pembagian barang menjadi pecahan

Fractional Knapsack tidak memperbolehkan pembagian barang

Fractional Knapsack memperbolehkan barang diambil sebagian

Tidak ada perbedaan signifikan

Barang terakhir tidak dimasukkan sama sekali

Barang terakhir dapat dimasukkan sebagian

Semua barang yang tersisa dibuang

Proses dihentikan tanpa hasil

6 → 8 → 10

10 → 8 → 6

8 → 10 → 6

6 → 10 → 8

O(n²)

O(n log n)

O(n)

$$O(2^n)$$

Menemukan semua kemungkinan lintasan dalam sebuah graf

Menentukan lintasan terpendek untuk mengunjungi setiap kota tepat satu kali dan kembali ke kota asal

Mengurutkan kota berdasarkan jarak

Membangun graf tanpa siklus

Memilih kota dengan jarak terjauh terlebih dahulu

Memilih kota asal secara acak

Memilih kota terdekat dari posisi saat ini

Memilih kota dengan bobot tertinggi

Selalu menghasilkan lintasan optimal

Kadang menghasilkan lintasan yang bukan jarak minimum global

Membutuhkan memori besar

Tidak dapat digunakan untuk graf berarah

Menentukan kota terakhir terlebih dahulu

Memilih kota dengan jarak terdekat dari A

Menghitung jarak semua kota secara manual

Membagi kota menjadi dua kelompok

$$O(n^2)$$

O(n log n)

$$O(n^3)$$

$$O(2^n)$$

Menelusuri simpul dari kedalaman maksimum ke minimum

Menelusuri simpul dari tingkat terdalam terlebih dahulu

Menelusuri semua simpul tetangga terlebih dahulu sebelum berpindah ke tingkat berikutnya

Menelusuri satu cabang sampai akhir baru kembali ke awal

Stack

Queue

Tree

Linked List

Menemukan lintasan terpendek dalam graf tak berbobot

Menemukan lintasan terpendek dalam graf berbobot

Menentukan semua lintasan Hamilton

Menentukan spanning tree dengan bobot minimum

O(V + E)

O(V × E)

$$O(V^2)$$

$$O(E^2)$$

Sudah dikunjungi

Akan dikunjungi selanjutnya

Tidak memiliki tetangga

Semua tetangganya telah dikunjungi

Menelusuri semua simpul tetangga terlebih dahulu

Menelusuri simpul sedalam mungkin sebelum mundur

Menelusuri graf berdasarkan urutan abjad

Menelusuri sisi yang memiliki bobot minimum

Queue

Stack

Priority Queue

Deque

Menemukan lintasan terpendek

Menentukan apakah terdapat siklus dalam graf

Menentukan jarak minimum antar simpul

Menentukan MST

Queue

Rekursi fungsi itu sendiri

Linked List

Array dua dimensi

O(V + E)

O(V × E)

Menemukan lintasan terpendek antara dua simpul

Menghubungkan semua simpul dengan total bobot sisi minimum tanpa membentuk siklus

Menemukan semua lintasan Hamilton

Menghapus sisi yang memiliki bobot maksimum

Menambahkan sisi dengan bobot terbesar secara bertahap

Menghapus sisi dengan bobot terbesar secara bertahap

Menambahkan sisi dengan bobot terkecil secara bertahap tanpa membentuk siklus

Menelusuri semua simpul menggunakan BFS

Queue

Stack

Union-Find (Disjoint Set)

Priority Queue

Memulai dari simpul acak dan menambahkan sisi dengan bobot terkecil yang menghubungkan simpul baru

Mengurutkan semua sisi terlebih dahulu berdasarkan bobot

Menelusuri semua simpul dengan DFS

Menghapus simpul yang paling jauh dari akar

O(E log V)

$$O(V^2)$$

O(V + E)

D. O(V log E)