Algorithms (2) Flashcards
Topics covered: More on algorithm complexity Binary search Brute force Greedy algorithm - able to apply algorithm analysis techniques to problem-solving.
Komponen Algoritma
Struktur Data: Menyimpan informasi.
Instruksi: Mengubah nilai data.
Ekspresi Kondisional: Membuat keputusan.
Struktur Kontrol: Menjalankan keputusan.
Modul: Membantu abstraksi dan manajemen algoritma.
Jenis Kompleksitas
Waktu (Time Complexity): Jumlah langkah eksekusi.
Ruang (Space Complexity): Memori yang digunakan.
Kompleksitas Waktu
Fungsi š(š) yang menyatakan jumlah operasi maksimum untuk input berukuran n.
Notasi Big-O
mengukur seberapa cepat atau efisien sebuah algoritma bekerja berdasarkan jumlah inputnya.
Kenapa Notasi Big O Penting?
Notasi Big O membantu kita menjawab pertanyaan seperti:
ā
Seberapa cepat algoritma bekerja jika jumlah data bertambah?
ā
Mana algoritma yang lebih efisien saat menangani data dalam jumlah besar?
O(1)
Konstan
Operasi sederhana (akses elemen array).
Misalnya, kamu langsung mengambil mie dari lemari dapur. Waktu yang dibutuhkan tetap sama, tidak peduli berapa banyak mie yang ada di lemari.
O(log n)
Logaritmik
Pencarian biner dalam daftar terurut.
Misalnya, kamu ingin mencari kata dalam kamus. Kamu tidak membuka satu per satu halaman dari awal, tetapi langsung melompat ke tengah, lalu ke bagian kiri atau kanan sampai menemukan kata yang dicari.
O(n)
Linear
Misalnya, kamu sedang mencari kunci di dalam tas. Kamu harus memeriksa satu per satu sampai menemukannya. Semakin banyak barang di dalam tas, semakin lama waktu yang dibutuhkan.
š” Contoh dalam pemrograman:
Linear Search (pencarian dalam daftar tidak terurut).
Menjumlahkan semua angka dalam array.
O(n log n)
Linearithmic
Misalnya, kamu sedang menyusun kartu remi berdasarkan angka. Kamu membagi kartu menjadi beberapa kelompok kecil, menyusun masing-masing kelompok, lalu menggabungkannya.
š” Contoh dalam pemrograman:
Merge Sort atau Quick Sort (algoritma sorting yang lebih efisien).
O(nĀ²)
Kuadratik
Misalnya, kamu sedang menyusun tim sepak bola dari sekelompok teman. Kamu harus membandingkan setiap orang dengan yang lain satu per satu untuk memastikan strategi terbaik. Jika jumlah teman bertambah, waktu yang dibutuhkan bertambah drastis.
š” Contoh dalam pemrograman:
Bubble Sort, Selection Sort (algoritma sorting yang lambat).
O(2āæ)
Eksponensial
Misalnya, kamu harus memilih pakaian untuk 10 hari ke depan, tetapi setiap hari kamu bisa memilih 2 jenis pakaian yang berbeda. Jumlah kombinasi yang harus dipertimbangkan akan bertambah dengan sangat cepat.
š” Contoh dalam pemrograman:
Brute-force dalam pemecahan masalah kombinatorial.
Algoritma rekursif Fibonacci tanpa optimasi.
O(n!)
Faktorial
Misalnya, kamu ingin menyusun 10 buku dalam rak tetapi bisa menaruhnya dalam urutan apa saja. Jumlah kemungkinan urutan yang bisa terjadi akan sangat besar.
š” Contoh dalam pemrograman:
Traveling Salesman Problem (TSP) dengan brute-force.
Binary Search
menemukan elemen dalam daftar yang sudah terurut.
bekerja dengan cara membagi daftar menjadi dua bagian, lalu membandingkan elemen tengah dengan target. Jika elemen tengah bukan target, pencarian berlanjut ke bagian kiri atau kanan daftar hingga elemen ditemukan atau tidak ada lagi yang bisa diperiksa.
keunggulan binary search
Cepat (O(log n)), cocok untuk data besar
kekurangan binary search
Hanya untuk data terurut
contoh binary search
Mencari nomor telepon di buku kontak
keunggulan greedy algorithm
Mudah & cepat, cocok untuk masalah besar
kekurangan greedy algoritme
Tidak selalu optimal. Bisa jadi keputusan awal yang serakah membuat solusi akhir kurang baik.
Tidak cocok untuk masalah yang butuh perhitungan ulang (seperti TSP atau penyusunan jadwal kompleks).
keunggulan brute force
Pasti benar (dapat menemukan solusi), mudah dipahami
kekurangan brute force
Lambat, boros waktu dan daya
contoh brute force
Mencari password, kombinasi optimal
