Dalam ilmu komputer dan rekayasa sistem, algoritma adalah fondasi utama yang mendikte seberapa efisien, aman, dan skalabel sebuah aplikasi dijalankan. Namun, dengan ratusan algoritma yang eksis saat ini, insinyur sering kesulitan memilih algoritma terbaik untuk kasus penggunaan spesifik mereka.
Untuk mempermudah penjelajahan, cetak biru arsitektur visual di bawah memetakan taksonomi klasifikasi algoritma modern yang membagi 300+ algoritma ke dalam tiga paradigma era utama: Classic (🔵), Modern (🟢), dan Frontier/Research (🔴).
Kode Era Kategori: 🔵 Classic | 🟢 Modern | 🔴 Research/Frontier
Daftar Isi
- Sorting & Ordering
- Searching
- Graph Algorithms
- Dynamic Programming
- Machine Learning
- Deep Learning
- Cryptography
- Optimization
- Compression & Coding
- Number Theory & Math
- Computational Geometry
- Geospatial & Spatial Analysis
- String & Text Processing
- Scheduling & Systems
- Distributed Systems
- AI & Decision Making
- Bioinformatics
1. Sorting & Ordering
Comparison-Based
| Algoritma | Era | Kompleksitas | Penggunaan |
|---|---|---|---|
| Bubble Sort | 🔵 Classic | O(n²) | Edukasi, data kecil [Stable, Space: O(1)] (Contoh: Mengajarkan konsep dasar pengurutan dalam kelas ilmu komputer pemula) |
| Selection Sort | 🔵 Classic | O(n²) | Memory terbatas [Unstable, Space: O(1)] (Contoh: Sistem embedded dengan memori RAM yang sangat kecil) |
| Insertion Sort | 🔵 Classic | O(n²) | Data hampir terurut [Stable, Space: O(1)] (Contoh: Pengurutan sisipan log transaksi perbankan yang hampir selalu masuk berurutan) |
| Merge Sort | 🔵 Classic | O(n log n) | General purpose [Stable, Space: O(n)] (Contoh: Standard pengurutan data bertipe obyek besar (Linked List) di backend server) |
| Quick Sort | 🔵 Classic | O(n log n) | General purpose [Unstable, Space: O(log n)] (Contoh: Fungsi pengurutan bawaan C qsort untuk list angka mentah yang sangat panjang) |
| Heap Sort | 🔵 Classic | O(n log n) | Real-time systems [Unstable, Space: O(1)] (Contoh: Pengurutan prioritas kontrol penerbangan pesawat yang butuh memori tetap) |
| Shell Sort | 🔵 Classic | O(n log² n) | Embedded systems [Unstable, Space: O(1)] (Contoh: Komponen mikrokontroler sensor IoT yang lambat) |
| Tim Sort | 🟢 Modern | O(n log n) | Library standard [Stable, Space: O(n)] (Contoh: Algoritma bawaan sort() pada Python dan Arrays.sort() obyek pada Java) |
| Intro Sort | 🟢 Modern | O(n log n) | C++ std::sort [Unstable, Space: O(log n)] (Contoh: Pengurutan array game engine secara efisien menghindari skenario terburuk QuickSort) |
| Gnome Sort | 🔵 Classic | O(n²) | Pembelajaran [Stable, Space: O(1)] (Contoh: Demonstrasi algoritma sederhana pergerakan maju-mundur gnome pot bunga) |
| Pancake Sort | 🔵 Classic | O(n) flips | Diskrit, robotika [Unstable, Space: O(1)] (Contoh: Algoritma pembalikan (flipping) tumpukan kaset robotik di pabrik gudang) |
| Block Sort (WikiSort) | 🟢 Modern | O(n log n) | In-place stable sort [Stable, Space: O(1)] (Contoh: Mengurutkan record database jutaan baris tanpa memakan memori RAM tambahan) |
| Cocktail Shaker Sort | 🔵 Classic | O(n²) | Varian Bubble Sort [Stable, Space: O(1)] (Contoh: Penyisiran data korup bolak-balik dalam pita memori lama) |
| Comb Sort | 🔵 Classic | O(n²) | Improvement Bubble [Unstable, Space: O(1)] (Contoh: Penghilangan entitas "turtles" (nilai kecil di ujung kanan) pada dataset sensor murah) |
| Cycle Sort | 🔵 Classic | O(n²) | EEPROM/Flash [Unstable, Space: O(1)] (Contoh: Pengurutan array yang meminimalisir ausnya siklus tulis/write pada chip EEPROM) |
| Strand Sort | 🔵 Classic | O(n²) | Sublist extraction [Stable, Space: O(n)] (Contoh: Pemisahan untaian list pasien darurat dari list pasien umum secara berulang) |
| Tournament Sort | 🔵 Classic | O(n log n) | Priority queue [Unstable, Space: O(n)] (Contoh: Penjadwalan pemenang proses (job) eksekusi paralel di sistem operasi) |
| Tree Sort | 🔵 Classic | O(n log n) | Online sorting [Stable, Space: O(n)] (Contoh: Penyimpanan nama pelanggan yang terus masuk ke dalam Binary Search Tree untuk auto-complete) |
| Smooth Sort | 🔵 Classic | O(n log n) | Adaptive heap sort [Unstable, Space: O(1)] (Contoh: Pengurutan array data yang sebagian besarnya sudah terurut parsial (menggunakan Leonardo numbers)) |
| Library Sort | 🟢 Modern | O(n log n) | Cache-friendly [Stable, Space: O(n)] (Contoh: Pengurutan katalog buku perpustakaan digital dengan menyisakan gap ruang kosong) |
| Patience Sort | 🔵 Classic | O(n log n) | Card game solver [Stable, Space: O(n)] (Contoh: Mencari Longest Increasing Subsequence pada analisis tren harga saham) |
| Odd-Even Merge Sort | 🔵 Classic | O(n log² n) | Sorting network [Stable, Space: O(n)] (Contoh: Operasi sinkronisasi paralel data CPU dan GPU) |
| 3-Way Quick Sort | 🟢 Modern | O(n log n) | Duplicate elements [Unstable, Space: O(log n)] (Contoh: Mengurutkan warna bendera Belanda (merah, putih, biru) secara massal tanpa rekursi sia-sia) |
| Dual-Pivot Quick Sort | 🟢 Modern | O(n log n) | Java Arrays.sort() [Unstable, Space: O(log n)] (Contoh: Pengurutan tipe primitif (int/char) super cepat di belakang layar aplikasi Android modern) |
Non-Comparison (Linear)
| Algoritma | Era | Kompleksitas | Penggunaan |
|---|---|---|---|
| Counting Sort | 🔵 Classic | O(n + k) | Integer range kecil [Stable, Space: O(k)] (Contoh: Mengurutkan nilai ulangan sekolah (0-100) dari 10.000 murid seketika) |
| Radix Sort (LSD) | 🔵 Classic | O(nk) | Digit terkecil dulu [Stable, Space: O(n+k)] (Contoh: Pengurutan data KTP penduduk berdasarkan tahun, bulan, lalu tanggal lahir) |
| Bucket Sort | 🔵 Classic | O(n + k) | Distribusi seragam [Stable, Space: O(n)] (Contoh: Mengelompokkan nilai desimal probabilitas machine learning (0.0 hingga 1.0) ke dalam ember/bucket) |
| Radix Sort (MSD) | 🟢 Modern | O(nk) | Karakter terbesar [Stable, Space: O(n+k)] (Contoh: Mengurutkan jutaan daftar kata dalam kamus bahasa (lexicographical)) |
| Flash Sort | 🟢 Modern | O(n) avg | Distribusi non-uniform [Unstable, Space: O(m)] (Contoh: Mengurutkan sinyal analitik spektrum frekuensi dengan efisiensi mendekati linear) |
| Pigeonhole Sort | 🔵 Classic | O(n + k) | Varian Counting [Stable, Space: O(k)] (Contoh: Menentukan 5 pemenang undian dari laci nomor peserta yang rentangnya pasti) |
| Bead Sort (Gravity Sort) | 🔵 Classic | O(S) | Hardware model [Stable, Space: O(n²)] (Contoh: Visualisasi mekanika gravitasi manik-manik jatuh pada abakus matematika) |
| Spreadsort | 🟢 Modern | O(n·k/d) | Hybrid radix+compare [Unstable, Space: O(k/d)] (Contoh: Boost C++ library untuk mengurutkan jutaan string IP address secepat kilat) |
Adaptive / Hybrid
| Algoritma | Era | Kompleksitas | Penggunaan |
|---|---|---|---|
| Tim Sort | 🟢 Modern | O(n log n) | Exploit existing runs (Contoh: Default sort yang cerdas saat tabel Excel Anda sudah setengah urut) |
| Natural Merge Sort | 🔵 Classic | O(n log n) | Detect natural runs (Contoh: Penggabungan data log harian server yang sudah berurutan secara natural) |
| Adaptive Heap Sort | 🟢 Modern | O(n log n) | Smooth Sort variant (Contoh: Mempercepat proses pemulihan struktur Heap jika hanya sedikit elemen yang bergeser) |
| Patience Sort | 🔵 Classic | O(n log n) | Extract runs via piles (Contoh: Pencarian tren deret waktu terpanjang yang naik berturut-turut) |
| Powersort | 🔴 Research | O(n log n) | Optimal merge policy (Contoh: Pengganti Tim Sort di CPython 3.12+ untuk mengurutkan list besar dengan memori lebih optimal) |
| Peeksort | 🔴 Research | O(n log n) | Look-ahead runs (Contoh: Kandidat alternatif struktur merge tree efisien pada riset compiler terbaru) |
| Quadsort | 🟢 Modern | O(n log n) | Branchless, cache-friendly (Contoh: Pengurutan data grafis dalam memori L1 cache CPU gaming secara super efisien) |
Parallel / Distributed
| Algoritma | Era | Kompleksitas | Penggunaan |
|---|---|---|---|
| Bitonic Sort | 🔵 Classic | O(log² n) | GPU computing (Contoh: Akselerasi pengurutan jutaan titik koordinat 3D di dalam Graphic Card / GPU) |
| Odd-Even Sort | 🔵 Classic | O(n) | Parallel computing (Contoh: Sinkronisasi data di dalam desain chip semikonduktor (systolic array)) |
| Sample Sort | 🟢 Modern | O(n log n / p) | MapReduce (Contoh: Pengurutan Big Data cuaca global berukuran petabyte melintasi klaster Hadoop) |
| Merge Sort (Parallel) | 🔵 Classic | O(n/p log n) | Shared memory (Contoh: Pengurutan string genetik raksasa menggunakan framework OpenMP di server multicore) |
| Radix Sort (Parallel) | 🟢 Modern | O(nk/p) | CUDA Thrust (Contoh: CUDA GPU sort untuk memproses rendering partikel (asap/api) video game AAA) |
| Hyper Quick Sort | 🟢 Modern | O(n log n / p) | Hypercube MPI (Contoh: Pengurutan terdistribusi arsitektur memori di dalam superkomputer IBM) |
| Flashsort (Parallel) | 🟢 Modern | O(n/p) | Large-scale (Contoh: Pengurutan cepat nilai tukar mata uang kripto jutaan transaksi per detik di node terdistribusi) |
| Counting Sort (GPU) | 🟢 Modern | O(n/p + k) | CUDA parallel (Contoh: Pengurutan warna histogram gambar resolusi 8K di dalam Photoshop) |
| AMS Sort | 🔴 Research | O(n/p log p) | Bulk Synchronous (Contoh: Algoritma masa depan untuk pengurutan data satelit astronomi miliaran gigabyte) |
External / Disk-Based
| Algoritma | Era | Kompleksitas | Penggunaan |
|---|---|---|---|
| External Merge Sort | 🔵 Classic | O(n/B log(n/B)) | Database sorting (Contoh: Klausa SQL ORDER BY di PostgreSQL saat memori RAM tidak kuat menampung data) |
| Polyphase Merge Sort | 🔵 Classic | O(n log_k n) | Tape sorting (Contoh: Membaca dan mengurutkan pita rekaman magnetik bank jadul dengan jumlah drive terbatas) |
| Cascade Merge Sort | 🔵 Classic | O(n log n) | Polyphase variant (Contoh: Alternatif efisien saat jumlah drive pita (k) yang tersedia sangat banyak) |
| Replacement Selection | 🔵 Classic | O(n) I/O | Initial sorted runs (Contoh: Memasukkan rekaman transaksi toko harian ke heap memori kecil secara bertahap) |
| LoserTree Sort | 🟢 Modern | O(n log k) | k-way merge (Contoh: Penggabungan log akses web 100 server load balancer menggunakan Apache Spark) |
Hardware / Sorting Network
| Algoritma | Era | Kompleksitas | Penggunaan |
|---|---|---|---|
| Bubble Network | 🔵 Classic | O(n) depth | Simple network (Contoh: Desain logika hardware awal untuk pengurutan 8 byte sinyal radio analog) |
| Bitonic Sorting Network | 🔵 Classic | O(log² n) depth | GPU shader, FPGA (Contoh: Inti logika hardware modern pencarian nilai minimal dalam array komputasi grafis) |
| Batcher Odd-Even Network | 🔵 Classic | O(log² n) depth | Hardware merge (Contoh: Skema jaringan sirkuit multiplexer telekomunikasi digital) |
| AKS Sorting Network | 🔴 Research | O(log n) depth | Optimal theoretical (Contoh: Batas pembuktian teoretis (Ahjo-Komlos-Szemeredi) bahwa jaringan sort O(log n) itu ada walau mustahil dirakit) |
| Shell Sorting Network | 🔵 Classic | O(log² n) depth | Fixed-connection (Contoh: Pendekatan pragmatis pembuatan silikon ASIC untuk filter paket router internet) |
Research / Frontier
| Algoritma | Era | Kompleksitas | Penggunaan |
|---|---|---|---|
| Powersort | 🔴 Research | O(n log n) | Production ready (Contoh: Menggantikan Tim Sort pada bahasa pemrograman Python 3.12 sebagai mesin pengurutan bawaan list.sort()) |
| Peeksort | 🔴 Research | O(n log n) | Near-optimal merge tree (Contoh: Subyek penelitian akademis algoritma dengan deteksi pre-existing run dari dua sisi sekalian) |
| Flow Sort | 🔴 Research | O(n log n) | Flow network runs (Contoh: Memperluas deteksi run (urutan natural) menggunakan konsep aliran jaringan di riset graf) |
| Learned Sort | 🔴 Research | O(n) expected | Machine Learning model (Contoh: Meramal posisi persis baris database menggunakan model regresi linear ML sehingga komputasi sorting nyaris O(n)) |
| Cache-Oblivious Sort | 🔴 Research | O(n log n) | Funnelsort (Contoh: Pendekatan algoritmik dari Frigo dkk (1999) yang menembus batas efisiensi cache memori di semua level CPU L1/L2/L3) |
| Integer Sort (Han's) | 🔴 Research | O(n log log n) | Sub-linear comparison (Contoh: Penemuan teoritis Yijie Han (2002) menembus batas bawah O(n log n) khusus untuk data bertipe integer konstan) |
2. Searching
Array / List Search
| Algoritma | Era | Kompleksitas | Penggunaan |
|---|---|---|---|
| Linear Search | 🔵 Classic | O(n) | Data tak terurut [Space: O(1)] (Contoh: Pencarian manual data yang hilang pada log file teks mentah) |
| Binary Search | 🔵 Classic | O(log n) | Data terurut [Space: O(1)] (Contoh: Menemukan nomor kartu kredit spesifik di dalam database yang sudah di-index) |
| Interpolation Search | 🔵 Classic | O(log log n) avg | Distribusi seragam [Space: O(1)] (Contoh: Mencari nama "Zack" langsung dengan melompat ke halaman akhir buku telepon digital) |
| Exponential Search | 🔵 Classic | O(log n) | Unbounded arrays [Space: O(1)] (Contoh: Mencari sinyal anomali pertama pada stream sensor monitoring tiada akhir) |
| Fibonacci Search | 🔵 Classic | O(log n) | Tanpa division [Space: O(1)] (Contoh: Pencarian elemen pada arsitektur mikrokontroler murah yang lambat memproses operasi pembagian) |
| Jump Search | 🔵 Classic | O(√n) | Step konstan [Space: O(1)] (Contoh: Navigasi daftar lagu pemutar MP3 lawas dengan menekan tombol "Next Page") |
| Ternary Search | 🔵 Classic | O(log₃ n) | Ekstrim unimodal [Space: O(1)] (Contoh: Menemukan titik puncak pantulan maksimum gelombang radio radar) |
| Sentinel Linear Search | 🔵 Classic | O(n) | Tanpa bounds check [Space: O(1)] (Contoh: Peningkatan performa pencarian string di dalam game engine dengan memasukkan nilai dummy di akhir) |
| Binary Search (Recursive) | 🔵 Classic | O(log n) | Call stack [Space: O(log n)] (Contoh: Algoritma edukasional pencarian cepat di struktur folder rekursif) |
| Fractional Cascading | 🟢 Modern | O(log n + k) | Multi-list [Space: O(n)] (Contoh: Kueri pencarian area geografis tumpang tindih di Google Maps (Computational Geometry)) |
| Galloping Search (Exponential Merge) | 🟢 Modern | O(log k) | Hint posisi [Space: O(1)] (Contoh: Mekanisme internal Tim Sort untuk meloncat cepat melewati ratusan elemen yang nilainya seragam) |
| Meta Binary Search | 🔵 Classic | O(log n) | Bit-level [Space: O(1)] (Contoh: Ekstraksi sinyal bit kompresi secara instan tanpa perlu menghitung nilai tengah) |
| Ubiquitous Binary Search | 🔵 Classic | O(log n) | Safe template [Space: O(1)] (Contoh: Versi anti-infinite-loop yang biasa diterapkan pada low-level memory lookup OS) |
| Block Search | 🔵 Classic | O(√n) | Hybrid [Space: O(1)] (Contoh: Pencarian blok data pada sistem alokasi memori harddisk lawas (FAT32)) |
| Sublist Search | 🔵 Classic | O(m·n) | Cari sublist [Space: O(1)] (Contoh: Mendeteksi sekuens urutan DNA tertentu di dalam sampel darah) |
| Fibonacci Search on 2D | 🟢 Modern | O(log n + log m) | Matrix terurut [Space: O(1)] (Contoh: Memindai nilai kecerahan spesifik pada matriks piksel monitor LCD) |
String Search
| Algoritma | Era | Kompleksitas | Penggunaan |
|---|---|---|---|
| KMP (Knuth-Morris-Pratt) | 🔵 Classic | O(n + m) | String matching [Space: O(m)] (Contoh: Analisis stream log server web untuk mendeteksi sekuens serangan peretasan (DDoS)) |
| Boyer-Moore | 🔵 Classic | O(n/m) best | Text search [Space: O(σ + m)] (Contoh: Utilitas Command Line OS Linux seperti grep untuk mencari string di jutaan baris teks) |
| Rabin-Karp | 🔵 Classic | O(n + m) avg | Hashing [Space: O(1)] (Contoh: Software anti-plagiarisme Turnitin untuk mencocokkan kemiripan paragraf secara simultan) |
| Aho-Corasick | 🔵 Classic | O(n + m + z) | Multi-pattern [Space: O(m·σ)] (Contoh: Sistem Deteksi Intrusi Jaringan (IDS) seperti Snort untuk memblokir ribuan virus signature) |
| Z Algorithm | 🔵 Classic | O(n) | Pattern matching [Space: O(n)] (Contoh: Riset bioinformatika untuk perbandingan rantai genetik CRISPR) |
| Suffix Array | 🟢 Modern | O(n log n) build | Full-text [Space: O(n)] (Contoh: Sistem pencarian indeks data teks offline berukuran gigabyte di aplikasi ensiklopedia) |
| Boyer-Moore-Horspool | 🔵 Classic | O(n/m) avg | Simplified BM [Space: O(σ)] (Contoh: Algoritma di balik fitur CTRL+F pada text editor ringan seperti Notepad++) |
| Sunday Algorithm | 🟢 Modern | O(n/m) avg | Varian BM cepat [Space: O(σ)] (Contoh: Pemindaian pattern cepat pada engine email client untuk memfilter spam) |
| Two-Way String Matching | 🟢 Modern | O(n + m) | O(1) extra space [Space: O(1)] (Contoh: Standar industri pencarian strstr() di GNU C library yang Anda gunakan sehari-hari) |
| Bitap Algorithm (Shift-Or) | 🔵 Classic | O(n·m/w) | Bit-parallel [Space: O(m + σ)] (Contoh: Perangkat lunak agrep UNIX untuk fitur pencarian fuzzy typo-tolerant) |
| BNDM | 🟢 Modern | O(n·m/w) | Fast DAWG [Space: O(σ·m/w)] (Contoh: Ekstraksi pola berulang kecepatan ekstrem di data kompresi DNA) |
| Suffix Tree (Ukkonen's) | 🟢 Modern | O(n) build | Substring search O(m) [Space: O(n)] (Contoh: Basis sistem penyelarasan urutan genom RNA berskala nasional di lab medis) |
| Suffix Automaton (DAWG) | 🟢 Modern | O(n) build | Directed Acyclic Graph [Space: O(n)] (Contoh: Penemuan kemunculan substring berulang (LCS) pada competitive programming top level) |
| FM-Index | 🟢 Modern | O(m log σ) query | Compressed [Space: O(n log σ)] (Contoh: Inti dari genome aligner raksasa modern (BWA, Bowtie) tanpa perlu men-dekompresi memori RAM) |
| Commentz-Walter | 🔵 Classic | O(n·m) worst | Multi-pattern [Space: O(m·σ)] (Contoh: Mesin pencarian multi-keyword pada aplikasi forensik digital forensik EnCase) |
Graph / Tree Search
Pada grafis perbandingan arsitektur pencarian rute di bawah, visualisasikan bagaimana Dijkstra mengeksplorasi jalan secara radial melingkar ke segala arah tanpa petunjuk, sementara A* Search melangkah secara fokus dan cepat menuju node target menggunakan rumus heuristik $f(n) = g(n) + h(n)$:
3.1 Classic Traversal
| Algoritma | Era | Kompleksitas | Penggunaan |
|---|---|---|---|
| BFS (Breadth-First Search) | 🔵 Classic | O(V + E) | Shortest path [Space: O(V)] (Contoh: Googlebot melakukan web crawling berpindah dari satu tautan halaman ke tautan lainnya) |
| DFS (Depth-First Search) | 🔵 Classic | O(V + E) | Cycle detection [Space: O(V)] (Contoh: Menemukan adanya relasi ketergantungan berputar melingkar pada daftar paket NPM package.json) |
| A* (A-star) | 🔵 Classic | O(b^d) | Heuristic path [Space: O(b^d)] (Contoh: Navigasi utama GPS rute mobil terpendek di aplikasi Waze) |
| Dijkstra | 🔵 Classic | O((V+E) log V) | Network routing [Space: O(V)] (Contoh: Protokol routing OSPF jaringan fiber optik backbone internet global) |
| Bidirectional Search | 🔵 Classic | O(b^(d/2)) | Path planning [Space: O(b^(d/2))] (Contoh: Penentuan seberapa jauh (derajat) dua orang di LinkedIn saling mengenal) |
| IDA* (Iterative Deepening A*) | 🔵 Classic | O(b^d) | Memory constrained [Space: O(d)] (Contoh: Program AI pemecah teka-teki Rubik 3x3 yang membutuhkan batas memori kecil) |
3.2 Informed / Heuristic Search
| Algoritma | Era | Kompleksitas | Penggunaan |
|---|---|---|---|
| Greedy Best-First Search | 🔵 Classic | O(b^m) | Heuristic-only [Space: O(b^m)] (Contoh: Algoritma pencarian pac-man / hantu AI pada game arcade yang hanya melangkah ke depan) |
| Bidirectional A* | 🟢 Modern | O(b^(d/2)) | Dua arah heuristik [Space: O(b^(d/2))] (Contoh: Aplikasi KRL mencari jalur stasiun transit tercepat secara sinkron dari arah hulu dan hilir) |
| SMA* (Simplified Memory A*) | 🟢 Modern | O(b^d) | Drop worst leaf [Space: O(memory)] (Contoh: Perencanaan pergerakan robot vakum otomatis yang harus membuang peta lawasnya bila RAM penuh) |
| RBFS (Recursive Best-First) | 🔵 Classic | O(b^d) | Backtrack w/ bound [Space: O(bd)] (Contoh: Alternatif hemat memori bagi sistem AI catur untuk melacak pergerakan bidak 5 langkah ke depan) |
| Weighted A* | 🟢 Modern | O(b^d) | Faster, suboptimal [Space: O(b^d)] (Contoh: NPC game RPG yang perlu menemukan pemain secepatnya walau tidak menggunakan jalur paling efisien) |
| Theta* | 🟢 Modern | O(n log n) | Any-angle path [Space: O(n)] (Contoh: Menggambar garis tembak bebas pandang (line-of-sight) pada game strategi Starcraft II) |
| JPS (Jump Point Search) | 🟢 Modern | O(b^d) | Grid pathfinding [Space: O(n)] (Contoh: Standar emas pencarian unit karakter di map game industri modern, 10–40x lipat lebih cepat dari A* konvensional) |
3.3 Uninformed / Blind Search
| Algoritma | Era | Kompleksitas | Penggunaan |
|---|---|---|---|
| IDDFS / DFID | 🔵 Classic | O(b^d) | Iterative DFS [Space: O(d)] (Contoh: Engine pencari catur klasik (Deep Blue) saat terbentur batas waktu turnamen) |
| Uniform Cost Search (UCS) | 🔵 Classic | O(b^(1+C/ε)) | Tree search Dijkstra [Space: O(b^(1+C/ε))] (Contoh: Sistem pengaturan tarif paket logistik yang mencari kombinasi penerbangan kargo termurah) |
| Beam Search | 🟢 Modern | O(b·w·d) | Keep top-w nodes [Space: O(w·d)] (Contoh: Standar utama (decoding strategy) yang dipakai GPT, Claude, dan Gemini untuk menggenerasi teks jawaban AI) |
| Monte Carlo Tree Search (MCTS) | 🟢 Modern | O(iter) | UCT bandit [Space: O(iter)] (Contoh: Otak dibalik kehebatan AI Google AlphaGo/AlphaZero saat mengalahkan juara dunia Go) |
| Fringe Search | 🟢 Modern | O(b^d) | Hybrid IDA* + A* [Space: O(b^d)] (Contoh: Menelusuri pohon keputusan graf besar tanpa redundansi re-ekspansi berlebih) |
| D* (Dynamic A*) | 🟢 Modern | O(b^d) | Replanning dinamik [Space: O(n)] (Contoh: Navigasi tank otonom militer yang dapat merubah arah saat melihat adanya ledakan mendadak di depannya) |
| D* Lite | 🟢 Modern | O(b^d) | Simplified D* [Space: O(n)] (Contoh: Algoritma navigasi andalan kendaraan NASA Mars Rover saat menjelejahi planet Mars secara mandiri) |
Tree-Specific Search
| Algoritma | Era | Kompleksitas | Penggunaan |
|---|---|---|---|
| Binary Search Tree (BST) Search | 🔵 Classic | O(log n) avg | Dasar BST (Contoh: Manajemen hierarki direktori file OS dasar tingkat mahasiswa) |
| AVL Tree Search | 🔵 Classic | O(log n) | Strict balance (Contoh: Sistem pembacaan log kernel Linux seketika untuk pemantauan server) |
| Red-Black Tree Search | 🔵 Classic | O(log n) | Self-balancing (Contoh: Struktur bawaan Java TreeMap atau C++ std::map untuk manajemen state web aplikasi) |
| B-Tree Search | 🔵 Classic | O(log n) | Database index (Contoh: Backbone manajemen basis data SQL InnoDB (MySQL) atau PostgreSQL untuk semua perintah kueri indeks) |
| B+ Tree Search | 🔵 Classic | O(log n) | Range query efisien (Contoh: Pengembalian SELECT * FROM sales WHERE year > 2020 secara berurutan dan masif di SQL) |
| Trie Search | 🔵 Classic | O(m) — m=length | Prefix tree (Contoh: Sistem saran kata (autocomplete) yang muncul saat Anda mengetik di Google Search) |
| Skip List Search | 🟢 Modern | O(log n) avg | Probabilistic (Contoh: Engine database memori Redis (Sorted Set) penghitung klasemen ranking game leaderboard online) |
| Van Emde Boas Tree Search | 🟢 Modern | O(log log U) | Fastest integer (Contoh: Pengaturan prioritas rute data (packet routing) super kilat miliaran IP di dalam Cisco Core Router) |
Probabilistic / Approximate Search
| Algoritma | Era | Kompleksitas | Penggunaan |
|---|---|---|---|
| Bloom Filter | 🔵 Classic | O(k) query | No false negative (Contoh: Database Cassandra/Redis memangkas pembacaan disk berat dengan mengecek apakah "user_id tidak mungkin ada") |
| Cuckoo Filter | 🟢 Modern | O(1) | Support deletion (Contoh: Implementasi Bloom Filter yang lebih hemat space dan mendukung penghapusan akun, contoh pada CDN caching) |
| Count-Min Sketch | 🟢 Modern | O(k) | Frequency estimation (Contoh: Memperkirakan "Berapa kali hashtag viral #Pemilu2024 diketik" pada stream data Twitter real-time raksasa) |
| HyperLogLog | 🟢 Modern | O(1) | Approx cardinality (Contoh: Menghitung total pengunjung "Unique Views" di Google Analytics tanpa perlu menyimpan setiap ID pengguna) |
| MinHash / LSH | 🟢 Modern | O(1) approx | Jaccard similarity (Contoh: Pendeteksi berita hoaks kloning web plagiat oleh crawler index pencarian Bing) |
| SimHash | 🟢 Modern | O(d) | Near-duplicate (Contoh: Membuang website-website palsu mirip e-commerce asli di backend index crawler Google) |
| Quotient Filter | 🟢 Modern | O(1) | Cache-friendly (Contoh: Alternatif dari Bloom Filter skala besar yang digunakan pada arsitektur SSD log-structured modern) |
Database & Index Search
| Algoritma | Era | Kompleksitas | Penggunaan |
|---|---|---|---|
| Hash Table Search | 🔵 Classic | O(1) avg | O(1) lookup (Contoh: Penyimpanan tipe map / dictionary pada Python untuk pemanggilan nilai JSON web berkecepatan tinggi) |
| Linear Probing | 🔵 Classic | O(1) avg | Cache-friendly (Contoh: Pemecahan kasus konflik hash yang mengandalkan kedekatan letak L1 cache memori fisik) |
| Double Hashing | 🔵 Classic | O(1) avg | Reduce clustering (Contoh: Distribusi merata blok memori basis data agar klaster pencarian berurutan tidak menumpuk) |
| Extendible Hashing | 🟢 Modern | O(1) avg | Dynamic table (Contoh: File sistem manajemen direktori direktori data virtual pada OS modern yang ukurannya membesar dinamis) |
| Index Scan (B+ Tree Range) | 🔵 Classic | O(log n + k) | SQL scan (Contoh: Kueri data absensi bulanan 30 hari dalam format range scan di database SDM Oracle) |
| Bitmap Index Search | 🟢 Modern | O(n/64) | Column store (Contoh: Pemfilteran analitik Data Warehouse raksasa untuk memfilter gender "Pria/Wanita" secara bitwise) |
| Inverted Index Search | 🔵 Classic | O(k) | Full-text (Contoh: Teknologi utama search engine (Elasticsearch, Lucene) untuk mencari kata di jutaan artikel secara terbalik) |
| R-Tree Search | 🔵 Classic | O(log n) | Spatial query (Contoh: ST_Intersects PostGIS mencari luas area perumahan yang tumpang tindih dengan banjir) |
Semantic / AI-Powered Search
| Algoritma | Era | Kompleksitas | Penggunaan |
|---|---|---|---|
| TF-IDF Search | 🔵 Classic | O(n·d) | Relevance ranking (Contoh: Standar awal mesin pencari Yahoo untuk membobot kata yang jarang muncul namun penting) |
| BM25 (Best Match 25) | 🟢 Modern | O(n) | Improved TF-IDF (Contoh: Algoritma pembobotan ranking default di sistem Elasticsearch dan Wikipedia) |
| Dense Retrieval (DPR) | 🟢 Modern | O(d) + ANN | Neural search (Contoh: Mencari makna konteks kalimat, bukan hanya string, (misal pipeline Facebook DPR untuk sistem RAG Chatbot AI)) |
| ANN Search (HNSW) | 🔥 Tren | O(log n) approx | Hierarchical Small World (Contoh: Standar industri utama Vector Database modern (Weaviate, Qdrant, Milvus) di era Gen AI / LLM) |
| FAISS | 🔥 Tren | O(log n) approx | Billion-scale vector (Contoh: Software internal open source andalan Facebook (Meta) untuk mencocokkan miliaran wajah pengguna) |
| Hybrid Search | 🔥 Tren | O(n) | Sparse + Dense (Contoh: Elasticsearch 8.x yang menggunakan perpaduan BM25 dan Neural Vector Embedding bersamaan) |
| ColBERT | 🔴 Research | O(n·m) | Late Interaction (Contoh: Penelusuran pencarian tanya jawab medis spesifik yang memperhatikan detail per-token (RAGatouille)) |
| Learned Index | 🔴 Research | O(1) | Neural B-Tree (Contoh: Eksperimen Google untuk menggantikan B-Tree di database dengan Machine Learning berbobot nyaris ringan) |
Research / Frontier Search
| Algoritma | Era | Kompleksitas | Penggunaan |
|---|---|---|---|
| QUBO Search | 🔴 Research | O(√n) quantum | Quantum annealing (Contoh: Pencarian optimisasi rute pengiriman satelit melalui komputer D-Wave Quantum System) |
| Grover's Algorithm | 🔴 Research | O(√n) | Quantum advantage (Contoh: Basis kriptanalisis di komputer kuantum masa depan untuk membongkar tebakan pasword yang tidak berstruktur) |
| Neural A* | 🔴 Research | O(b^d) | Neural heuristic (Contoh: Navigasi robot humanoid Boston Dynamics yang mengestimasi jalur tabrakan dengan visi ML instan) |
| AlphaCode Search | 🔴 Research | O(iter) | Transformer sampling (Contoh: AI buatan DeepMind yang memindai jutaan variasi sintaks guna menemukan kode program terbaik (competitive programming)) |
| Differentiable Search Index (DSI) | 🔴 Research | O(1) | LLM index (Contoh: Melatih model LLM untuk langsung menghafal dan menghasikan Document ID tanpa harus mencari di dalam database tradisional) |
| Token-level Beam Search | 🔴 Research | O(b·w·d) | Constrained decoding (Contoh: Mesin penghasil keluaran spesifik format (misal JSON murni) dari sistem OpenAI ChatGPT untuk enterprise) |
3. Graph Algorithms
Shortest Path
| Algoritma | Era | Kompleksitas | Penggunaan |
|---|---|---|---|
| Bellman-Ford | 🔵 Classic | O(VE) | Routing protocols (BGP) |
| Floyd-Warshall | 🔵 Classic | O(V³) | Network analysis |
| Johnson's Algorithm | 🔵 Classic | O(V² log V + VE) | Sparse graphs |
| SPFA | 🟢 Modern | O(kE) | Competitive programming |
Spanning Tree
| Algoritma | Era | Kompleksitas | Penggunaan |
|---|---|---|---|
| Kruskal's | 🔵 Classic | O(E log E) | Network design |
| Prim's | 🔵 Classic | O(E log V) | Dense graph, network |
| Borůvka's | 🔵 Classic | O(E log V) | Parallel MST |
Flow & Matching
| Algoritma | Era | Kompleksitas | Penggunaan |
|---|---|---|---|
| Ford-Fulkerson | 🔵 Classic | O(Ef) | Network flow, bipartite matching |
| Edmonds-Karp | 🔵 Classic | O(VE²) | Network optimization |
| Dinic's Algorithm | 🔵 Classic | O(V²E) | Large flow networks |
| Hungarian Algorithm | 🔵 Classic | O(n³) | Task scheduling, matching |
| Hopcroft-Karp | 🔵 Classic | O(E√V) | Bipartite matching |
| Edmonds' Blossom Algorithm | 🔵 Classic | O(V²E) | Maximum matching pada graf umum |
Connectivity & Structure
| Algoritma | Era | Kompleksitas | Penggunaan |
|---|---|---|---|
| Tarjan's SCC | 🔵 Classic | O(V + E) | Compiler optimization, graph analysis |
| Kosaraju's | 🔵 Classic | O(V + E) | Social network analysis |
| Topological Sort | 🔵 Classic | O(V + E) | Build systems, task scheduling |
| Union-Find (DSU) | 🔵 Classic | O(α(n)) | Kruskal, connectivity queries |
| PageRank | 🟢 Modern | O(k·(V+E)) | Web search, citation analysis |
| HITS | 🟢 Modern | O(k·(V+E)) | Web analysis |
| Louvain Method | 🟢 Modern | O(n log n) | Social networks, clustering |
| Girvan-Newman | 🟢 Modern | O(m²n) | Community detection |
| Hierholzer's Algorithm | 🔵 Classic | O(V + E) | Menemukan sirkuit/jalur Eulerian |
| Karger's Algorithm | 🟢 Modern | O(V² log³ V) | Minimum cut berbasis probabilitas |
4. Dynamic Programming
Classic DP
| Algoritma | Era | Kompleksitas | Penggunaan |
|---|---|---|---|
| Fibonacci DP | 🔵 Classic | O(n) | Edukasi, baseline |
| Knapsack (0/1) | 🔵 Classic | O(nW) | Resource allocation, finance |
| Knapsack (Unbounded) | 🔵 Classic | O(nW) | Coin change, cutting stock |
| Longest Common Subsequence | 🔵 Classic | O(nm) | diff tool, bioinformatics |
| Longest Increasing Subsequence | 🔵 Classic | O(n log n) | Sequence analysis |
| Edit Distance (Levenshtein) | 🔵 Classic | O(nm) | Spell check, fuzzy search, NLP |
| Matrix Chain Multiplication | 🔵 Classic | O(n³) | Compiler optimization |
| Coin Change | 🔵 Classic | O(nA) | Finance, combinatorics |
| Rod Cutting | 🔵 Classic | O(n²) | Manufacturing, optimization |
| Kadane's Algorithm | 🔵 Classic | O(n) | Menemukan maximum subarray sum |
Interval & Advanced DP
| Algoritma | Era | Kompleksitas | Penggunaan |
|---|---|---|---|
| Interval DP | 🔵 Classic | O(n³) | Parsing, triangulation |
| Bitmask DP | 🔵 Classic | O(2ⁿ·n) | TSP, assignment problems |
| DP on Trees | 🔵 Classic | O(n) | Graph problems, competitive programming |
| Digit DP | 🔵 Classic | O(d·10·2) | Competitive programming, number theory |
| Broken Profile DP | 🔴 Research | O(n·m·2^m) | Tiling, grid problems |
| CYK Algorithm | 🔵 Classic | O(n³·|G|) | Parsing Context-Free Grammar |
5. Machine Learning
Classical ML
| Algoritma | Era | Kompleksitas | Penggunaan |
|---|---|---|---|
| Linear Regression | 🔵 Classic | O(n²d) | Regresi, forecasting |
| Logistic Regression | 🔵 Classic | O(nd·iter) | Klasifikasi, credit scoring |
| Naive Bayes | 🔵 Classic | O(nd) | Spam filter, NLP |
| k-NN | 🔵 Classic | O(nd) | Rekomendasi, klasifikasi |
| SVM (Support Vector Machine) | 🔵 Classic | O(n²d) | Klasifikasi teks, bioinformatics |
| Decision Tree | 🔵 Classic | O(n²d) | Interpretable ML, tabular data |
| Random Forest | 🟢 Modern | O(k·n log n) | Tabular data, feature importance |
| Gradient Boosting | 🟢 Modern | O(k·n log n) | Kaggle winner, tabular data |
| XGBoost | 🟢 Modern | O(k·n log n) | Industri, kompetisi data science |
| LightGBM | 🟢 Modern | O(k·n log n) | Large-scale tabular data |
| CatBoost | 🟢 Modern | O(k·n log n) | Categorical data |
| AdaBoost | 🔵 Classic | O(N·M) | Algoritma boosting klasik berkinerja tinggi |
Clustering
| Algoritma | Era | Kompleksitas | Penggunaan |
|---|---|---|---|
| k-Means | 🔵 Classic | O(nkd·iter) | Segmentasi, compression |
| DBSCAN | 🔵 Classic | O(n log n) | Geospatial, anomaly detection |
| Hierarchical Clustering | 🔵 Classic | O(n³) | Bioinformatics, dendrogram |
| Gaussian Mixture Models | 🔵 Classic | O(n·k·d²) | Density estimation |
| HDBSCAN | 🟢 Modern | O(n log n) | High-dimensional data |
| OPTICS | 🟢 Modern | O(n log n) | Variable density clusters |
| Isolation Forest | 🟢 Modern | O(n log n) | Deteksi anomali pada data tabular |
| Spectral Clustering | 🟢 Modern | O(n³) | Clustering grafis berbasis nilai eigen matriks laplacian |
Dimensionality Reduction
| Algoritma | Era | Kompleksitas | Penggunaan |
|---|---|---|---|
| PCA | 🔵 Classic | O(n²d) | Feature reduction, visualization |
| LDA | 🔵 Classic | O(nd²) | Classification preprocessing |
| ICA | 🔵 Classic | O(n²d) | Signal processing, fMRI |
| t-SNE | 🟢 Modern | O(n log n) | ML visualization |
| UMAP | 🟢 Modern | O(n^1.14) | Embedding visualization, preprocessing |
| Autoencoder | 🟢 Modern | O(depends) | Anomaly detection, generation |
6. Deep Learning
Architectures
| Algoritma | Era | Kompleksitas | Penggunaan |
|---|---|---|---|
| MLP / Feedforward | 🔵 Classic | O(n·d·h) | Tabular data, classification |
| CNN (Convolutional Neural Network) | 🟢 Modern | O(n·k²·c) | Computer vision |
| RNN / LSTM / GRU | 🟢 Modern | O(n·h²) | NLP, time series (pre-Transformer) |
| Transformer | 🟢 Modern | O(n²d) | NLP, CV, multimodal AI |
| Vision Transformer (ViT) | 🟢 Modern | O(n²d) | Image classification, detection |
| Graph Neural Network (GNN) | 🟢 Modern | O(E·h) | Social networks, drug discovery, fraud |
| Diffusion Models | 🔴 Research | O(T·n) | Image/audio/video generation |
| State Space Models (Mamba) | 🔴 Research | O(n) | Long-context NLP, genomics |
| Mixture of Experts (MoE) | 🔴 Research | O(n·k/E) | LLM scaling (GPT-4, Mixtral) |
| Kolmogorov-Arnold Networks (KAN) | 🔴 Research | O(n·p²) | Scientific ML, interpretability |
Training Algorithms
| Algoritma | Era | Kompleksitas | Penggunaan |
|---|---|---|---|
| Backpropagation | 🔵 Classic | O(n·d) | Semua neural network training |
| SGD (Stochastic Gradient Descent) | 🔵 Classic | O(d) | DL training baseline |
| Adam | 🟢 Modern | O(d) | Default optimizer DL |
| AdamW | 🟢 Modern | O(d) | LLM training |
| LoRA / QLoRA | 🟢 Modern | O(n·r) | LLM fine-tuning |
| RLHF | 🟢 Modern | O(n·d) | ChatGPT, Claude, Gemini |
| Lion | 🔴 Research | O(d) | Large model training |
| DPO (Direct Preference Optimization) | 🔴 Research | O(n·d) | LLM alignment |
| RMSprop | 🟢 Modern | O(d) | Optimizer adaptif untuk DL |
| AdaGrad | 🟢 Modern | O(d) | Optimizer adaptif berbasis gradien historis |
Generative Models
| Algoritma | Era | Kompleksitas | Penggunaan |
|---|---|---|---|
| GAN (Generative Adversarial Network) | 🟢 Modern | O(n·d) | Image synthesis, deepfake |
| VAE (Variational Autoencoder) | 🟢 Modern | O(n·d) | Generation, representation learning |
| Flow Models (Normalizing Flows) | 🟢 Modern | O(n·d) | Audio generation, density estimation |
| Score Matching | 🔴 Research | O(n·T) | Generative modeling |
| Consistency Models | 🔴 Research | O(n) | Fast image generation |
| NeRF | 🔴 Research | O(varies) | Rekonstruksi 3D scene menggunakan neural network |
| 3D Gaussian Splatting | 🔴 Research | O(N) | Rendering/rekonstruksi 3D real-time |
7. Cryptography
Symmetric Encryption
| Algoritma | Era | Kompleksitas | Penggunaan |
|---|---|---|---|
| AES | 🟢 Modern | O(n) | TLS, file encryption, disk encryption |
| DES / 3DES | 🔵 Classic | O(n) | Legacy systems (deprecated) |
| ChaCha20 | 🟢 Modern | O(n) | TLS 1.3, mobile |
| Blowfish / Twofish | 🟢 Modern | O(n) | Password hashing (Bcrypt) |
| Bcrypt / Scrypt | 🟢 Modern | O(work factor) | Hashing password dengan ketahanan brute-force tinggi |
Asymmetric / Public Key
| Algoritma | Era | Kompleksitas | Penggunaan |
|---|---|---|---|
| RSA | 🔵 Classic | O(k³) | TLS, digital signatures, key exchange |
| Diffie-Hellman | 🔵 Classic | O(k²) | TLS, SSH key exchange |
| Elliptic Curve (ECC) | 🟢 Modern | O(k²) | Bitcoin, TLS, modern cryptography |
| EdDSA (Ed25519) | 🟢 Modern | O(k²) | SSH, Signal protocol |
| ElGamal | 🔵 Classic | O(k²) | GPG encryption |
| DSA | 🔵 Classic | O(k³) | Standar federal AS terdahulu untuk tanda tangan digital |
Hash Functions
| Algoritma | Era | Kompleksitas | Penggunaan |
|---|---|---|---|
| MD5 | 🔵 Classic | O(n) | Checksum saja (bukan security) |
| SHA-1 | 🔵 Classic | O(n) | Legacy systems (deprecated) |
| SHA-256 / SHA-3 | 🟢 Modern | O(n) | TLS, Bitcoin, digital signatures |
| BLAKE2 | 🟢 Modern | O(n) | File integrity, general hashing |
| BLAKE3 | 🟢 Modern | O(n) | High-performance hashing |
| Argon2 | 🟢 Modern | O(n·m) | Password storage |
Post-Quantum Cryptography
Ilustrasi alur migrasi di bawah menggambarkan ancaman komputer kuantum yang mampu meretakan algoritma asimetris klasik (RSA & ECC) menggunakan Algoritma Shor, serta peta pertahanan tangguh berbasis kisi matematika (Lattice-based) seperti CRYSTALS-Kyber dan CRYSTALS-Dilithium:
| Algoritma | Era | Kompleksitas | Penggunaan |
|---|---|---|---|
| CRYSTALS-Kyber | 🔴 Research | O(n log n) | Post-quantum key exchange (NIST standard) |
| CRYSTALS-Dilithium | 🔴 Research | O(n log n) | Post-quantum signatures (NIST standard) |
| NTRU | 🔴 Research | O(n log n) | Post-quantum encryption |
| SPHINCS+ | 🔴 Research | O(log² n) | Post-quantum signatures |
| McEliece Cryptosystem | 🔵 Classic | O(n²) | Skema kunci publik berbasis kode koreksi kesalahan |
8. Optimization
Gradient-Based
| Algoritma | Era | Kompleksitas | Penggunaan |
|---|---|---|---|
| Gradient Descent | 🔵 Classic | O(d·iter) | ML training, baseline (Contoh: Pelatihan awal regresi linear untuk prediksi harga saham) |
| Newton's Method | 🔵 Classic | O(d³·iter) | Logistic regression, SciPy (Contoh: Konvergensi cepat untuk pemodelan risiko kredit bank) |
| L-BFGS | 🔵 Classic | O(d·iter) | ML, scientific computing (Contoh: Estimasi parameter geofisika di industri minyak bumi) |
| Conjugate Gradient | 🔵 Classic | O(n√κ) | FEM, large-scale linear systems (Contoh: Simulasi tekanan struktural sayap pesawat terbang) |
| Nelder-Mead Method | 🔵 Classic | O(iter) | Optimasi multidimensi tanpa gradien (Contoh: Kalibrasi instrumen mesin pabrik yang tidak memiliki turunan analitik) |
| Stochastic Gradient Descent (SGD) | 🔵 Classic | O(d) per step | Deep learning training (Contoh: Pembaruan bobot model klasifikasi gambar satu per satu dari stream data real-time) |
| Mini-batch SGD | 🟢 Modern | O(b·d) per step | Neural network training standard (Contoh: Pelatihan model deteksi objek YOLO menggunakan GPU batching) |
| Momentum (SGD + Momentum) | 🟢 Modern | O(d) | Percepat konvergensi SGD (Contoh: Menghindari terjebak di saddle point saat melatih neural network pengenal wajah) |
| AdaGrad | 🟢 Modern | O(d) | Sparse data, NLP (Contoh: Optimasi model rekomendasi e-commerce yang datanya sangat jarang/sparse) |
| RMSProp | 🟢 Modern | O(d) | RNN training (Contoh: Menstabilkan pelatihan model prediksi suhu cuaca deret waktu) |
| Adam (Adaptive Moment Estimation) | 🟢 Modern | O(d) | Default optimizer deep learning (Contoh: Standard emas untuk pelatihan model klasifikasi sentimen teks di NLP) |
| AdamW | 🟢 Modern | O(d) | LLM training (Contoh: Pelatihan Large Language Models seperti GPT dengan regulasi bobot/weight decay yang benar) |
| Nesterov Accelerated Gradient (NAG) | 🔵 Classic | O(d) | Lebih cepat dari momentum (Contoh: Prediksi lookahead untuk koreksi trayektori rudal kendali) |
| BFGS | 🔵 Classic | O(d²·iter) | Quasi-Newton (Contoh: Estimasi matriks Hessian penuh untuk pemodelan fisika kuantum molekuler) |
Metaheuristic
| Algoritma | Era | Kompleksitas | Penggunaan |
|---|---|---|---|
| Simulated Annealing | 🔵 Classic | O(iter) | TSP, circuit design (Contoh: Mencari desain tata letak paling efisien untuk sirkuit motherboard) |
| Genetic Algorithm (GA) | 🔵 Classic | O(gen·pop) | Scheduling, parameter tuning (Contoh: Pembuatan jadwal kelas otomatis untuk ribuan mahasiswa di universitas) |
| Particle Swarm Optimization (PSO) | 🟢 Modern | O(gen·pop) | Continuous optimization (Contoh: Kalibrasi parameter kontrol motor servo pada lengan robot industri) |
| Differential Evolution (DE) | 🟢 Modern | O(gen·pop) | Global optimization (Contoh: Optimasi desain bentuk lambung kapal laut agar minim hambatan air) |
| Ant Colony Optimization (ACO) | 🟢 Modern | O(iter·n²) | Routing, scheduling (Contoh: Pencarian rute serat optik bawah tanah yang paling murah) |
| CMA-ES | 🟢 Modern | O(d²·iter) | Robotics, neuroevolution (Contoh: Melatih agen robot virtual agar bisa berjalan seimbang di simulasi physics) |
| Bayesian Optimization | 🟢 Modern | O(n³) | Hyperparameter tuning (Contoh: Pencarian nilai learning rate terbaik untuk algoritma ML yang lambat dilatih) |
| Tabu Search | 🔵 Classic | O(iter) | Local search dengan memori (Contoh: Perencanaan shift kerja perawat rumah sakit tanpa melanggar aturan lembur) |
| Hill Climbing | 🔵 Classic | O(iter) | Optimasi heuristik lokal sederhana (Contoh: Optimasi penjadwalan CPU dasar pada sistem embedded) |
| Harmony Search | 🟢 Modern | O(iter·HMS) | Structural design (Contoh: Optimasi desain struktur baja penahan gempa pada gedung pencakar langit) |
| Firefly Algorithm | 🟢 Modern | O(iter·n²) | Multimodal optimization (Contoh: Pemilihan fitur krusial dalam data microarray kanker medis) |
| Grey Wolf Optimizer (GWO) | 🟢 Modern | O(iter·n) | Engineering design (Contoh: Optimalisasi daya pada sistem pembangkit listrik tenaga surya / MPPT) |
| Whale Optimization Algorithm (WOA) | 🟢 Modern | O(iter·n) | Structural optimization (Contoh: Penetapan lokasi ideal untuk sumur ekstraksi air tanah) |
| Bat Algorithm | 🟢 Modern | O(iter·n) | Continuous, combinatorial (Contoh: Sinkronisasi waktu pada jaringan sensor nirkabel IoT) |
| Artificial Bee Colony (ABC) | 🟢 Modern | O(iter·n) | Function optimization (Contoh: Menyeimbangkan beban kerja pada server komputasi cloud) |
| Cuckoo Search | 🟢 Modern | O(iter·n) | Engineering optimization (Contoh: Optimasi rasio roda gigi pada desain transmisi otomotif) |
| Evolutionary Strategy (ES) | 🔵 Classic | O(gen·pop) | Continuous optimization (Contoh: Adaptasi parameter kontrol pada sistem stabilisator pesawat terbang) |
| Genetic Programming (GP) | 🔵 Classic | O(gen·pop) | Symbolic regression (Contoh: Menghasilkan rumus matematika penemuan obat otomatis dari data eksperimen) |
| Evolution Strategy (1+1) ES | 🔵 Classic | O(iter) | Simple self-adaptive (Contoh: Tuning cepat untuk filter antena radar militer) |
| Random Search | 🔵 Classic | O(iter) | Baseline (Contoh: Ekplorasi grid pencarian korban hilang di perairan luas) |
| Iterated Local Search (ILS) | 🔵 Classic | O(iter) | Kombinasi perturbation (Contoh: Memperbaiki rute bus kota dengan menghindari rute macet lokal) |
| Variable Neighborhood Search (VNS) | 🟢 Modern | O(iter·n) | Combinatorial, VRP (Contoh: Rute truk sampah yang berubah-ubah jika ada jalan yang ditutup) |
Linear & Integer Programming
| Algoritma | Era | Kompleksitas | Penggunaan |
|---|---|---|---|
| Simplex Method | 🔵 Classic | O(2ⁿ) worst | LP, operations research (Contoh: Memaksimalkan profit pabrik pembuat dua jenis barang dengan kendala mesin) |
| Interior Point Methods | 🟢 Modern | O(n³·L) | Large-scale LP, SDP (Contoh: Alokasi portofolio investasi saham untuk jutaan nasabah perbankan) |
| Branch and Bound | 🔵 Classic | O(2ⁿ) worst | ILP, exact solution (Contoh: Perencanaan optimal pembagian wilayah sales representatif agar tidak tumpang tindih) |
| Cutting Plane | 🔵 Classic | O(poly) | ILP, combinatorial optimization (Contoh: Optimasi pemotongan plat besi di pabrik otomotif untuk meminimalisir sisa) |
| Column Generation | 🟢 Modern | O(poly) | Airline scheduling (Contoh: Penjadwalan rotasi awak kabin maskapai komersial) |
| Branch and Cut | 🟢 Modern | O(2ⁿ) worst | ILP (Contoh: Memecahkan masalah penugasan mesin pabrik berskala raksasa) |
| Branch and Price | 🟢 Modern | O(2ⁿ) worst | ILP + Column Generation (Contoh: Optimalisasi penjadwalan kereta api komuter jabodetabek) |
| Gomory Cut | 🔵 Classic | O(poly) | Integer cut dari LP (Contoh: Analisis jumlah armada truk tangki bensin utuh (integer) tanpa desimal) |
| Benders Decomposition | 🔵 Classic | O(poly·iter) | Large-scale MIP (Contoh: Perencanaan lokasi pembangunan gudang baru nasional perusahaan logistik) |
| Lagrangian Relaxation | 🔵 Classic | O(iter·n) | Relax constraint (Contoh: Menyederhanakan kompleksitas jadwal liga sepakbola profesional) |
Stochastic & Probabilistic Optimization
| Algoritma | Era | Kompleksitas | Penggunaan |
|---|---|---|---|
| Stochastic Approximation (Robbins-Monro) | 🔵 Classic | O(iter) | Root finding stochastic (Contoh: Uji klinis adaptif untuk menentukan dosis obat baru) |
| SPSA (Simultaneous Perturbation SA) | 🟢 Modern | O(iter) | Gradient-free stochastic (Contoh: Tuning parameter pada eksperimen quantum physics atau simulasi aerodinamika) |
| Cross-Entropy Method (CEM) | 🟢 Modern | O(iter·n) | Rare event simulation (Contoh: Estimasi probabilitas kegagalan sistem kelistrikan pada reaktor nuklir) |
| Evolution Strategy with Importance Mixing | 🟢 Modern | O(iter·pop) | Sample-efficient ES (Contoh: Melatih karakter animasi game untuk berjalan realistis) |
| Natural Evolution Strategy (NES) | 🟢 Modern | O(iter·pop·d) | Information-geometric ES (Contoh: Kontrol robot bipedal untuk berjalan di medan berbatu) |
| Monte Carlo Optimization | 🔵 Classic | O(iter·n) | Optimization via random sampling (Contoh: Evaluasi kelayakan nilai akuisisi perusahaan di masa depan) |
| Markov Chain Monte Carlo (MCMC) | 🔵 Classic | O(iter) | Bayesian inference (Contoh: Prediksi penyebaran infeksi wabah dari data yang tidak lengkap) |
| Simulated Tempering | 🟢 Modern | O(iter) | Ekstensi SA (Contoh: Melarutkan struktur protein kompleks ke dalam bentuk paling stabil energinya) |
Multi-Objective Optimization
| Algoritma | Era | Kompleksitas | Penggunaan |
|---|---|---|---|
| NSGA-II (Non-dominated Sorting GA II) | 🟢 Modern | O(M·N²) | Engineering design (Contoh: Standar industri mendesain mesin mobil agar cepat sekaligus irit bahan bakar) |
| NSGA-III | 🟢 Modern | O(M·N²) | Many-objective (>3 obj) (Contoh: Perencanaan kota yang mempertimbangkan emisi, biaya, tata ruang, dan ruang hijau sekaligus) |
| MOEA/D (Decomposition-based) | 🟢 Modern | O(iter·N·T) | Decompose jadi subproblem skalar (Contoh: Optimalisasi pembagian spektrum frekuensi radio 5G) |
| SPEA2 (Strength Pareto EA 2) | 🟢 Modern | O(N³) | Pareto-based selection (Contoh: Penjadwalan portofolio investasi berisiko tinggi dan berisiko rendah) |
| MOPSO (Multi-Objective PSO) | 🟢 Modern | O(iter·n) | PSO untuk multi-objective (Contoh: Pengaturan turbin angin untuk daya maksimal dengan polusi suara minimal) |
| Weighted Sum Method | 🔵 Classic | O(iter) | Skalarisasi sederhana (Contoh: Pembobotan scoring credit nasabah dari gaji vs tanggungan) |
| ε-Constraint Method | 🔵 Classic | O(iter) | Satu objective + constraint (Contoh: Minimalisasi biaya proyek IT asalkan selesai dalam 3 bulan) |
| Hypervolume Indicator | 🟢 Modern | O(N·d^(d/2)) | Ukur kualitas Pareto front (Contoh: Metrik pembanding dua mesin pencari multi-objective di e-commerce) |
Combinatorial Optimization
| Algoritma | Era | Kompleksitas | Penggunaan |
|---|---|---|---|
| Dynamic Programming Optimization | 🔵 Classic | Varies | Sequence alignment (Contoh: Solusi pasti untuk optimalisasi pemuatan barang ke pesawat kargo) |
| Greedy Algorithms | 🔵 Classic | O(n log n) | Kruskal, Prim, Huffman (Contoh: Algoritma serakah pemilihan jaringan pemasangan kabel serat optik antar kota) |
| Christofides Algorithm | 🔵 Classic | O(n³) | 1.5-approx TSP (Contoh: Estimasi pengiriman paket pos darat skala nasional dengan garansi error) |
| Lin-Kernighan Heuristic (LK) | 🔵 Classic | O(n²·k) | TSP high-quality heuristic (Contoh: Standar industri penyelesaian masalah routing microchip di PCB) |
| 2-opt / 3-opt | 🔵 Classic | O(n²) / O(n³) | TSP local improvement (Contoh: Mengurai jalur silang yang tumpang tindih pada rute kurir) |
| Or-Opt | 🟢 Modern | O(n²) | Relocate segments (Contoh: Perubahan rute mendadak saat truk ekspedisi sedang di jalan) |
| Large Neighborhood Search (LNS) | 🟢 Modern | O(iter·n) | Destroy + repair (Contoh: Sistem perombakan ulang jadwal harian masinis jika ada kereta rusak) |
| Set Covering / Partitioning | 🔵 Classic | NP-hard | Crew scheduling (Contoh: Penentuan titik stasiun pemadam kebakaran agar seluruh kota tercover) |
| Knapsack Algorithms | 🔵 Classic | O(nW) DP | Resource allocation (Contoh: Memilih video iklan mana yang paling menguntungkan untuk ditayangkan dalam 30 detik jeda TV) |
Convex Optimization
| Algoritma | Era | Kompleksitas | Penggunaan |
|---|---|---|---|
| Gradient Projection Method | 🔵 Classic | O(d·iter) | Constrained convex (Contoh: Pelatihan Support Vector Machine (SVM) dengan pembatas hard-margin) |
| Proximal Gradient Method | 🟢 Modern | O(d·iter) | L1-regularized (Contoh: Kompresi model sparse Machine Learning untuk deteksi gambar di HP) |
| ADMM (Alternating Direction Method) | 🟢 Modern | O(d·iter) | Distributed optimization (Contoh: Tulang punggung Federated Learning (melatih AI di ratusan HP tanpa mengirim foto pribadi)) |
| CVXPY / Disciplined Convex Programming | 🟢 Modern | O(poly) | Convex problem modeling (Contoh: Software pemodelan optimasi bauran energi listrik terbarukan dan batubara) |
| Ellipsoid Method | 🔵 Classic | O(n⁴·L) | Theoretically polynomial LP (Contoh: Analisis batas konveks teoritis jaringan komunikasi nirkabel) |
| Frank-Wolfe Algorithm | 🔵 Classic | O(1/iter) | Constrained convex (Contoh: Rekonstruksi sinyal medis dari alat pacu jantung) |
| Mirror Descent | 🟢 Modern | O(d·iter) | Online learning (Contoh: Model click-through rate (CTR) iklan Google yang belajar terus dari data streaming baru) |
Continuous Global Optimization
| Algoritma | Era | Kompleksitas | Penggunaan |
|---|---|---|---|
| DIRECT (Dividing Rectangles) | 🟢 Modern | O(iter·n) | Derivative-free global (Contoh: Kalibrasi parameter hidrologi pada simulasi banjir sungai) |
| Basin Hopping | 🟢 Modern | O(iter) | Global + local (Contoh: Prediksi 3D pelipatan (folding) ikatan molekul obat farmasi) |
| Multistart Gradient Descent | 🔵 Classic | O(starts·iter) | Random restart (Contoh: Mencari celah keamanan sistem dengan menembak berbagai koordinat masuk yang acak) |
| Lipschitz Optimization (LIPO) | 🔴 Research | O(n) | Global tanpa gradient (Contoh: Optimasi tuning hyperparameter ML untuk kasus budget server terbatas) |
| Surrogate-Based Optimization | 🟢 Modern | O(n³) | Black-box (Contoh: Optimasi desain bentuk sayap Formula 1 menggunakan simulasi fluida (CFD) yang mahal dihitung) |
| Interval Arithmetic Optimization | 🔴 Research | O(2ⁿ) | Guaranteed global (Contoh: Pembuktian keselamatan absolut pada kode perangkat lunak pengontrol autopilot roket SpaceX) |
Quantum & Emerging Optimization
| Algoritma | Era | Kompleksitas | Penggunaan |
|---|---|---|---|
| QAOA (Quantum Approximate Optimization) | 🔴 Research | O(p·n) | Combinatorial opt di quantum (Contoh: Mencari rute optimal kargo pelayaran lintas benua di komputer IBM Quantum) |
| Quantum Annealing | 🔴 Research | O(T) | D-Wave; QUBO (Contoh: Penempatan gate penerbangan maskapai di bandara raksasa menggunakan komputer kuantum D-Wave) |
| VQE (Variational Quantum Eigensolver) | 🔴 Research | O(poly) | Chemistry, materials science (Contoh: Simulasi baterai lithium jenis baru tanpa harus membuat baterainya secara fisik di lab) |
| Differentiable Programming | 🔴 Research | O(d) | End-to-end gradient (Contoh: Penggunaan JAX/PyTorch untuk mengoptimasi desain optik lensa kamera HP secara gradien terbalik) |
| Neural Architecture Search (NAS) | 🔴 Research | O(arch·epoch) | Automated ML architecture (Contoh: AI milik Google yang merancang model AI baru (AutoML) tanpa campur tangan manusia) |
| Zeroth-Order Optimization | 🔴 Research | O(d·iter) | Gradient-free (Contoh: Melakukan serangan adverserial (tipuan gambar) terhadap sistem pengenal wajah secara diam-diam) |
9. Compression & Coding
Lossless
| Algoritma | Era | Kompleksitas | Penggunaan |
|---|---|---|---|
| Huffman Coding | 🔵 Classic | O(n log n) | ZIP, JPEG, PNG |
| Arithmetic Coding | 🔵 Classic | O(n) | HEVC, modern compressors |
| LZ77 / LZ78 | 🔵 Classic | O(n) | ZIP, gzip, deflate |
| LZW | 🔵 Classic | O(n) | GIF, TIFF, PDF |
| BWT (Burrows-Wheeler Transform) | 🔵 Classic | O(n log n) | bzip2, SAM format |
| Deflate | 🟢 Modern | O(n) | PNG, gzip, HTTP compression |
| Brotli | 🟢 Modern | O(n) | Web compression (HTTP) |
| Zstandard (zstd) | 🟢 Modern | O(n) | Linux kernel, databases |
| ANS / rANS | 🟢 Modern | O(n) | zstd, HEVC, JPEG XL |
| LZMA | 🟢 Modern | O(n) | Kompresi rasio tinggi pada format 7z/xz |
| Run-Length Encoding (RLE) | 🔵 Classic | O(n) | Kompresi lossless paling sederhana berbasis sekuens berulang |
Lossy
| Algoritma | Era | Kompleksitas | Penggunaan |
|---|---|---|---|
| DCT (JPEG) | 🔵 Classic | O(n log n) | JPEG, MP3, video codecs |
| Wavelet (JPEG 2000) | 🟢 Modern | O(n) | Medical imaging, JPEG 2000 |
| VQ (Vector Quantization) | 🔵 Classic | O(n·k) | Speech coding, image |
| Neural Image Compression | 🔴 Research | O(n·d) | Next-gen image compression |
Error Correction
| Algoritma | Era | Kompleksitas | Penggunaan |
|---|---|---|---|
| Hamming Code | 🔵 Classic | O(n) | RAM ECC, legacy telecom |
| Reed-Solomon | 🔵 Classic | O(n log n) | QR code, CD/DVD, storage |
| Turbo Codes | 🟢 Modern | O(n) | 3G/4G LTE, deep space |
| LDPC | 🟢 Modern | O(n) | 5G, WiFi 802.11, deep space |
| Polar Codes | 🔴 Research | O(n log n) | 5G NR control channel |
| BCH Code | 🔵 Classic | O(n log n) | Kode koreksi error aljabar linier |
10. Number Theory & Math
Prime & Factorization
| Algoritma | Era | Kompleksitas | Penggunaan |
|---|---|---|---|
| Sieve of Eratosthenes | 🔵 Classic | O(n log log n) | Number theory, competitive programming |
| Sieve of Atkin | 🔵 Classic | O(n / log log n) | Large prime generation |
| Miller-Rabin | 🔵 Classic | O(k log²n) | RSA key generation |
| Pollard's Rho | 🔵 Classic | O(n^¼) | Integer factorization |
| AKS Primality Test | 🟢 Modern | O(log^6 n) | Theoretical CS, verification |
| GNFS (General Number Field Sieve) | 🟢 Modern | O(sub-exp) | Breaking RSA, cryptanalysis |
GCD & Modular Arithmetic
| Algoritma | Era | Kompleksitas | Penggunaan |
|---|---|---|---|
| Euclidean Algorithm | 🔵 Classic | O(log min) | Number theory, fractions |
| Extended Euclidean | 🔵 Classic | O(log min) | RSA, modular arithmetic |
| Fast Modular Exponentiation | 🔵 Classic | O(log e) | RSA, primality testing |
| CRT (Chinese Remainder Theorem) | 🔵 Classic | O(n²) | RSA optimization, number theory |
| Binary GCD | 🔵 Classic | O(log² n) | FPB cepat menggunakan operasi bitwise |
| Montgomery Modular Multiplication | 🔵 Classic | O(log² n) | Perkalian modular cepat untuk kriptografi |
Transform & FFT
| Algoritma | Era | Kompleksitas | Penggunaan |
|---|---|---|---|
| FFT (Cooley-Tukey) | 🔵 Classic | O(n log n) | Signal processing, polynomial multiplication |
| NTT (Number Theoretic Transform) | 🔵 Classic | O(n log n) | Competitive programming, crypto |
| Walsh-Hadamard Transform | 🔵 Classic | O(n log n) | Coding theory, competitive programming |
| Schönhage-Strassen | 🟢 Modern | O(n log n log log n) | Big number libraries (GMP) |
| Harvey-Hoeven | 🔴 Research | O(n log n) | Theoretical breakthrough 2019 |
| Strassen's Algorithm | 🔵 Classic | O(n^2.807) | Perkalian matriks cepat sub-kubik |
11. Computational Geometry
Convex Hull
| Algoritma | Era | Kompleksitas | Penggunaan |
|---|---|---|---|
| Graham Scan | 🔵 Classic | O(n log n) | GIS, computer graphics (Contoh: Menentukan batas terluar area jangkauan sinyal BTS seluler) |
| Jarvis March (Gift Wrapping) | 🔵 Classic | O(nh) | Output-sensitive, small h (Contoh: Membungkus sekumpulan koordinat GPS untuk mendefinisikan zona geo-fence) |
| Chan's Algorithm | 🔵 Classic | O(n log h) | Optimal convex hull (Contoh: Perhitungan batas teritori pengiriman logistik secara real-time) |
| QuickHull | 🔵 Classic | O(n log n) avg | GPU, point cloud (Contoh: Deteksi area tabrakan (collision detection) pada simulasi fisika game) |
| Andrew's Monotone Chain | 🔵 Classic | O(n log n) | Varian Graham Scan yang lebih praktis untuk Convex Hull (Contoh: Menghasilkan poligon convex dari data titik sebaran wabah penyakit) |
Proximity & Intersection
| Algoritma | Era | Kompleksitas | Penggunaan |
|---|---|---|---|
| Closest Pair of Points | 🔵 Classic | O(n log n) | GIS, collision detection |
| Line Sweep (Shamos-Hoey / Bentley-Ottmann) | 🔵 Classic | O(n log n) | CAD, GIS |
| Voronoi Diagram (Fortune's) | 🔵 Classic | O(n log n) | GIS, network planning |
| Delaunay Triangulation | 🔵 Classic | O(n log n) | Mesh generation, FEM |
| KD-Tree / R-Tree | 🔵 Classic | O(log n) | Databases, GIS, ML (k-NN) |
| Bowyer-Watson Algorithm | 🔵 Classic | O(n log n) avg | Pembentukan Delaunay Triangulation (Contoh: Generasi terrain acak pada video game dunia terbuka) |
Polygon Operations
| Algoritma | Era | Kompleksitas | Penggunaan |
|---|---|---|---|
| Point in Polygon | 🔵 Classic | O(n) | GIS, game collision |
| Sutherland-Hodgman Clipping | 🔵 Classic | O(n) | Computer graphics, GIS (Contoh: Memotong rendering objek yang keluar dari layar monitor (viewport)) |
| Boolean Polygon Operations | 🟢 Modern | O(n log n) | CAD, GIS, vector graphics |
| Cohen-Sutherland | 🔵 Classic | O(1) avg | Pemotongan garis 2D pada viewport grafika komputer |
Convex Hull Algorithms
| Algoritma | Era | Kompleksitas | Penggunaan |
|---|---|---|---|
| Graham Scan | 🔵 Classic | O(n log n) | Convex hull 2D via polar angle sort + CCW test (Contoh: Menentukan batas terluar area jangkauan sinyal BTS seluler) [Graham (1972)] |
| Jarvis March (Gift Wrapping) | 🔵 Classic | O(nh) | Output-sensitive; h = hull points (Contoh: Membungkus sekumpulan koordinat GPS untuk mendefinisikan zona geo-fence) [Jarvis (1973)] |
| Chan's Algorithm | 🔵 Classic | O(n log h) | Optimal output-sensitive; combine Graham + Jarvis (Contoh: Perhitungan batas teritori pengiriman logistik secara real-time) [Chan (1996)] |
| QuickHull | 🔵 Classic | O(n log n) avg, O(n²) worst | Divide & conquer; seperti Quicksort untuk hull (Contoh: Deteksi area tabrakan (collision detection) pada simulasi fisika game) [Barber et al. (1996)] |
| Andrew's Monotone Chain | 🔵 Classic | O(n log n) | Sort + build upper + lower hull; praktis dan clean (Contoh: Menghasilkan poligon convex dari data titik sebaran wabah penyakit) [Andrew (1979)] |
| Kirkpatrick-Seidel | 🔵 Classic | O(n log h) | Pertama kali optimal output-sensitive (Contoh: Optimasi rendering area pada aplikasi pemetaan digital) [Kirkpatrick & Seidel (1986)] |
| Dynamic Convex Hull | 🟢 Modern | O(log²n) amortized | Insert/delete points dan maintain hull (Contoh: Melacak pergerakan batas formasi drone secara dinamis) [Brodal & Jacob (2002)] |
| Convex Hull 3D (Beneath-Beyond) | 🔵 Classic | O(n log n) | Hull 3D via incremental insertion (Contoh: Pembuatan bounding volume untuk objek 3D di CAD) [Beneath-Beyond method] |
| Convex Hull 3D (Randomized) | 🟢 Modern | O(n log n) expected | Randomized incremental 3D hull (Contoh: Analisis volume awan titik (point cloud) dari scan LiDAR) [Clarkson & Shor (1989)] |
| Gift Wrapping 3D | 🔵 Classic | O(nF) | Output-sensitive 3D; F = faces (Contoh: Ekstraksi selubung terluar model 3D arsitektur bangunan) [3D variant Jarvis March] |
| Kinetic Convex Hull | 🔴 Research | O(n log n) per event | Hull untuk moving points (Contoh: Sistem anti-tabrakan kawanan robot otonom) [Kinetic Data Structures] |
| Approximate Convex Hull | 🟢 Modern | O(n/ε²) | ε-approximation untuk big data (Contoh: Pemrosesan cepat batas wilayah dari jutaan data sensor IoT) [Agarwal & Yu (2007)] |
Intersection & Proximity Algorithms
Line & Segment Intersection
| Algoritma | Era | Kompleksitas | Penggunaan |
|---|---|---|---|
| Brute Force Segment Intersection | 🔵 Classic | O(n²) | Check semua pasang segmen (Contoh: Deteksi persimpangan jalan pada peta skala kecil) [Baseline] |
| Shamos-Hoey Algorithm | 🔵 Classic | O(n log n) | Deteksi apakah ada interseksi (binary); sweep line (Contoh: Validasi integritas desain sirkuit cetak (PCB)) [Shamos & Hoey (1976)] |
| Bentley-Ottmann Algorithm | 🔵 Classic | O((n+k) log n) | Semua k intersection; sweep line + event queue (Contoh: Menemukan semua titik potong kabel listrik dalam desain tata kota) [Bentley & Ottmann (1979)] |
| Randomized Segment Intersection | 🟢 Modern | O(n log n + k) expected | Randomized sweep; simpler implementation (Contoh: Render grafis garis-garis pada aplikasi ilustrasi vektor) [Mulmuley (1988)] |
| Segment Tree Intersection | 🔵 Classic | O(log n + k) query | Range intersection query (Contoh: Analisis tumpang tindih waktu tayang iklan) [Segment tree variant] |
| Line Arrangement | 🔵 Classic | O(n²) | Planar subdivision dari n lines (Contoh: Pemotongan area pada desain tata letak arsitektur) [Edelsbrunner (1987)] |
| Ray-Segment Intersection | 🔵 Classic | O(log n) | Point-in-polygon via ray casting (Contoh: Mekanik line-of-sight (pandangan) karakter dalam video game) [Standard CG] |
| Circle-Circle Intersection | 🔵 Classic | O(1) | Interseksi dua lingkaran (Contoh: Mencari titik pertemuan cakupan dua radar pemindai) [Analytic geometry] |
| Polygon-Polygon Intersection | 🟢 Modern | O(n log n) | Boolean ops pada polygon (Contoh: Menganalisis area tumpang tindih antara zona rawan banjir dan permukiman) [Sutherland-Hodgman variant] |
Closest Pair & Proximity
| Algoritma | Era | Kompleksitas | Penggunaan |
|---|---|---|---|
| Closest Pair (Divide & Conquer) | 🔵 Classic | O(n log n) | Pasangan titik terdekat di 2D (Contoh: Deteksi jarak terdekat antar pesawat di radar ATC) [Shamos (1975)] |
| Closest Pair (Randomized) | 🟢 Modern | O(n) expected | Randomized hashing approach (Contoh: Menemukan dua menara pemancar seluler yang posisinya terlalu berdekatan) [Rabin (1976)] |
| All Nearest Neighbors | 🔵 Classic | O(n log n) | Setiap titik → neighbor terdekat (Contoh: Pemetaan pelanggan terdekat untuk setiap titik toko retail) [Bentley & Shamos (1976)] |
| Bichromatic Closest Pair | 🟢 Modern | O(n log n) | Closest pair antara dua set titik (Contoh: Mencocokkan taksi yang menganggur dengan penumpang terdekat) [Fortune & Hopcroft] |
| k-Nearest Neighbors (Exact) | 🔵 Classic | O(n log n) preprocessing | k tetangga terdekat untuk setiap titik (Contoh: Sistem rekomendasi restoran terdekat dari lokasi pengguna) [KD-Tree based] |
| Approximate Nearest Neighbor (ANN) | 🟢 Modern | O(log n) | ε-approximate NN; jauh lebih cepat (Contoh: Pencarian gambar serupa (visual search) pada e-commerce) [Arya et al. (1998), FLANN] |
| HNSW (Hierarchical NSW) | 🔥 Tren | O(log n) | Graph-based ANN; state-of-art untuk high-dim (Contoh: Vector database pencarian konteks semantic pada LLM (ChatGPT)) [Malkov & Yashunin (2020)] |
| FAISS | 🔥 Tren | O(log n) approximate | Facebook's ANN library; GPU support (Contoh: Pencarian embedding skala miliaran untuk pengenalan wajah biometrik) [Facebook AI Research] |
| Diameter of Point Set | 🔵 Classic | O(n log n) | Pasangan titik terjauh (Contoh: Mencari jarak terjauh antar batas provinsi) [Rotating calipers] |
| Width of Point Set | 🔵 Classic | O(n log n) | Lebar minimum bounding strip (Contoh: Menentukan lebar minimum koridor aman untuk penerbangan drone) [Rotating calipers] |
Voronoi & Delaunay
| Algoritma | Era | Kompleksitas | Penggunaan |
|---|---|---|---|
| Fortune's Algorithm (Voronoi) | 🔵 Classic | O(n log n) | Voronoi diagram 2D via sweep line (Contoh: Membagi wilayah layanan puskesmas agar pasien pergi ke lokasi terdekat) [Fortune (1987)] |
| Voronoi via Convex Hull (3D lifting) | 🔵 Classic | O(n log n) | Dual: Voronoi 2D = projection dari hull 3D (Contoh: Dekomposisi struktur material dalam kristalografi) [Shamos & Hoey] |
| Incremental Delaunay | 🔵 Classic | O(n log n) avg | Insert titik satu per satu; flip edges (Contoh: Pembuatan jaring segitiga (mesh) pada modeling 3D secara dinamis) [Guibas & Stolfi (1985)] |
| Divide & Conquer Delaunay | 🔵 Classic | O(n log n) | Merge dua half-triangulation (Contoh: Triangulasi data elevasi permukaan bumi (DEM) skala besar) [Lee & Schachter (1980)] |
| Bowyer-Watson Algorithm | 🔵 Classic | O(n²) worst, O(n log n) avg | Incremental; hapus circumcircle, retriangulasi (Contoh: Generasi terrain acak pada video game dunia terbuka) [Bowyer (1981), Watson (1981)] |
| Randomized Incremental Delaunay | 🟢 Modern | O(n log n) expected | Randomized insertion order; simpler (Contoh: Rendering topografi dasar laut dari data sonar) [Guibas et al. (1992)] |
| Constrained Delaunay Triangulation (CDT) | 🟢 Modern | O(n log n) | Delaunay dengan constraint edges (batas polygon) (Contoh: Desain jaringan jalan yang harus mengikuti batas sungai) [Chew (1989), Shewchuk] |
| Conforming Delaunay | 🟢 Modern | O(n log n) | Tambah Steiner points untuk quality mesh (Contoh: Analisis kekuatan jembatan dengan Finite Element Method (FEM)) [Shewchuk (1996)] |
| Weighted Voronoi (Power Diagram) | 🟢 Modern | O(n log n) | Voronoi dengan bobot per site (Contoh: Menentukan area pengaruh tower BTS dengan kekuatan sinyal berbeda) [Aurenhammer (1987)] |
| Additively Weighted Voronoi | 🟢 Modern | O(n log n) | Voronoi dengan radius additif (Contoh: Pemodelan zona pertumbuhan sel atau bakteri) [CG research] |
| Higher-Order Voronoi | 🔵 Classic | O(k²n log n) | Order-k Voronoi; k nearest sites (Contoh: Mencari 3 rumah sakit terdekat untuk rujukan darurat) [Shamos (1975)] |
| Voronoi on Sphere | 🟢 Modern | O(n log n) | Voronoi di permukaan bola; untuk globe (Contoh: Pemetaan wilayah kontrol satelit di orbit bumi) [CGAL spherical] |
| Dynamic Voronoi | 🔴 Research | O(log² n) amortized | Insert/delete dan maintain diagram (Contoh: Update wilayah layan (coverage) saat armada ambulans bergerak) [Kinetic CG] |
| Anisotropic Voronoi | 🔴 Research | O(n log n) | Voronoi dengan metric tensor berbeda per point (Contoh: Pemodelan aliran angin atau air yang terpengaruh arah (directional)) [CVT research] |
| Centroidal Voronoi Tessellation (CVT) | 🟢 Modern | O(n·iter) | Site = centroid cell; via Lloyd's algorithm (Contoh: Penempatan optimal titik-titik lampu jalan agar pencahayaan merata) [Du et al. (1999)] |
| Laguerre–Voronoi (Sectional) | 🔴 Research | O(n log n) | Voronoi berbasis jarak kuadrat minus bobot (Contoh: Simulasi kepadatan busa atau struktur seluler material) [Advanced CG] |
Triangulation & Mesh Generation
| Algoritma | Era | Kompleksitas | Penggunaan |
|---|---|---|---|
| Ear Clipping Triangulation | 🔵 Classic | O(n²) | Triangulasi simple polygon via ear removal (Contoh: Merender poligon 2D kompleks pada HTML5 Canvas) [Meisters (1975)] |
| Fan Triangulation | 🔵 Classic | O(n) | Triangulasi convex polygon; semua ke satu vertex (Contoh: Triangulasi cepat untuk area peluru/ledakan pada game) [Simple CG] |
| Polygon Triangulation (Optimal) | 🔵 Classic | O(n log n) | Optimal via Chazelle's algorithm (Contoh: Pemrosesan font vektor (TrueType) pada rendering teks) [Chazelle (1991)] |
| Ruppert's Algorithm (Mesh Refinement) | 🟢 Modern | O(n log n) | Quality Delaunay mesh; angle ≥ 20.7° (Contoh: Meshing aerodinamika sayap pesawat agar simulasi tidak eror) [Ruppert (1995)] |
| Shewchuk's Triangle | 🟢 Modern | O(n log n) | Robust quality mesh generation (Contoh: Simulasi perambatan panas pada komponen mesin) [Shewchuk (1996), Triangle software] |
| TetGen (3D Mesh) | 🟢 Modern | O(n log n) | Tetrahedral mesh generation 3D (Contoh: Pembuatan mesh volume 3D untuk analisis tumor dari scan MRI) [Si (2015), TetGen software] |
| Advancing Front Method | 🟢 Modern | O(n log n) | Mesh grow dari boundary ke dalam (Contoh: Meshing aliran fluida (CFD) di dalam pipa) [Löhner & Parikh (1988)] |
| Paving / Plastering | 🟢 Modern | O(n) | Quad mesh generation untuk FEM (Contoh: Meshing elemen kotak (hexahedral) untuk simulasi benturan mobil) [CG / FEM community] |
| Isosurface Extraction (Marching Cubes) | 🔵 Classic | O(n) | Extract surface dari volumetric data (Contoh: Visualisasi tulang manusia dari data CT Scan medis) [Lorensen & Cline (1987)] |
| Marching Tetrahedra | 🟢 Modern | O(n) | Variasi marching cubes; tidak ada ambiguity (Contoh: Rendering awan atau asap volumetrik di game modern) [Variant of MC] |
| Dual Contouring | 🟢 Modern | O(n) | Isosurface dengan sharp features (Contoh: Menghasilkan voxel terrain dengan permukaan halus seperti di game Minecraft) [Ju et al. (2002)] |
| Poisson Surface Reconstruction | 🟢 Modern | O(n log n) | Reconstruct surface dari point cloud (Contoh: Membuat model 3D solid dari hasil scan LiDAR drone) [Kazhdan et al. (2006)] |
| Alpha Shapes | 🔵 Classic | O(n log n) | Generalisasi convex hull; parameter α (Contoh: Menentukan batas terluar (footprint) dari sekumpulan titik rumah pendudukan) [Edelsbrunner (1983)] |
| Ball Pivoting Algorithm | 🟢 Modern | O(n log n) | 3D surface dari point cloud via rolling ball (Contoh: Rekonstruksi artefak sejarah 3D dari hasil pemindaian laser) [Bernardini et al. (1999)] |
Polygon Operations & Boolean Geometry
| Algoritma | Era | Kompleksitas | Penggunaan |
|---|---|---|---|
| Point-in-Polygon (Ray Casting) | 🔵 Classic | O(n) | Deteksi apakah titik dalam polygon (Contoh: Validasi apakah kursor mouse mengklik tombol yang bentuknya asimetris) [Shimrat (1962)] |
| Point-in-Polygon (Winding Number) | 🔵 Classic | O(n) | Lebih robust untuk complex polygon; signed count (Contoh: Mengecek apakah koordinat user GPS berada dalam batas provinsi) [Hormann & Agathos (2001)] |
| Sutherland-Hodgman Clipping | 🔵 Classic | O(n·k) | Clip polygon terhadap convex polygon (Contoh: Memotong rendering objek yang keluar dari layar monitor (viewport)) [Sutherland & Hodgman (1974)] |
| Weiler-Atherton Clipping | 🔵 Classic | O(n log n) | Clip arbitrary polygon (termasuk non-convex) (Contoh: Efek masking gambar kompleks pada editor grafis seperti Photoshop) [Weiler & Atherton (1977)] |
| Greiner-Hormann Algorithm | 🟢 Modern | O(n·m) | Boolean ops: union, intersection, difference (Contoh: Menggabungkan dua batas sertifikat tanah yang bertumpang tindih) [Greiner & Hormann (1998)] |
| Polygon Clipping (Clipper Library) | 🟢 Modern | O((n+k) log n) | Robust polygon boolean ops; integer arithmetic (Contoh: Memotong desain pola bordir digital atau jalur mesin CNC) [Angus Johnson (Clipper2)] |
| Polygon Union | 🟢 Modern | O((n+k) log n) | Union beberapa polygon (Contoh: Menyatukan poligon-poligon tutupan lahan hutan yang berdekatan) [CGAL, JTS Topology Suite] |
| Polygon Intersection | 🟢 Modern | O((n+k) log n) | Irisan dua atau lebih polygon (Contoh: Mencari area irisan antara peta rencana jalan dan peta pemukiman) [CGAL, Shapely] |
| Polygon Difference (Subtraction) | 🟢 Modern | O((n+k) log n) | Kurangi satu polygon dari polygon lain (Contoh: Menghitung sisa lahan pertanian setelah dipotong proyek tol) [CGAL, JTS] |
| Polygon XOR | 🟢 Modern | O((n+k) log n) | Symmetric difference polygon (Contoh: Mencari perbedaan perubahan batas wilayah dari dua peta tahun yang berbeda) [Clipper library] |
| Minkowski Sum (2D) | 🔵 Classic | O(mn) | Jumlah Minkowski dua polygon (Contoh: Menghitung zona clearance aman (bemper) saat memarkir mobil otonom) [Computational Geometry] |
| Minkowski Sum (3D) | 🟢 Modern | O(m²n²) | 3D Minkowski sum; robot motion planning (Contoh: Perencanaan jalur lengan robot di pabrik perakitan agar tidak menabrak) [CGAL 3D Minkowski] |
| Polygon Simplification (Douglas-Peucker) | 🔵 Classic | O(n log n) avg | Reduksi vertex polygon; tolerance ε (Contoh: Meringankan ukuran file GeoJSON peta tanpa mengubah bentuk drastis) [Douglas & Peucker (1973)] |
| Visvalingam-Whyatt Simplification | 🔵 Classic | O(n log n) | Simplifikasi berdasarkan area triangle (Contoh: Penyederhanaan peta pesisir pantai untuk tampilan zoom-out) [Visvalingam & Whyatt (1993)] |
| Topology-Preserving Simplification | 🟢 Modern | O(n log n) | Simplifikasi tanpa topologi rusak (Contoh: Menyederhanakan batas negara tanpa membuat batas antar negara bolong/overlap) [Saalfeld (1999)] |
| Polygon Offset / Buffering | 🟢 Modern | O(n log n) | Expand atau shrink polygon dengan jarak d (Contoh: Menetapkan zona bahaya radius 5 km dari kawah gunung berapi) [CGAL, JTS buffer] |
| Straight Skeleton | 🔵 Classic | O(n² log n) | Kerangka dari offset polygon hingga collapse (Contoh: Menghasilkan desain struktur atap rumah otomatis (hip roof)) [Aichholzer et al. (1995)] |
| Medial Axis Transform | 🔵 Classic | O(n log n) | "Tulang belakang" shape; via Voronoi (Contoh: Sistem deteksi pembuluh darah pada pemindaian medis) [Blum (1967)] |
| Shape Decomposition | 🟢 Modern | O(n log n) | Pecah non-convex polygon ke convex pieces (Contoh: Memecah peta rintangan menjadi bentuk sederhana untuk algoritma pathfinding A*) [Chazelle & Dobkin (1985)] |
| Polygon Morphing | 🟢 Modern | O(n) | Interpolasi antara dua polygon shapes (Contoh: Animasi transisi halus antara ikon A menjadi ikon B pada UI web) [CG animation] |
Spatial Search & Indexing Structures
| Algoritma / Struktur | Era | Kompleksitas | Penggunaan |
|---|---|---|---|
| KD-Tree | 🔵 Classic | O(log n) avg | Nearest neighbor, range query 2D/3D (Contoh: Pencarian restoran terdekat pada aplikasi Gojek (sebelum Redis)) [scipy.spatial, nanoflann] |
| Range Tree | 🔵 Classic | O(log^d n + k) | d-dimensional orthogonal range query (Contoh: Mencari pelanggan yang berada di kordinat X1-X2 dan berumur Y1-Y2) [Computational Geometry] |
| Segment Tree (2D) | 🔵 Classic | O(log² n + k) | 2D segment intersection, stabbing query (Contoh: Analisis rentang wilayah yang terkena bayangan gerhana matahari) [Competitive programming] |
| Interval Tree | 🔵 Classic | O(log n + k) | Query interval yang overlap dengan query (Contoh: Mengecek apakah jadwal booking hotel tumpang tindih) [std::set based] |
| R-Tree | 🔵 Classic | O(log n) | Spatial indexing untuk MBR; disk-based (Contoh: Indeks utama PostGIS untuk mempercepat kueri batas wilayah) [PostGIS, SQLite] |
| R*-Tree | 🟢 Modern | O(log n) | Improved R-Tree dengan better split heuristic (Contoh: Pengindeksan ruang memori pada sistem basis data spasial raksasa) [libspatialindex] |
| R+-Tree | 🟢 Modern | O(log n) | R-Tree dengan non-overlapping regions (Contoh: Sistem deteksi benturan objek spasial berkecepatan tinggi) [Spatial DB] |
| Hilbert R-Tree | 🟢 Modern | O(log n) | R-Tree dengan Hilbert curve ordering (Contoh: Pengindeksan data spasial dengan urutan memori yang lebih optimal) [Kamel & Faloutsos (1994)] |
| Packed R-Tree | 🟢 Modern | O(log n) | Bulk-loaded read-only R-Tree; very fast (Contoh: Membangun indeks peta statis untuk dibaca oleh aplikasi frontend (Flatbush)) [Flatbush JS, CGAL] |
| STR-Tree (Sort-Tile-Recursive) | 🟢 Modern | O(log n) | Bulk-load R-Tree via tiling (Contoh: Memuat jutaan data polygon gedung sekaligus ke memori GIS) [JTS, Shapely] |
| Grid File | 🔵 Classic | O(1) avg | Uniform grid spatial index (Contoh: Penyimpanan data sensor cuaca yang tersebar merata) [Simple spatial DB] |
| Quadtree (2D) | 🔵 Classic | O(log n) | Recursive 4-way space partition (Contoh: Membagi layar rendering game untuk deteksi tabrakan 2D) [Finkel & Bentley (1974)] |
| Octree (3D) | 🔵 Classic | O(log n) | 3D extension quadtree (Contoh: Menyimpan data voxel 3D LiDAR untuk kendaraan otonom) [3D game engine, LiDAR] |
| BSP Tree (Binary Space Partition) | 🔵 Classic | O(n log n) | 3D rendering, ray casting (Contoh: Penentuan urutan render dinding pada game DOOM lawas) [Doom, Quake engine] |
| BVH (Bounding Volume Hierarchy) | 🟢 Modern | O(log n) | Ray tracing, collision detection (Contoh: Akselerasi ray tracing pencahayaan pada game AAA) [Game engine, ray tracer] |
| Cover Tree | 🟢 Modern | O(c^d log n) | Metric space NN; dimensionally independent (Contoh: Pencarian kesamaan struktur protein kompleks di bioinformatika) [Beygelzimer et al. (2006)] |
| Locality Sensitive Hashing (LSH) | 🟢 Modern | O(1) approx | Approximate NN via hashing (Contoh: Deteksi plagiarisme dokumen dan gambar) [Indyk & Motwani (1998)] |
| Product Quantization (PQ) | 🟢 Modern | O(m·d/m) | Approximate NN via vector compression (Contoh: Kompresi miliaran vektor embeddings di database AI) [Jégou et al. (2011), FAISS] |
| HNSW | 🔥 Tren | O(log n) | Graph-based ANN; best trade-off speed/recall (Contoh: Vector search engine di balik Retrieval-Augmented Generation (RAG)) [hnswlib, Weaviate, Milvus] |
| H3 (Uber Hexagonal) | 🔥 Tren | O(1) | Hierarchical hex grid indexing (Contoh: Pembagian wilayah surge pricing (tarif dinamis) pada Uber/Gojek) [H3 library (Uber)] |
| S2 Geometry | 🔥 Tren | O(log n) | Spherical geometry + cell indexing (Google) (Contoh: Sistem backend Google Maps untuk index geospasial) [S2 library] |
| GeoHash | 🔵 Classic | O(log n) | Base32 encode lat/lng; prefix = proximity (Contoh: Pengiriman koordinat pengguna di aplikasi kencan seperti Tinder) [PostGIS, Redis GeoSearch] |
| What3Words Grid | 🟢 Modern | O(1) | 3-word address untuk 3×3m grid (Contoh: Pengiriman lokasi darurat di daerah tanpa nama jalan) [W3W API] |
| Morton Code (Z-Order Curve) | 🔵 Classic | O(1) | Bit-interleaving untuk spatial locality (Contoh: Akselerasi kueri spasial menggunakan GPU) [GPU spatial, database] |
| Hilbert Curve Indexing | 🟢 Modern | O(1) | Better spatial locality dari Morton (Contoh: Pemrosesan data satelit cuaca yang sangat besar) [Database, GPU spatial] |
| Space Filling Curve (SFC) | 🔵 Classic | O(1) | General SFC untuk multidimensional indexing (Contoh: Partisi data geospasial di Hadoop/Spark) [DB research] |
Geometric Shortest Path & Visibility
| Algoritma | Era | Kompleksitas | Penggunaan |
|---|---|---|---|
| Visibility Graph | 🔵 Classic | O(n² log n) | Shortest path di antara obstacles (polygon) (Contoh: Menentukan jalur terbang drone yang menghindari gedung pencakar langit) [Lee & Preparata (1979)] |
| Shortest Path in Simple Polygon | 🔵 Classic | O(n) | Euclidean shortest path di dalam polygon (Contoh: Routing kabel di dalam sasis handphone) [Lee & Preparata (1984)] |
| Geodesic Path on Mesh | 🟢 Modern | O(n log n) | Shortest path di permukaan mesh 3D (Contoh: Menghitung jarak potongan kain pada desain baju 3D) [Mitchell et al. (1987)] |
| Fast Marching Method (FMM) | 🟢 Modern | O(n log n) | Eikonal equation; geodesic distance (Contoh: Simulasi perambatan gelombang tsunami di samudra) [Sethian (1996)] |
| Dijkstra on Visibility Graph | 🔵 Classic | O(n² log n) | Shortest path 2D dengan obstacles (Contoh: Pathfinding NPC game stealth untuk menghindari garis pandang) [Classic CG] |
| Tangent Graph | 🔵 Classic | O(n²) | Visibility graph menggunakan tangent lines (Contoh: Perencanaan rute kapal laut menghindari pulau-pulau) [Robot motion planning] |
| Any-Angle Path Planning | 🟢 Modern | O(n log n) | Theta*, ANYA — tidak terbatas ke grid edges (Contoh: Pergerakan mulus unit pasukan di game RTS (Starcraft)) [Nash et al. (2007)] |
| Funnel Algorithm | 🔵 Classic | O(n) | Shortest path dalam triangulated polygon (Contoh: Pergerakan karakter game menyusuri koridor sempit) [Lee & Preparata (1984)] |
| Art Gallery Problem | 🔵 Classic | NP-hard | Minimum guards untuk cover polygon (Contoh: Penempatan optimal kamera CCTV di dalam minimarket) [Chvátal (1975)] |
| Watchman Route Problem | 🔴 Research | NP-hard | Shortest tour dari mana semua polygon terlihat (Contoh: Rute satpam patroli keliling gedung) [CG research] |
| Continuous Dijkstra | 🔵 Classic | O(n log n) | Shortest Euclidean path, continuous domain (Contoh: Simulasi aliran evakuasi keramaian di stadion) [Lee & Preparata (1984)] |
| Fréchet Distance | 🟢 Modern | O(n²) | Similarity antara dua curves/paths (Contoh: Membandingkan kemiripan rute anjing pelacak dengan jalur manusia) [Alt & Godau (1995)] |
| Hausdorff Distance | 🔵 Classic | O(n log n) | Max of min distances antara dua point sets (Contoh: Mencocokkan bentuk plat nomor mobil dengan template database) [Computational Geometry] |
| Dynamic Time Warping (DTW) | 🟢 Modern | O(n²) | Similarity trajectory dengan time warping (Contoh: Pendeteksi kesamaan tanda tangan digital) [Trajectory analysis] |
Geometric Transforms & Duality
| Algoritma | Era | Kompleksitas | Penggunaan |
|---|---|---|---|
| Point-Line Duality Transform | 🔵 Classic | O(1) per point | Transform point ↔ line; dual problems (Contoh: Mendeteksi kelompok garis yang sejajar (Hough Transform)) [CG duality] |
| Projective Transformation | 🔵 Classic | O(1) | Homogeneous coordinates; perspective transform (Contoh: Koreksi foto miring hasil scan dokumen (CamScanner)) [Computer vision] |
| Affine Transformation | 🔵 Classic | O(1) | Rotate, scale, shear, translate; linear (Contoh: Fitur rotate dan scale pada aplikasi Canva) [All geometric systems] |
| Möbius Transformation | 🔵 Classic | O(1) | Conformal map; circle → circle (Contoh: Simulasi deformasi lensa fisheye) [Complex analysis, CG] |
| Stereographic Projection | 🔵 Classic | O(1) | Sphere → plane mapping (Contoh: Pemetaan langit malam (astronomi)) [Cartography, CG] |
| Geometric Hashing | 🟢 Modern | O(n) | Object recognition via hash table of features (Contoh: Sistem deteksi sidik jari kepolisian otomatis (AFIS)) [Computer vision] |
| Rotating Calipers | 🔵 Classic | O(n) | Diameter, width, antipodal pairs on convex hull (Contoh: Membuat kotak pembungkus terkecil (bounding box) untuk pengiriman paket) [Shamos (1978)] |
| Ham-Sandwich Theorem Cut | 🔵 Classic | O(n log n) | Simultaneously bisect d sets in d-space (Contoh: Membagi dua adonan roti yang memiliki isi berbeda) [Theoretical CG] |
| Radon Partition | 🔵 Classic | O(n²) | Partition point set; any d+2 points (Contoh: Pemisahan kelompok data point di machine learning) [Topological CG] |
| Helly's Theorem Application | 🔵 Classic | O(n·d) | Intersection of convex sets in R^d (Contoh: Deteksi apakah semua sensor IoT mencakup area titik yang sama) [Combinatorial CG] |
Curve & Shape Analysis
| Algoritma | Era | Kompleksitas | Penggunaan |
|---|---|---|---|
| Bezier Curve de Casteljau | 🔵 Classic | O(n²) | Evaluasi Bezier curve; stable numerically [de Casteljau (1959)] |
| B-Spline / NURBS | 🔵 Classic | O(n·k) | Non-Uniform Rational B-Spline; CAD standard [Schoenberg, Piegl & Tiller] |
| Catmull-Rom Spline | 🔵 Classic | O(n) | Smooth interpolating spline; game paths [Catmull & Rom (1974)] |
| Subdivision Curves | 🔵 Classic | O(n) per level | Chaikin, Lane-Riesenfeld; smooth via refine [Chaikin (1974)] |
| Subdivision Surfaces | 🟢 Modern | O(n) per level | Catmull-Clark, Loop; smooth 3D mesh [Catmull & Clark (1978)] |
| Curvature Estimation | 🟢 Modern | O(n) | Komputasi curvature dari discrete points [Differential geometry] |
| Curve Smoothing (Laplacian) | 🟢 Modern | O(n) | Smooth kurva/mesh via Laplacian operator [Signal processing on graphs] |
| Shape Context Descriptor | 🟢 Modern | O(n²) | Shape comparison via context histogram [Belongie et al. (2002)] |
| Contour Tracing (Moore Neighbor) | 🔵 Classic | O(n) | Trace batas objek dalam binary image [CG + CV] |
| Douglas-Peucker Simplification | 🔵 Classic | O(n log n) | Reduksi titik kurva; topologi preserved [Douglas & Peucker (1973)] |
| Ramer's Algorithm | 🔵 Classic | O(n log n) | Sama dengan Douglas-Peucker [Ramer (1972)] |
| Thinning / Skeletonization | 🔵 Classic | O(n·iter) | Extract skeleton dari binary shape [Zhang & Suen (1984)] |
| Convex Decomposition | 🟢 Modern | O(n log n) | Pecah shape ke convex components [CG research] |
| Shape Matching (Procrustes) | 🔵 Classic | O(n) | Align dua shape; minimize distance [Dryden & Mardia] |
| Point Cloud Registration (ICP) | 🟢 Modern | O(n²) per iter | Iterative Closest Point; align two point clouds [Besl & McKay (1992)] |
| NDT (Normal Distribution Transform) | 🟢 Modern | O(n) | Registration lebih cepat dari ICP [Biber & Straßer (2003)] |
| RANSAC for Geometric Fitting | 🟢 Modern | O(iter·n) | Robust fitting line/plane/circle dari noisy data [Fischler & Bolles (1981)] |
Motion Planning & Robot Geometry
| Algoritma | Era | Kompleksitas | Penggunaan |
|---|---|---|---|
| Configuration Space (C-Space) | 🔵 Classic | Varies | Representasi robot state; obstacle avoidance [Lozano-Pérez (1983)] |
| Bug Algorithms (Bug0/Bug1/Bug2/Tangent Bug) | 🔵 Classic | O(n) | Simple reactive robot navigation [Lumelsky & Stepanov (1987)] |
| Potential Field Method | 🔵 Classic | O(n) | Attractive goal + repulsive obstacles [Khatib (1986)] |
| Probabilistic Roadmap (PRM) | 🟢 Modern | O(n log n) | Random sampling + local planner; high-dim [Kavraki et al. (1996)] |
| RRT (Rapidly-exploring Random Tree) | 🟢 Modern | O(n log n) | Explore via random tree expansion [LaValle (1998)] |
| RRT* (Optimal RRT) | 🟢 Modern | O(n log n) | RRT dengan rewiring; asymptotically optimal [Karaman & Frazzoli (2011)] |
| Informed RRT* | 🟢 Modern | O(n log n) | RRT* dengan heuristic ellipse sampling [Gammell et al. (2014)] |
| Bi-directional RRT (BiRRT) | 🟢 Modern | O(n log n) | Tree dari start DAN goal; meet in middle [Kuffner & LaValle (2000)] |
| RRT-Connect | 🟢 Modern | O(n log n) | Aggressive BiRRT; faster in practice [Kuffner & LaValle (2000)] |
| BIT* (Batch Informed Trees) | 🔴 Research | O(n log n) | A* on implicit RGG; efficient global planning [Gammell et al. (2015)] |
| CHOMP | 🟢 Modern | O(n·iter) | Trajectory optimization via gradient descent [Ratliff et al. (2009)] |
| STOMP | 🟢 Modern | O(n·iter) | Stochastic trajectory optimization [Kalakrishnan et al. (2011)] |
| Visibility-based PRM | 🟢 Modern | O(n log n) | Compact roadmap via visibility [Simeon et al. (2000)] |
| Cell Decomposition | 🔵 Classic | O(n²) | Exact atau approximate cell-based planning [CG + Robotics] |
| Trapezoidal Decomposition | 🔵 Classic | O(n log n) | Dekomposisi free space jadi trapezoid [Standard CG] |
| Generalized Voronoi Diagram (GVD) | 🟢 Modern | O(n log n) | Maximize clearance path via Voronoi [CG + Robotics] |
| Dynamic Window Approach (DWA) | 🟢 Modern | O(n) | Local planner; feasible velocity space [Fox et al. (1997)] |
| TEB (Timed Elastic Band) | 🟢 Modern | O(n·iter) | Local planner; time-optimal trajectory [Rösmann et al. (2012)] |
12. Geospatial & Spatial Analysis
Map Projection & Coordinate Systems
| Algoritma | Era | Kompleksitas | Penggunaan |
|---|---|---|---|
| Mercator Projection | 🔵 Classic | O(1) | Web map tiles; conformal, angle preserved (Contoh: Navigasi laut historis dan peta Google Maps (Web Mercator)) [EPSG:3857, Web Mercator] |
| Transverse Mercator (UTM) | 🔵 Classic | O(1) | UTM zones; accurate untuk narrow strips (Contoh: Sistem peta administrasi agraria (BPN) di Indonesia) [EPSG:32N/S series] |
| Lambert Conformal Conic | 🔵 Classic | O(1) | Mid-latitude mapping; US state plane (Contoh: Peta penerbangan pesawat wilayah ekuator) [EPSG LCC variants] |
| Albers Equal-Area Conic | 🔵 Classic | O(1) | Area-preserving; thematic maps (Contoh: Peta tematik kepadatan penduduk yang menghindari distorsi luasan) [USA national maps] |
| Stereographic Projection | 🔵 Classic | O(1) | Polar regions; Antarctic, Arctic maps (Contoh: Pemetaan langit malam (astronomi)) [EPSG:3031, 3995] |
| Robinson Projection | 🔵 Classic | O(1) | World map; compromise projection (Contoh: Peta dunia di buku teks sekolah (kompromi distorsi)) [Deprecated by Winkel Tripel] |
| Winkel Tripel Projection | 🔵 Classic | O(1) | World map standard (National Geographic) (Contoh: Standar peta dunia rilisan National Geographic) [Eckert Winkel tripel] |
| Mollweide Projection | 🔵 Classic | O(1) | Equal-area world map (Contoh: Peta sebaran radiasi gelombang kosmik (astronomi)) [Thematic mapping] |
| Sinusoidal Projection | 🔵 Classic | O(1) | Equal-area; MODIS product grid (Contoh: Peta satelit MODIS NASA) [Remote sensing] |
| Plate Carrée (Equirectangular) | 🔵 Classic | O(1) | Simplest; lat/lng → x/y directly (Contoh: Pemetaan tekstur globe 3D dan video 360 derajat) [WGS84 geographic] |
| LAEA (Lambert Azimuthal EA) | 🔵 Classic | O(1) | Single-hemisphere equal area (Contoh: Peta persentase tutupan lahan hutan di Uni Eropa) [Europe: EPSG:3035] |
| Goode's Homolosine | 🔵 Classic | O(1) | Interrupted equal-area world (Contoh: Peta atlas distribusi spesies hewan global) [Atlas mapping] |
| AuthaGraph Projection | 🟢 Modern | O(1) | Nearly equal-area polyhedra unfolding (Contoh: Peta lipat arsitektur untuk menjaga proporsi wilayah secara presisi) [Japan 2016] |
| Dymaxion / Fuller Projection | 🔵 Classic | O(1) | Icosahedral unfolding; minimal distortion (Contoh: Visualisasi aliran arus samudra tanpa terputus) [Buckminster Fuller (1943)] |
| Coordinate Conversion (Helmert) | 🔵 Classic | O(1) | Datum transformation 7-parameter (Contoh: Transformasi data kordinat WGS84 ke sistem lokal) [Geodesy standard] |
| PROJ Library Transformations | 🟢 Modern | O(1) | General geodetic transformations (Contoh: Konversi kordinat massal di software QGIS) [PROJ (OSGeo)] |
Geodesic & Distance on Earth
| Algoritma | Era | Kompleksitas | Penggunaan |
|---|---|---|---|
| Haversine Formula | 🔵 Classic | O(1) | Great-circle distance (spherical Earth) (Contoh: Menghitung tarif jarak tempuh langsung pada aplikasi ojek online) [geopy, turf.js] |
| Vincenty Formula | 🔵 Classic | O(iter) | Geodesic distance (ellipsoidal Earth); high accuracy (Contoh: Pengukuran jarak presisi tinggi pada konstruksi jembatan antarpulau) [geopy, Vincenty] |
| Karney's Algorithm (GeodPy) | 🟢 Modern | O(1) | Most accurate geodesic; series expansion (Contoh: Perhitungan jarak geodesik akurat untuk navigasi satelit) [geographiclib (Karney 2013)] |
| Great-Circle Navigation | 🔵 Classic | O(1) | Initial bearing, midpoint, waypoints (Contoh: Sistem autopilot rute pesawat komersial antarbenua) [Aviation, maritime] |
| Rhumb Line (Loxodrome) | 🔵 Classic | O(1) | Constant bearing path; mercator line (Contoh: Navigasi kapal laut jarak dekat menggunakan kompas magnetik) [Marine navigation] |
| Geodesic on Ellipsoid | 🔵 Classic | O(iter) | True shortest path on WGS84 ellipsoid (Contoh: Penetapan batas teritorial laut antar negara (ZEE)) [geographiclib] |
| Along-Track Distance | 🔵 Classic | O(1) | Distance along great circle dari point ke path (Contoh: Menghitung jarak tempuh kereta api pada rel) [turf.js, geopy] |
| Cross-Track Distance | 🔵 Classic | O(1) | Perpendicular distance titik ke great-circle path (Contoh: Peringatan pesawat yang melenceng dari jalur terbang (off-course)) [turf.js] |
| Bearing Calculation | 🔵 Classic | O(1) | Sudut dari utara ke titik tujuan (Contoh: Penunjuk arah kiblat pada aplikasi sholat) [turf.js, geopy] |
| Midpoint on Great Circle | 🔵 Classic | O(1) | Midpoint antara dua koordinat (Contoh: Menentukan titik kumpul tengah antara dua pelacak GPS) [turf.js] |
| Destination Point | 🔵 Classic | O(1) | Titik setelah jarak d di bearing b (Contoh: Memproyeksikan lokasi peluru kendali setelah terbang sejauh 5 km) [turf.js] |
Geospatial Indexing & Search
| Algoritma | Era | Kompleksitas | Penggunaan |
|---|---|---|---|
| GeoHash | 🔵 Classic | O(1) | Base32 lat/lng encode; prefix = bounding box (Contoh: Pengiriman koordinat pengguna di aplikasi kencan seperti Tinder) [Redis GEOSEARCH, PostGIS] |
| Tile38 Spatial Index | 🟢 Modern | O(log n) | Real-time geospatial db; geofencing (Contoh: Geofencing armada bus kota secara real-time) [Tile38] |
| Quadtree Spatial Index | 🔵 Classic | O(log n) | 2D recursive partitioning [Many GIS implementations] |
| R-Tree (PostGIS) | 🔵 Classic | O(log n) | Default spatial index PostgreSQL/PostGIS (Contoh: Mesin kueri di balik aplikasi pencarian properti (Rumah123)) [PostGIS GIST index] |
| H3 Hexagonal Grid | 🔥 Tren | O(1) | Hierarchical hex indexing; Uber (Contoh: Agregasi data sebaran kepadatan penumpang Uber) [H3-py, DeckGL] |
| S2 Cell Index | 🔥 Tren | O(log n) | Google's spherical cap indexing (Contoh: Sistem backend index geospasial Pokemon GO) [S2 geometry library] |
| OpenLocationCode (Plus Code) | 🟢 Modern | O(1) | Google's open location code; no internet needed (Contoh: Berbagi alamat rumah di area tanpa nama jalan resmi) [Google Plus Codes] |
| Geofencing Algorithm | 🟢 Modern | O(n) | Deteksi apakah titik dalam fence polygon (Contoh: Absensi online presensi pegawai masuk radius kantor) [Tile38, turf.js, PostGIS] |
| Spatial Join | 🟢 Modern | O(n log m) | Join dua layer spatial berdasarkan relasi (Contoh: Menggabungkan data GPS pelanggan dengan peta kode pos) [PostGIS ST_Join, geopandas sjoin] |
| KNN on Sphere | 🟢 Modern | O(log n) | K nearest neighbor dengan spherical distance (Contoh: Mencari 5 pom bensin terdekat dari koordinat saat ini) [PostGIS, spatialite] |
| Spatial Clustering (DBSCAN geo) | 🟢 Modern | O(n log n) | Cluster GPS points dengan haversine distance (Contoh: Menemukan klaster kerumunan warga saat pandemi dari sinyal HP) [scikit-learn DBSCAN + haversine] |
| Binning (Hex/Square/Triangle) | 🟢 Modern | O(n) | Aggregate points ke grid cells (Contoh: Visualisasi heatmap kepadatan lalu lintas harian) [H3, S2, DeckGL] |
Map Generalization & Simplification
| Algoritma | Era | Kompleksitas | Penggunaan |
|---|---|---|---|
| Douglas-Peucker (Ramer–Douglas–Peucker) | 🔵 Classic | O(n log n) avg | Simplifikasi polyline; toleransi ε (Contoh: Mempercepat load peta gpx rute sepeda Strava) [turf.js, Shapely, GDAL] |
| Visvalingam-Whyatt | 🔵 Classic | O(n log n) | Simplifikasi berbasis area triangle (Contoh: Menghaluskan garis pantai pada aplikasi peta cuaca) [Simplification library] |
| Lang Simplification | 🔵 Classic | O(n) | Look-ahead window simplification (Contoh: Penyederhanaan data lintasan sungai) [GIS tools] |
| Chaikin's Corner Cutting | 🔵 Classic | O(n) | Smooth polyline via subdivision (Contoh: Membuat tikungan jalan yang dirender peta menjadi melengkung halus) [CG + GIS] |
| Topology-Preserving Simplification | 🟢 Modern | O(n log n) | Simplifikasi tanpa topologi break (Contoh: Menyederhanakan batas negara tanpa membuat batas antar negara bolong/overlap) [PostGIS ST_Simplify] |
| Reumann-Witkam Algorithm | 🔵 Classic | O(n) | Strip-based simplification (Contoh: Meringankan render vektor rel kereta) [GIS] |
| Opheim Simplification | 🔵 Classic | O(n) | Min/max distance simplification (Contoh: Filter noise data koordinat GPS pelacak) [GIS] |
| Jenks Natural Breaks | 🔵 Classic | O(n²) | Optimal class breaks untuk choropleth (Contoh: Pewarnaan zona merah, kuning, hijau kasus COVID-19 pada peta choropleth) [QGIS, natural breaks classifier] |
| Equal Interval Classification | 🔵 Classic | O(n) | Data classification untuk mapping (Contoh: Pewarnaan peta tingkat curah hujan per 10 mm) [GIS] |
| Quantile Classification | 🔵 Classic | O(n log n) | Equal-count class breaks (Contoh: Peta distribusi kuintil tingkat kemiskinan) [GIS, mapclassify] |
| Standard Deviation Classification | 🔵 Classic | O(n) | Class breaks berdasarkan std dev (Contoh: Peta anomali kenaikan suhu permukaan laut) [GIS] |
| Head/Tail Breaks | 🟢 Modern | O(n log n) | Classification untuk heavy-tail distribution (Contoh: Klasifikasi peta sebaran cuitan Twitter yang sangat timpang) [Jiang (2013)] |
| Label Placement Algorithm | 🟢 Modern | O(n log n) | Optimal label placement tanpa overlap (Contoh: Menata otomatis teks nama kota di Google Maps) [Map label placement, Mapbox] |
| Collision Detection for Labels | 🟢 Modern | O(n log n) | Cegah label bertabrakan di map (Contoh: Menyembunyikan teks nama restoran saat peta di-zoom out) [Mapbox GL, MapLibre] |
Routing & Network Algorithms (Geospatial)
Classic Graph Routing
| Algoritma | Era | Kompleksitas | Penggunaan |
|---|---|---|---|
| Dijkstra's Algorithm | 🔵 Classic | O((V+E) log V) | Shortest path; baseline routing (Contoh: Dasar perhitungan rute navigasi open source) [OSM routing] |
| A* (A-star) | 🔵 Classic | O(E log V) | Heuristic shortest path; GPS navigation (Contoh: Engine utama pencarian rute pada game dan navigasi GPS) [pgRouting, OSRM] |
| Bidirectional Dijkstra | 🔵 Classic | O(E log V) | Dari dua arah sekaligus; lebih cepat (Contoh: Pencarian rute tol dari dua pintu secara paralel) [pgRouting] |
| Bidirectional A* | 🔵 Classic | O(E log V) | Bidirectional dengan heuristic (Contoh: Pencarian rute jarak jauh yang lebih cepat) [Routing engines] |
| Bellman-Ford | 🔵 Classic | O(VE) | Negative weight; time-dependent routing (Contoh: Routing trafik jaringan internet dinamis (BGP)) [Theoretical routing] |
| Floyd-Warshall | 🔵 Classic | O(V³) | All-pairs shortest path; small graph (Contoh: Analisis jarak antarkota pada matriks logistik) [Small road network] |
| Johnson's Algorithm | 🔵 Classic | O(V² log V + VE) | All-pairs sparse graph (Contoh: Perhitungan logistik jarak pendek kompleks) [Network analysis] |
Speed-Up Techniques
| Algoritma | Era | Kompleksitas | Penggunaan |
|---|---|---|---|
| Contraction Hierarchies (CH) | 🟢 Modern | O(1) query | State-of-art road routing; OSRM default (Contoh: Backend routing seketika pada OpenSRM) [OSRM, RoutingKit] |
| Transit Node Routing (TNR) | 🟢 Modern | O(1) query | Ultra-fast long-distance routing (Contoh: Navigasi antarnegara lintas benua secara kilat) [Bast et al. (2007)] |
| Hub Labeling | 🟢 Modern | O(label size) | Fastest known exact routing (Contoh: Mesin kueri jarak supercepat untuk API routing) [Abraham et al. (2012)] |
| SHARC | 🟢 Modern | O(E log V) | Arc-flag + CH combination (Contoh: Kombinasi routing hirarki dan area untuk server GPS) [Bauer et al. (2008)] |
| ALT (A* + Landmarks + Triangle) | 🟢 Modern | O(E log V) | A* dengan landmark heuristic (Contoh: Pencarian rute cepat menggunakan gedung ikonik sebagai patokan) [Goldberg & Harrelson (2005)] |
| Reach-Based Routing | 🟢 Modern | O(E log V) | Prune vertices dengan low reach (Contoh: Membuang rute gang sempit saat navigasi perjalanan jauh) [Gutman (2004)] |
| Arc Flags | 🟢 Modern | O(E log V) | Precompute flags per partition (Contoh: Mempartisi peta negara bagian untuk pencarian rute lintas batas) [Lauther (2004)] |
| RAPTOR | 🟢 Modern | O(k·E) | Round-based public transit routing (Contoh: Sistem pencarian jadwal kereta/bus tanpa graph routing) [Delling et al. (2015)] |
| Connection Scan Algorithm (CSA) | 🟢 Modern | O(C) | Scan connections chronologically; transit (Contoh: Kueri jadwal penerbangan pesawat terkoneksi) [Dibbelt et al. (2013)] |
| Trip-Based Routing | 🟢 Modern | O(T) | Earliest arrival via trips; transit (Contoh: Optimalisasi transfer tiket KRL dan TransJakarta) [Witt (2015)] |
| Time-Dependent Dijkstra | 🟢 Modern | O(E log V) | Routing dengan waktu tiba berbeda (Contoh: Navigasi Google Maps yang memperhitungkan macet jam sibuk) [Time-dependent routing] |
| Profile Queries | 🟢 Modern | O(E log V) | Optimal departure time query (Contoh: Rekomendasi jam berangkat terbaik dari Jakarta ke Bandung) [Advanced routing] |
Optimization Routing
| Algoritma | Era | Kompleksitas | Penggunaan |
|---|---|---|---|
| Travelling Salesman Problem (TSP) | 🔵 Classic | NP-hard | Kunjungi semua titik sekali; minimum cost (Contoh: Rute kurir paket JNE keliling komplek) [OR-Tools, Concorde] |
| Christofides Algorithm | 🔵 Classic | O(n³) | 1.5-approximation TSP (Contoh: Pendekatan rute wisata keliling 10 kota Eropa) [Christofides (1976)] |
| Lin-Kernighan Heuristic | 🔵 Classic | O(n²·k) | High-quality TSP heuristic (Contoh: Sistem optimasi rute sales lapangan obat-obatan) [LKH solver] |
| LKH-3 | 🟢 Modern | O(n²·k) | State-of-art TSP; handles VRP variants (Contoh: Pemecah routing tingkat lanjut perusahaan logistik) [LKH-3 solver] |
| Vehicle Routing Problem (VRP) | 🔵 Classic | NP-hard | Fleet routing dengan kapasitas (Contoh: Pembagian rute truk sampah kota berdasarkan kapasitas) [OR-Tools, VROOM] |
| VRPTW (VRP with Time Windows) | 🟢 Modern | NP-hard | VRP + waktu pengiriman constraints (Contoh: Rute pengiriman sayur segar dengan batas waktu (Sameday)) [OR-Tools] |
| CVRP (Capacitated VRP) | 🔵 Classic | NP-hard | VRP dengan kapasitas kendaraan (Contoh: Rute truk tangki bensin menyuplai SPBU) [Google OR-Tools] |
| Clarke-Wright Savings | 🔵 Classic | O(n² log n) | Greedy VRP heuristic (Contoh: Logistik gudang e-commerce meminimalisir jarak armada) [Logistics software] |
| Or-Opt | 🟢 Modern | O(n²) | Local search; relocate segments (Contoh: Algoritma local search pengubahan jadwal kurir mendadak) [VROOM, OR-Tools] |
| Sweep Algorithm (VRP) | 🔵 Classic | O(n log n) | Cluster-first route-second heuristic (Contoh: Membagi wilayah antaran paket pos menggunakan sapuan sudut radar) [Logistics] |
| Large Neighborhood Search (LNS) | 🟢 Modern | O(iter·n) | Destroy + repair metaheuristic untuk VRP (Contoh: Sistem optimasi routing harian logistik skala enterprise) [DPDP solver] |
| Electric Vehicle Routing (EVRP) | 🔥 Tren | NP-hard | VRP + charging station constraints (Contoh: Perencanaan rute truk listrik dengan mampir ke SPKLU) [OR-Tools extension] |
| Isochrone-Based Routing | 🔥 Tren | O(V log V) | Area reachable dalam N menit (Contoh: Pemetaan area yang bisa dijangkau pemadam kebakaran dalam 5 menit) [Valhalla, OpenRouteService] |
| Multi-Modal Routing | 🔥 Tren | O(E log V) | Gabungan jalan/transit/bike/walk (Contoh: Navigasi campuran jalan kaki, naik KRL, lalu naik ojek) [OpenTripPlanner] |
| Pedestrian / Bicycle Routing | 🟢 Modern | O(E log V) | Network dengan surface dan slope weights (Contoh: Aplikasi Strava untuk rute sepeda menghindari jalan raya) [GraphHopper, OSRM] |
Spatial Analysis & Geostatistics
Spatial Autocorrelation
| Algoritma | Era | Kompleksitas | Penggunaan |
|---|---|---|---|
| Moran's I | 🔵 Classic | O(n²) | Global spatial autocorrelation (Contoh: Mendeteksi apakah tingkat pengangguran mengelompok di wilayah tertentu) [PySAL, spdep (R)] |
| Geary's C | 🔵 Classic | O(n²) | Local variation spatial autocorrelation (Contoh: Menganalisis variasi lokal harga tanah antar kecamatan) [PySAL] |
| Getis-Ord G (Hot Spot) | 🟢 Modern | O(n²) | Hot spot detection; Gi* statistic (Contoh: Analisis hot spot tindak kriminalitas di kepolisian) [ArcGIS, PySAL, ESDA] |
| LISA (Local Indicators of Spatial Association) | 🟢 Modern | O(n²) | Local Moran's I per area (Contoh: Menemukan kantong kemiskinan ekstrem di tengah kota maju) [PySAL, GeoDa] |
| Spatial Lag Model | 🔵 Classic | O(n²) | Regression dengan spatial lagged variable (Contoh: Prediksi harga rumah yang dipengaruhi fasilitas tetangganya) [PySAL, spdep] |
| Spatial Error Model | 🔵 Classic | O(n²) | Regression dengan spatial error term (Contoh: Pemodelan dampak limpasan limbah polusi pabrik) [PySAL, spdep] |
| Geographically Weighted Regression (GWR) | 🟢 Modern | O(n²) | Lokal regression; koefisien berbeda per lokasi (Contoh: Pemodelan penyebaran penyakit malaria yang berbeda di setiap pulau) [PySAL, GWR4, R] |
| Multiscale GWR (MGWR) | 🔴 Research | O(n²) | GWR dengan bandwidth berbeda per variabel (Contoh: Analisis dampak perubahan iklim pada ekosistem lokal yang beragam) [MGWR software] |
Interpolation & Surface Estimation
| Algoritma | Era | Kompleksitas | Penggunaan |
|---|---|---|---|
| Kriging (Ordinary) | 🔵 Classic | O(n³) | Optimal spatial interpolation via variogram (Contoh: Memperkirakan kadar emas di area tambang dari titik sampel bor) [PyKrige, gstat (R)] |
| Simple Kriging | 🔵 Classic | O(n³) | Kriging dengan known mean (Contoh: Interpolasi curah hujan dari beberapa stasiun cuaca terdekat) [PyKrige] |
| Universal Kriging | 🔵 Classic | O(n³) | Kriging dengan trend surface (Contoh: Memodelkan elevasi air tanah berdasar tren topografi) [PyKrige] |
| Co-Kriging | 🔵 Classic | O(n³) | Kriging dengan secondary variable (Contoh: Memperkirakan salinitas laut dengan bantuan citra satelit) [gstat] |
| Indicator Kriging | 🟢 Modern | O(n³) | Kriging untuk probability mapping (Contoh: Peta probabilitas risiko kontaminasi tanah beracun) [GSLIB] |
| Sequential Gaussian Simulation | 🟢 Modern | O(n·iter) | Monte Carlo spatial simulation (Contoh: Simulasi monte carlo cadangan reservoir minyak) [GSLIB, SGeMS] |
| Inverse Distance Weighting (IDW) | 🔵 Classic | O(n·m) | Interpolasi sederhana; bobot = 1/d^p (Contoh: Peta panas (heatmap) konsentrasi polutan PM 2.5 di kota) [QGIS, ArcGIS, scipy] |
| Natural Neighbor Interpolation | 🔵 Classic | O(n log n) | Sibson; via Voronoi weights (Contoh: Interpolasi mulus data kedalaman laut (batimetri)) [scipy.interpolate] |
| Thin Plate Spline (TPS) | 🔵 Classic | O(n³) | Smooth surface fit; minimum bending (Contoh: Warping citra satelit untuk mencocokkan peta digital) [scipy, R] |
| Radial Basis Function (RBF) | 🔵 Classic | O(n³) | General purpose spatial interpolation (Contoh: Rekonstruksi permukaan 3D dari hasil pindaian geologi) [scipy] |
| Triangulated Irregular Network (TIN) | 🔵 Classic | O(n log n) | Terrain model dari irregular points (Contoh: Pemodelan topografi lereng untuk simulasi aliran lahar) [QGIS, ArcGIS] |
| ANUDEM (Topo to Raster) | 🟢 Modern | O(n log n) | Hydrologically correct DEM (Contoh: Pembuatan model elevasi digital (DEM) sungai secara hidrologis) [ArcGIS, ANUDEM] |
| Nearest Neighbor Interpolation | 🔵 Classic | O(log n) per point | Simplest; assign nilai tetangga terdekat (Contoh: Resampling gambar peta satelit yang dizoom ekstrim) [All GIS tools] |
| Bilinear Interpolation | 🔵 Classic | O(1) per point | Interpolasi 4 grid cell neighbors (Contoh: Penghalusan raster suhu permukaan bumi) [Raster tools, GDAL] |
| Bicubic Interpolation | 🔵 Classic | O(1) per point | Smoother dari bilinear; 16 neighbors (Contoh: Scaling citra peta cuaca presisi tinggi) [GDAL, scipy] |
| Kernel Density Estimation (KDE) | 🔵 Classic | O(n·m) | Heatmap dari point events (Contoh: Pembuatan peta hotspot lokasi kecelakaan lalu lintas) [KDE in QGIS, scipy] |
| Two-dimensional KDE | 🟢 Modern | O(n·m) | 2D density surface; bandwidth selection (Contoh: Analisis sebaran habitat harimau sumatera dari kamera jebak) [scipy, seaborn, QGIS] |
Terrain & Elevation Analysis
| Algoritma | Era | Kompleksitas | Penggunaan |
|---|---|---|---|
| DEM Slope Calculation | 🔵 Classic | O(n) | Gradient dari elevation grid (Contoh: Pemetaan area rawan longsor berdasar tingkat kemiringan) [GDAL, QGIS, ArcGIS] |
| DEM Aspect Calculation | 🔵 Classic | O(n) | Arah slope (N/S/E/W); degree from north (Contoh: Analisis arah lereng untuk pemasangan panel surya) [GDAL, QGIS] |
| Hillshade Algorithm | 🔵 Classic | O(n) | Bayangan bukit untuk visualisasi relief (Contoh: Pemberian efek bayangan relief 3D pada peta cetak) [GDAL, ArcGIS] |
| Viewshed Analysis | 🔵 Classic | O(n·r) | Area yang visible dari titik tertentu (Contoh: Penempatan tower telekomunikasi agar sinyal tidak terhalang bukit) [GRASS, QGIS, ArcGIS] |
| Line-of-Sight | 🔵 Classic | O(r) | Binary visibility antara dua titik di terrain (Contoh: Perencanaan pandangan penembak jitu atau deteksi radar militer) [GRASS, ArcGIS] |
| Watershed Delineation (D8) | 🔵 Classic | O(n) | Flow direction + flow accumulation; D8 algorithm (Contoh: Penentuan daerah tangkapan air bendungan) [GRASS r.watershed, TauDEM] |
| D-infinity Flow Direction | 🟢 Modern | O(n) | Flow ke fraction of 8 neighbors; Tarboton (Contoh: Pemodelan aliran air tanah yang tidak kaku pada grid) [TauDEM, SAGA] |
| Fill Sinks (Wang & Liu) | 🟢 Modern | O(n log n) | Fill DEM depression sebelum watershed (Contoh: Memperbaiki cekungan data DEM agar simulasi air tidak terjebak) [GRASS, SAGA, TauDEM] |
| Priority-Flood Algorithm | 🟢 Modern | O(n log n) | Efficient DEM filling via priority queue (Contoh: Pembersihan artefak noise pada peta elevasi raksasa) [Barnes et al. (2014)] |
| Curvature (Profile/Planform) | 🟢 Modern | O(n) | Rate of change of slope; landslide mapping (Contoh: Deteksi area perlambatan aliran banjir di lembah) [GRASS, QGIS] |
| Topographic Wetness Index (TWI) | 🟢 Modern | O(n) | ln(a/tan β); wetness dari terrain (Contoh: Pemetaan lahan gambut atau kelembaban tanah) [SAGA, TauDEM] |
| Stream Power Index (SPI) | 🟢 Modern | O(n) | Erosion potential dari terrain (Contoh: Analisis potensi erosi tepi sungai) [SAGA] |
| Least-Cost Path on DEM | 🟢 Modern | O(n log n) | Optimal path considering terrain cost (Contoh: Perencanaan rute pembangunan pipa minyak menembus pegunungan) [GRASS r.cost, ArcGIS] |
| Sky View Factor | 🟢 Modern | O(n·r) | Fraction of sky visible; urban climate (Contoh: Analisis efek pulau bahang (urban heat island) di jalan sempit kota) [SAGA, RVT] |
| Solar Radiation Modeling | 🟢 Modern | O(n·t) | Solar insolation dari DEM; PVGIS (Contoh: Perkiraan panen energi sel surya atap dalam setahun) [GRASS r.sun, ArcGIS Solar Analyst] |
| Flood Inundation Modeling | 🟢 Modern | O(n) | Fill DEM dari sea level; simple flood (Contoh: Simulasi area tenggelam jika bendungan jebol) [GRASS, QGIS] |
| LiDAR Point Cloud Processing | 🟢 Modern | O(n log n) | Ground filtering, DSM/DTM dari LiDAR (Contoh: Pembuatan peta kontur dasar hutan lebat penebangan pohon) [LAStools, PDAL, CloudCompare] |
Remote Sensing & Raster Analysis
| Algoritma | Era | Kompleksitas | Penggunaan |
|---|---|---|---|
| Normalized Difference Vegetation Index (NDVI) | 🔵 Classic | O(n) | (NIR−Red)/(NIR+Red); vegetation health (Contoh: Pemantauan tingkat kesuburan dan masa panen padi) [GDAL, rasterio, Google Earth Engine] |
| NDWI (Water Index) | 🔵 Classic | O(n) | (Green−NIR)/(Green+NIR); water body (Contoh: Mendeteksi luasan genangan banjir dari satelit) [GEE, rasterio] |
| NDBI (Built-up Index) | 🔵 Classic | O(n) | (SWIR−NIR)/(SWIR+NIR); urban area (Contoh: Pemantauan perkembangan pesat pemukiman perkotaan) [GEE, rasterio] |
| EVI (Enhanced Vegetation Index) | 🟢 Modern | O(n) | Improved NDVI; atmospheric correction (Contoh: Analisis vegetasi tropis tanpa gangguan awan tipis) [MODIS EVI product] |
| Land Use Land Cover (LULC) Classification | 🟢 Modern | O(n·d) | Supervised classification citra satelit (Contoh: Pemetaan perubahan hutan menjadi sawit) [GEE, scikit-learn, eo-learn] |
| Image Segmentation (OBIA) | 🟢 Modern | O(n log n) | Object-Based Image Analysis; segment + classify (Contoh: Penghitungan jumlah pohon sawit otomatis dari foto udara) [eCognition, OTB, GRASS] |
| SNIC (Simple Non-Iterative Clustering) | 🟢 Modern | O(n) | Fast superpixel segmentation untuk remote sensing (Contoh: Memecah citra satelit menjadi superpixel petak sawah) [GEE] |
| ISODATA Classification | 🔵 Classic | O(n·k·iter) | Unsupervised; iterative cluster splitting/merging (Contoh: Clustering tutupan lahan otomatis tanpa data training) [ERDAS, ENVI] |
| Maximum Likelihood Classification | 🔵 Classic | O(n·k) | Supervised; probabilistic Bayesian (Contoh: Pemetaan jenis tanaman dengan statistik probabilitas) [ENVI, GDAL] |
| Random Forest for RS | 🟢 Modern | O(n·trees) | Ensemble supervised classification (Contoh: Prediksi area bekas kebakaran hutan secara akurat) [GEE, scikit-learn] |
| Support Vector Machine (SVM) for RS | 🟢 Modern | O(n²·d) | Classification citra satelit (Contoh: Klasifikasi lahan mineral dari citra hiperspektral) [ENVI, scikit-learn] |
| Change Detection (Image Differencing) | 🔵 Classic | O(n) | Subtract dua image waktu berbeda (Contoh: Evaluasi kerusakan bangunan sesudah gempa) [ERDAS, GEE] |
| Change Detection (CVA) | 🟢 Modern | O(n) | Change Vector Analysis; multi-band (Contoh: Analisis arah transisi hutan menjadi lahan tandus) [ENVI, R] |
| Principal Component Analysis (PCA) for RS | 🔵 Classic | O(n·d²) | Dimensionality reduction multi-band image (Contoh: Mereduksi puluhan band citra satelit Landsat) [ENVI, scikit-learn] |
| Atmospheric Correction (DOS) | 🔵 Classic | O(n) | Dark Object Subtraction; remove haze (Contoh: Menghilangkan efek kabut asap pada citra satelit) [GDAL, Py6S] |
| Orthorectification | 🟢 Modern | O(n) | Koreksi distorsi terrain + sensor (Contoh: Memperbaiki distorsi kemiringan foto udara drone) [GDAL, Agisoft Metashape] |
| Pansharpening | 🟢 Modern | O(n) | Fuse panchromatic + multispectral (Contoh: Mempertajam citra satelit warna menggunakan lensa hitam putih) [GDAL, Orfeo Toolbox] |
| SAR Processing (Backscatter) | 🟢 Modern | O(n log n) | Synthetic Aperture Radar analysis (Contoh: Pemetaan tumpahan minyak di laut saat malam hari) [SNAP, GDAL] |
| InSAR (Interferometric SAR) | 🟢 Modern | O(n log n) | Surface deformation; subsidence, earthquake (Contoh: Pemantauan penurunan muka tanah (subsidence) di Jakarta) [SNAP, GMTSAR, StaMPS] |
| Time Series Analysis (BFAST) | 🟢 Modern | O(n·t) | Breakpoint detection dalam vegetation time series (Contoh: Deteksi waktu pastinya penebangan liar terjadi) [BFAST (R), GEE] |
| Google Earth Engine (GEE) Processing | 🔥 Tren | Cloud | Massive RS analysis di cloud; petabytes (Contoh: Analisis deforestasi global skala petabyte dari cloud) [Google Earth Engine] |
| Cloud-Native RS (STAC + COG) | 🔥 Tren | Streaming | Analisis tanpa download via COG + STAC (Contoh: Streaming analisis citra satelit tanpa perlu download) [PySTAC, stackstac, odc-stac] |
| Deep Learning for RS (CNN/Transformer) | 🔥 Tren | O(n·d) | Deteksi bangunan, jalan, deforestation (Contoh: Ekstraksi otomatis footprint jalan dan bangunan) [torchgeo, eo-learn, RAMP] |
Topology & Spatial Relationships
| Algoritma | Era | Kompleksitas | Penggunaan |
|---|---|---|---|
| DE-9IM (Dimensionally Extended 9-Intersection Model) | 🔵 Classic | O(n·m) | Model relasi topologi antar geometri (Contoh: Validasi integritas input batas administrasi daerah) [JTS, GEOS, PostGIS] |
| Point-in-Polygon (Topology) | 🔵 Classic | O(n) | Contains, Within relationship (Contoh: Mengecek apakah restoran masuk radius pengiriman promo) [PostGIS ST_Contains] |
| Polygon Contains Point | 🔵 Classic | O(n) | Apakah polygon contain titik (Contoh: Dasar logika hit test kursor di map UI) [All GIS tools] |
| Polygon Touches | 🔵 Classic | O(n·m) | Dua polygon share boundary, tidak overlap (Contoh: Mengecek lahan yang bersinggungan tanpa sengketa) [PostGIS ST_Touches] |
| Polygon Overlaps | 🔵 Classic | O(n·m) | Partial overlap dua polygon (Contoh: Mencari luasan sengketa antara dua izin tambang) [PostGIS ST_Overlaps] |
| Polygon Crosses | 🔵 Classic | O(n·m) | Line cross polygon boundary (Contoh: Mendeteksi jalan tol yang melintasi sungai) [PostGIS ST_Crosses] |
| ST_Intersects | 🟢 Modern | O(log n) | Spatial intersect dengan R-Tree (Contoh: Kueri SQL cepat mencari persil lahan di radius 1km) [PostGIS, Shapely] |
| ST_DWithin | 🟢 Modern | O(log n) | Titik dalam radius d (Contoh: Fitur radius pencarian ATM terdekat di mobile app) [PostGIS] |
| Spatial Network Topology | 🟢 Modern | O(E log V) | Node-edge topology untuk routing (Contoh: Pembuatan graf rute navigasi jalan OSRM) [pgRouting, NetworkX] |
| Snap to Grid | 🔵 Classic | O(n) | Quantize koordinat ke grid (Contoh: Merapikan ujung-ujung poligon digitasi manual) [GDAL, Shapely] |
| Topology Clean-up | 🟢 Modern | O(n log n) | Fix gaps, slivers, overlaps dalam polygon dataset (Contoh: Memperbaiki gap atau sliver pada peta tata ruang otomatis) [QGIS Topology Checker] |
| Planar Graph Embedding | 🔵 Classic | O(n) | Embed graph di plane tanpa crossing edges (Contoh: Pemodelan desain jaringan sirkuit listrik cetak) [CGAL, computational topology] |
| Euler Number Computation | 🔵 Classic | O(n) | V − E + F = 2 untuk planar graph (Contoh: Mendeteksi jumlah danau di dalam suatu wilayah poligon) [Topology] |
Point Cloud Processing
| Algoritma | Era | Kompleksitas | Penggunaan |
|---|---|---|---|
| Ground Filtering (PMF) | 🟢 Modern | O(n) | Progressive Morphological Filter; LiDAR ground (Contoh: Memisahkan data tanah dari pohon pada scan LiDAR hutan) [LAStools, PDAL] |
| Ground Filtering (CSF) | 🟢 Modern | O(n) | Cloth Simulation Filter; drape cloth dari atas (Contoh: Ekstraksi DTM (Digital Terrain Model) dari survei drone) [CSF library] |
| Ground Filtering (SMRF) | 🟢 Modern | O(n log n) | Simple Morphological Filter (Contoh: Penyaringan vegetasi lebat untuk topografi kontur) [PDAL] |
| Normal Estimation from Point Cloud | 🟢 Modern | O(n log n) | Estimasi surface normal via PCA (Contoh: Deteksi orientasi bidang untuk pendaratan drone otomatis) [Open3D, PCL] |
| FPFH Descriptor | 🟢 Modern | O(n·k²) | Fast Point Feature Histogram; registration feature (Contoh: Fitur pencocokan scan 3D ruang tamu untuk AR/VR) [PCL, Open3D] |
| ICP (Iterative Closest Point) | 🟢 Modern | O(n²) per iter | Align dua point cloud (Contoh: Menggabungkan hasil pindaian scan wajah 3D) [Open3D, PCL] |
| Point Cloud Segmentation (RANSAC plane) | 🟢 Modern | O(iter·n) | Deteksi plane dari point cloud (Contoh: Mendeteksi dinding dan lantai gedung dari data scan robot) [Open3D, PCL] |
| Euclidean Cluster Extraction | 🟢 Modern | O(n log n) | Cluster point cloud berdasarkan jarak (Contoh: Menghitung jumlah mobil yang lewat di gerbang tol otomatis) [PCL, Open3D] |
| Voxel Grid Downsampling | 🟢 Modern | O(n) | Reduce point cloud density via voxel (Contoh: Meringankan render file LiDAR 10 GB menjadi 100 MB di browser) [Open3D, PDAL] |
| Statistical Outlier Removal | 🟢 Modern | O(n log n) | Remove noise points; mean + std dev (Contoh: Membersihkan noise nyamuk/hujan dari scan laser LiDAR) [Open3D, PCL] |
| Radius Outlier Removal | 🟢 Modern | O(n log n) | Remove sparse points (Contoh: Pembersihan artefak pinggiran pada kamera Kinect) [Open3D] |
| 3D Reconstruction from Point Cloud | 🟢 Modern | O(n log n) | Surface mesh dari LiDAR/photogrammetry (Contoh: Membuat model game 3D dari patung bersejarah) [Meshlab, Open3D] |
| Building Extraction from LiDAR | 🟢 Modern | O(n log n) | Detect building footprint dari aerial LiDAR (Contoh: Pembuatan model 3D kota otomatis untuk simulasi) [LAStools + custom] |
| Tree Detection from LiDAR | 🟢 Modern | O(n log n) | Individual tree segmentation (Contoh: Penghitungan stok karbon per individu pohon di hutan lindung) [lidR (R), PDAL] |
| PointNet / PointNet++ | 🔥 Tren | O(n·d) | Deep learning langsung pada point cloud (Contoh: Deteksi rintangan objek oleh mobil self-driving) [PointNet (Qi et al. 2017)] |
| VoxelNet | 🔥 Tren | O(n·d) | 3D object detection dari LiDAR (Contoh: Sistem deteksi mobil dan pedestrian LiDAR real-time 3D) [VoxelNet, OpenPCDet] |
Geospatial Network Analysis
| Algoritma | Era | Kompleksitas | Penggunaan |
|---|---|---|---|
| Betweenness Centrality (Spatial) | 🔵 Classic | O(V·E) | Identifikasi node kritis dalam road network (Contoh: Mencari jalan arteri yang paling rentan macet parah) [NetworkX, igraph] |
| Closeness Centrality (Spatial) | 🔵 Classic | O(V²) | Aksesibilitas node; rata-rata jarak ke semua (Contoh: Menentukan lokasi pembangunan rumah sakit baru) [NetworkX] |
| Service Area Analysis | 🟢 Modern | O(V log V) | Area yang terjangkau dari titik dalam waktu t (Contoh: Pemetaan wilayah layan puskesmas dalam 15 menit) [pgRouting, NetworkX, ArcGIS] |
| Origin-Destination Matrix | 🔵 Classic | O(V² log V) | Cost antara semua pasang O-D (Contoh: Perhitungan matriks ongkir 10 gudang ke 1000 titik) [pgRouting, OSRM matrix API] |
| Gravity Model | 🔵 Classic | O(n²) | Interaksi antar lokasi = massa/jarak² (Contoh: Estimasi pergerakan penumpang KRL antar stasiun) [Spatial interaction models] |
| Space Syntax | 🟢 Modern | O(V²) | Analisis urban connectivity; integration, depth (Contoh: Perancangan desain sirkulasi pejalan kaki di mal) [depthmapX, Space Syntax Toolkit] |
| Network Centrality for Urban | 🟢 Modern | O(V·E) | Urban street network analysis (Contoh: Analisis tata ruang perumahan ke jalan raya) [OSMnx (Boeing 2017)] |
| Alpha Centrality | 🟢 Modern | O(V²) | PageRank-like untuk spatial network (Contoh: Analisis rute pelarian evakuasi di gedung) [NetworkX] |
| Stochastic User Equilibrium (SUE) | 🟢 Modern | O(iter·E) | Traffic assignment model (Contoh: Model kemacetan lalu lintas tol harian) [TransCAD, SUMO] |
| Dynamic Traffic Assignment (DTA) | 🟢 Modern | O(T·E log V) | Time-varying traffic assignment (Contoh: Simulasi pengalihan arus lalu lintas saat kecelakaan) [DynusT, MATSIM] |
| Corridor Analysis | 🟢 Modern | O(n log n) | Least-cost corridor antara habitat patch (Contoh: Perencanaan koridor lintas satwa gajah antar cagar alam) [GRASS, Linkage Mapper] |
| Connectivity Analysis (Circuit Theory) | 🟢 Modern | O(n³) | Habitat connectivity via electrical resistance (Contoh: Analisis sirkuit ekologi migrasi satwa liar) [Circuitscape] |
| MCDA Site Suitability | 🔵 Classic | O(n) | Multi-Criteria Decision Analysis untuk site (Contoh: Pembobotan kriteria untuk pemilihan lahan TPA sampah) [QGIS, ArcGIS ModelBuilder] |
| MaxP Regionalization | 🟢 Modern | O(n²·iter) | Spatially contiguous region dengan max p regions (Contoh: Membentuk batas daerah pemilihan (Dapil) pemilu) [PySAL regionalization] |
| REDCAP Regionalization | 🟢 Modern | O(n²) | Regional spatial clustering (Contoh: Mengelompokkan desa miskin bertetangga menjadi satu klaster) [PySAL] |
Geocoding & Address Algorithms
| Algoritma | Era | Kompleksitas | Penggunaan |
|---|---|---|---|
| Forward Geocoding | 🔵 Classic | O(log n) | Address → koordinat lat/lng (Contoh: Mencari kordinat latitude dari teks 'Jalan Sudirman 10') [Nominatim, Photon, Google Geocoding] |
| Reverse Geocoding | 🔵 Classic | O(log n) | Koordinat → address (Contoh: Menampilkan 'Anda sedang berada di Kemang' berdasar GPS) [Nominatim, Google Reverse Geocoding] |
| Fuzzy Address Matching | 🟢 Modern | O(n·m) | Match address string dengan toleransi typo (Contoh: Toleransi saat user typo nama kelurahan di e-commerce) [libpostal, Pelias] |
| Address Parsing | 🟢 Modern | O(n) | Parse komponen address (street, city, zip) (Contoh: Otomatis memisahkan kode pos, RT/RW, dan jalan dari teks) [libpostal, usaddress] |
| Interpolation Geocoding | 🔵 Classic | O(log n) | Interpolasi nomor rumah di antara dua titik (Contoh: Memperkirakan posisi rumah nomor 12 di antara blok 1 dan 20) [TIGER/Line, Nominatim] |
| Rooftop Geocoding | 🟢 Modern | O(log n) | Koordinat tepat di atap gedung (Contoh: Menentukan kordinat persis pintu masuk gedung untuk ojol) [Google Geocoding, HERE] |
| Semantic Place Search | 🔥 Tren | O(log n) | NLP-based place search; "coffee near park" (Contoh: Mencari 'Restoran Padang terdekat yang buka 24 jam') [Overture Maps, Google Places] |
| What3Words Encoding | 🟢 Modern | O(1) | 3mx3m cell → 3 unique words (Contoh: Pelaporan lokasi kecelakaan tol kepada polisi) [W3W API] |
| Plus Codes (OpenLocationCode) | 🟢 Modern | O(1) | Open standard lokasi; 6m² per code (Contoh: Pembuatan alamat digital gubuk perkampungan padat) [Google Open Location Code] |
| MGRS (Military Grid Reference) | 🔵 Classic | O(1) | Military coordinate system; UTM-based (Contoh: Kordinasi titik pengeboman standar militer NATO) [pyproj, MGRS library] |
Spatial Clustering & Pattern Detection
| Algoritma | Era | Kompleksitas | Penggunaan |
|---|---|---|---|
| DBSCAN (Density-Based Spatial) | 🔵 Classic | O(n log n) | Cluster GPS points; arbitrary shape (Contoh: Deteksi hotspot penyebaran virus berdasar kerumunan GPS) [scikit-learn, HDBSCAN] |
| HDBSCAN | 🟢 Modern | O(n log n) | Hierarchical DBSCAN; auto cluster count (Contoh: Segmentasi lokasi nongkrong driver ojol otomatis) [hdbscan library] |
| ST-DBSCAN (Spatio-Temporal) | 🟢 Modern | O(n log n) | DBSCAN dengan dimensi waktu (Contoh: Analisis pola kriminalitas malam hari di wilayah tertentu) [ST-DBSCAN implementation] |
| OPTICS | 🟢 Modern | O(n log n) | Ordering untuk cluster reachability (Contoh: Menemukan klaster pelabuhan kecil di sepanjang kepulauan) [scikit-learn] |
| K-Means Spatial | 🔵 Classic | O(n·k·iter) | Cluster spatial points ke k group (Contoh: Membagi area 5 armada kurir secara merata) [scikit-learn] |
| Spatial K-Means (Lloyd + haversine) | 🟢 Modern | O(n·k·iter) | K-Means dengan spherical distance (Contoh: Menentukan lokasi optimal 5 gudang logistik) [Custom implementation] |
| PAM (K-Medoids) | 🔵 Classic | O(n²·k) | Robust K-means; actual data point sebagai center (Contoh: Menentukan rumah warga untuk titik kumpul evakuasi aktual) [sklearn-extra] |
| Hierarchical Clustering (Spatial) | 🔵 Classic | O(n² log n) | Agglomerative dengan spatial distance matrix (Contoh: Analisis persebaran suku linguistik suatu kepulauan) [scipy.cluster] |
| SaTScan (Spatial Scan Statistic) | 🟢 Modern | O(n²) | Detect disease cluster / hot spot (Contoh: Surveilans deteksi dini lonjakan kasus DBD) [SaTScan software] |
| Kulldorff's Scan Statistic | 🟢 Modern | O(n²) | Circular window scan untuk anomaly (Contoh: Pemindaian area anomali penderita kanker (epidemiologi)) [SaTScan] |
| AMOEBA (Adaptive Moving Average) | 🟢 Modern | O(n²) | Adaptive cluster boundary detection (Contoh: Mendeteksi bentuk batas kantong kemiskinan kota) [PySAL] |
| Quadrat Analysis | 🔵 Classic | O(n) | Point pattern: random/clustered/regular (Contoh: Menganalisis sebaran pohon di hutan acak atau bergerombol) [Spatial stats] |
| Ripley's K-Function | 🔵 Classic | O(n²) | Multi-scale spatial point pattern analysis (Contoh: Menganalisis radius persaingan minimarket di kota besar) [spatstat (R), PySAL] |
| Nearest Neighbor Index | 🔵 Classic | O(n log n) | Ratio observed/expected NN distance (Contoh: Mengetahui pola sebaran sumur minyak) [ArcGIS, spatstat] |
| Trajectory Clustering | 🟢 Modern | O(n²) | Cluster GPS tracks berdasarkan similarity (Contoh: Mengenali pola lintasan utama kapal laut) [t-DBSCAN, TraClus] |
| Hotspot Analysis (Getis-Ord Gi*) | 🟢 Modern | O(n²) | Statistically significant hot/cold spots (Contoh: Peta visual zona rawan pencurian sepeda motor) [ArcGIS, PySAL] |
| Emerging Hotspot Analysis | 🔥 Tren | O(n²·t) | Hotspot yang berkembang dari waktu ke waktu (Contoh: Memprediksi area tren peningkatan pengangguran) [ArcGIS Pro] |
13. String & Text Processing
String Structures
| Algoritma | Era | Kompleksitas | Penggunaan |
|---|---|---|---|
| Trie | 🔵 Classic | O(m) | Autocomplete, spell check, IP routing |
| Suffix Tree (Ukkonen's) | 🔵 Classic | O(n) | Bioinformatics, full-text search |
| Suffix Automaton | 🔵 Classic | O(n) | Substring counting, LCS |
| Ternary Search Trie | 🟢 Modern | O(log n) | Autocomplete, symbol tables |
| FM-Index | 🟢 Modern | O(m log n) | Genome alignment, bioinformatics |
| Patricia Trie (Radix Tree) | 🔵 Classic | O(k) | Trie terkompresi hemat memori |
| Manacher's Algorithm | 🔵 Classic | O(n) | Menemukan palindrom terpanjang dalam string |
NLP Algorithms
| Algoritma | Era | Kompleksitas | Penggunaan |
|---|---|---|---|
| TF-IDF | 🔵 Classic | O(nd) | Search engine, information retrieval |
| BM25 | 🟢 Modern | O(n) | Elasticsearch, search engines |
| Word2Vec | 🟢 Modern | O(n·w·d) | NLP, semantic similarity |
| FastText | 🟢 Modern | O(n·w·d) | Multilingual NLP |
| Byte Pair Encoding (BPE) | 🟢 Modern | O(n·v) | GPT, BERT, semua LLM tokenizer |
| BERT / RoBERTa | 🟢 Modern | O(n²d) | NLP semua task |
| GPT Architecture | 🟢 Modern | O(n²d) | LLM, text generation |
| RAG (Retrieval-Augmented Generation) | 🟢 Modern | O(n·k) | Enterprise AI, knowledge bases |
| WordPiece / SentencePiece | 🟢 Modern | O(n) | Subword tokenization yang digunakan BERT/T5 |
14. Scheduling & Systems
CPU Scheduling
| Algoritma | Era | Kompleksitas | Penggunaan |
|---|---|---|---|
| FIFO / FCFS | 🔵 Classic | O(1) | Batch processing |
| Round Robin | 🔵 Classic | O(n) | OS process scheduling |
| SJF / SRTF | 🔵 Classic | O(n log n) | Batch job scheduling |
| Priority Scheduling | 🔵 Classic | O(log n) | Real-time OS, QoS |
| EDF (Earliest Deadline First) | 🔵 Classic | O(n log n) | Real-time OS, multimedia |
| CFS (Completely Fair Scheduler) | 🟢 Modern | O(log n) | Linux kernel default |
Task & Job Scheduling
| Algoritma | Era | Kompleksitas | Penggunaan |
|---|---|---|---|
| List Scheduling | 🔵 Classic | O(n log n) | Parallel computing |
| Critical Path Method (CPM/PERT) | 🔵 Classic | O(V + E) | Project management |
| Job Shop Scheduling | 🔵 Classic | NP-hard | Manufacturing, operations research |
| Disk Scheduling (SCAN/C-SCAN) | 🔵 Classic | O(n log n) | Pengaturan pergerakan head disk |
Memory Management
| Algoritma | Era | Kompleksitas | Penggunaan |
|---|---|---|---|
| LRU Cache | 🔵 Classic | O(1) | CPU cache, web cache, CDN |
| LFU Cache | 🔵 Classic | O(1) | Cache replacement |
| ARC Cache | 🟢 Modern | O(1) | ZFS, storage systems |
| Mark-and-Sweep GC | 🔵 Classic | O(n) | Java GC, JavaScript V8 |
| Generational GC | 🟢 Modern | O(n_young) | JVM, .NET CLR, Python |
| Clock Page Replacement | 🔵 Classic | O(1) | Aproksimasi praktis LRU untuk OS |
| MVCC | 🟢 Modern | O(1) | Kontrol konkurensi non-blocking database modern |
15. Distributed Systems
Consensus & Coordination
Visualisasi interaktif di bawah membedah mekanisme konsensus Raft—mulai dari proses pemilihan pemimpin (Leader Election via RequestVote RPC) hingga replikasi entri log transaksi terdistribusi secara konsisten (Log Replication via AppendEntries RPC):
| Algoritma | Era | Kompleksitas | Penggunaan |
|---|---|---|---|
| Paxos | 🔵 Classic | O(n) | Chubby, Zookeeper |
| Raft | 🟢 Modern | O(n) | etcd, TiKV, CockroachDB |
| PBFT (Practical Byzantine Fault Tolerance) | 🔵 Classic | O(n²) | Blockchain, distributed ledger |
| Viewstamped Replication | 🔵 Classic | O(n) | Distributed databases |
| Zab (Zookeeper Atomic Broadcast) | 🟢 Modern | O(n) | Apache Zookeeper |
| SWIM Protocol | 🟢 Modern | O(1) | Protokol keanggotaan kelompok terdistribusi berbasis gosip |
Hashing & Partitioning
| Algoritma | Era | Kompleksitas | Penggunaan |
|---|---|---|---|
| Consistent Hashing | 🟢 Modern | O(log n) | Cassandra, DynamoDB, CDN |
| Rendezvous Hashing | 🟢 Modern | O(n) | Content distribution |
| Jump Hash | 🟢 Modern | O(log n) | Google internal sharding |
| Maglev Hashing | 🔴 Research | O(n log n) | Google Maglev load balancer |
Clock & Ordering
| Algoritma | Era | Kompleksitas | Penggunaan |
|---|---|---|---|
| Lamport Timestamps | 🔵 Classic | O(1) | Distributed systems, causality |
| Vector Clocks | 🔵 Classic | O(n) | Dynamo, Riak, Voldemort |
| Hybrid Logical Clock (HLC) | 🟢 Modern | O(1) | CockroachDB, yugabyte |
| TrueTime (Google) | 🔴 Research | O(1) | Google Spanner |
| Chandy-Lamport Algorithm | 🔵 Classic | O(e) | Pengambilan snapshot terdistribusi yang konsisten |
| Bully Algorithm | 🔵 Classic | O(n²) | Pemilihan pemimpin terdistribusi |
Replication & Consistency
| Algoritma | Era | Kompleksitas | Penggunaan |
|---|---|---|---|
| Two-Phase Commit (2PC) | 🔵 Classic | O(n) | Distributed transactions |
| Three-Phase Commit (3PC) | 🔵 Classic | O(n) | Distributed transactions |
| Merkle Tree | 🔵 Classic | O(log n) | Git, Bitcoin, distributed sync |
| Gossip Protocol | 🟢 Modern | O(log n) | Cassandra, membership, health |
| CRDT (Conflict-free Replicated Data Types) | 🟢 Modern | O(1) | Collaborative editing, Riak |
16. AI & Decision Making
Reinforcement Learning
| Algoritma | Era | Kompleksitas | Penggunaan |
|---|---|---|---|
| Q-Learning | 🔵 Classic | O(|S|·|A|) | Game AI, robotics |
| SARSA | 🔵 Classic | O(|S|·|A|) | RL pada masalah kontinu |
| MCTS (Monte Carlo Tree Search) | 🔵 Classic | O(iter) | Board games, planning, LLM decoding |
| DQN (Deep Q-Network) | 🟢 Modern | O(n·d) | Game AI, Atari |
| PPO (Proximal Policy Optimization) | 🟢 Modern | O(n·d) | ChatGPT RLHF, robotics, games |
| SAC (Soft Actor-Critic) | 🟢 Modern | O(n·d) | Continuous control, robotics |
| AlphaZero / MuZero | 🔴 Research | O(b^d) | Board games, planning |
Classical AI Search
| Algoritma | Era | Kompleksitas | Penggunaan |
|---|---|---|---|
| Minimax | 🔵 Classic | O(b^d) | Board games AI |
| Alpha-Beta Pruning | 🔵 Classic | O(b^(d/2)) | Chess engines |
| Expectimax | 🔵 Classic | O(b^d) | Stochastic games, Pacman |
| Uniform Cost Search (UCS) | 🔵 Classic | O(b^(1 + [C*/ε])) | Pencarian rute terpendek graf berbobot dasar AI |
| Iterative Deepening DFS (IDDFS) | 🔵 Classic | O(b^d) | Pencarian kombinasi efisiensi ruang DFS dan kelengkapan BFS |
| Beam Search | 🔵 Classic | O(B · L) | Pencarian heuristik dengan lebar terbatas untuk LLM decoding |
| POMDP Planning | 🔴 Research | O(exp) | Autonomous driving, robotics |
Planning
| Algoritma | Era | Kompleksitas | Penggunaan |
|---|---|---|---|
| STRIPS / PDDL | 🔵 Classic | O(exp) | AI planning systems |
| FastForward (FF) | 🟢 Modern | O(n) | AI planning benchmarks |
| RRT / RRT* | 🟢 Modern | O(n log n) | Robot motion planning |
| PRM (Probabilistic Roadmap) | 🟢 Modern | O(n log n) | Robot path planning |
17. Bioinformatics
Sequence Analysis
| Algoritma | Era | Kompleksitas | Penggunaan |
|---|---|---|---|
| Smith-Waterman | 🔵 Classic | O(mn) | DNA alignment, BLAST |
| Needleman-Wunsch | 🔵 Classic | O(mn) | Protein alignment |
| BLAST | 🟢 Modern | O(mn/w) | NCBI database search |
| Bowtie / BWA | 🟢 Modern | O(m) | Genome sequencing alignment |
| HISAT2 | 🟢 Modern | O(m log n) | RNA-seq, transcriptomics |
| Hirschberg's Algorithm | 🔵 Classic | O(mn) | Global alignment hemat memori |
| ClustalW | 🟢 Modern | O(n²) | Phylogenetics, MSA |
| MUSCLE | 🟢 Modern | O(n² log n) | Multiple sequence alignment |
Assembly & Annotation
| Algoritma | Era | Kompleksitas | Penggunaan |
|---|---|---|---|
| OLC Assembly | 🔵 Classic | O(n²) | Long-read genome assembly |
| De Bruijn Graph Assembly | 🟢 Modern | O(n) | NGS genome assembly |
| Viterbi Algorithm | 🔵 Classic | O(T·K²) | Hidden Markov Model, gene prediction |
| CRF (Conditional Random Field) | 🟢 Modern | O(T·K²) | NER, gene annotation |
Structural & Evolutionary
| Algoritma | Era | Kompleksitas | Penggunaan |
|---|---|---|---|
| Neighbor Joining | 🔵 Classic | O(n³) | Evolutionary biology, phylogenetics |
| UPGMA / WPGMA | 🔵 Classic | O(n²) | Phylogenetics |
| Rosetta | 🟢 Modern | O(n³) | Protein design, drug discovery |
| Fitch's Algorithm | 🔵 Classic | O(N) | Rekonstruksi status leluhur pada pohon filogenetik |
| AlphaFold2 | 🔴 Research | O(n²) | Protein structure prediction, drug discovery |
Ringkasan Statistik
| Kategori | Jumlah Algoritma |
|---|---|
| Sorting & Ordering | 64 |
| Searching | 88 |
| Graph Algorithms | 23 |
| Dynamic Programming | 15 |
| Machine Learning | 26 |
| Deep Learning | 27 |
| Cryptography | 22 |
| Optimization | 90 |
| Compression & Coding | 21 |
| Number Theory & Math | 18 |
| Computational Geometry | 181 |
| Geospatial & Spatial Analysis | 223 |
| String & Text Processing | 16 |
| Scheduling & Systems | 17 |
| Distributed Systems | 21 |
| AI & Decision Making | 16 |
| Bioinformatics | 17 |
| Total | 885 |
Referensi & Sumber Lanjutan:
- CLRS — Introduction to Algorithms (Cormen et al.)
- Algorithm Design (Kleinberg & Tardos)
- The Art of Computer Programming (Knuth)
- Papers With Code — paperswithcode.com
- NIST Post-Quantum Cryptography — csrc.nist.gov