Belajar Algoritm - Apa Itu Algoritma & Korektivitas

#Pendahuluan

Setelah di episode 0 kita menyiapkan environment dan memastikan skill dasar terpenuhi — rekursi, manipulasi array, dan penghitungan Big-O — pada episode ini kita menarik napas sejenak dari coding dan memahami apa sebenarnya algoritma itu. Definisi yang tepat akan menjadi fondasi pemahaman kalian di 26 episode ke depan.

Mengapa harus memahami definisi algoritma? Karena banyak programmer menulis kode yang "bekerja" tanpa memahami apakah langkah-langkahnya memenuhi syarat sebagai algoritma yang benar. Tanpa definisi yang jelas, kalian tidak bisa membuktikan bahwa solusi kalian benar — dan optimasi atas solusi yang salah hanya menghasilkan kode yang lebih cepat tetapi tetap salah.

#Definisi Formal Algoritma

Algoritma adalah urutan langkah-langkah terbatas dan deterministik untuk menyelesaikan masalah tertentu. Setiap langkah harus jelas (definiteness), prosesnya harus berakhir (finiteness), dan setiap langkah harus dapat dieksekusi (effectivity).

Properti	Arti
Input	Nol atau lebih nilai yang diterima dari luar
Output	Satu atau lebih nilai yang dihasilkan
Definiteness	Setiap langkah harus didefinisikan secara tepat, tidak ambigu
Finiteness	Algoritma harus berakhir dalam jumlah langkah terbatas
Effectiveness	Setiap langkah harus cukup dasar untuk bisa dieksekusi

Perhatikan bahwa "efektif" berarti langkah-langkahnya harus grundlegend — kalian tidak bisa memasukkan "selesaikan masalah NP-lengkap" sebagai satu langkah dalam algoritma. Setiap operasi harus bisa dilakukan secara konkret.

Note

Bedakan algoritma dari program. Algoritma adalah ide abstrak — urutan langkah logis. Program adalah implementasi algoritma dalam bahasa pemrograman tertentu. Satu algoritma bisa diimplementasikan dalam banyak bahasa.

#Korektivitas: Benar Sebelum Cepat

Korektivitas (correctness) adalah properti paling mendasar dari sebuah algoritma. Algoritma yang tidak benar tidak berguna seberapa cepat pun ia berjalan. Prinsipnya sederhana: buktikan benar dulu, baru optimasi.

#Loop Invariant

Loop invariant adalah kondisi yang selalu benar sebelum dan sesudah setiap iterasi loop. Ini adalah alat utama untuk membuktikan korektivitas algoritma berbasis loop.

Pola pembuktian menggunakan loop invariant:

Inisialisasi: loop invariant benar sebelum iterasi pertama.
Maintenance: jika benar sebelum iterasi, maka benar juga sesudahnya.
Termination: ketika loop berhenti, invariant memberikan properti berguna yang membuktikan algoritma benar.

Contoh konkret — linear search:

python

def linear_search(arr, target):
    # Invariant: arr[0..i-1] tidak mengandung target
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1

Inisialisasi: i = 0, arr[0..-1] kosong → invariant terpenuhi.
Maintenance: jika arr[i] != target, maka arr[0..i] tidak mengandung target → invariant terpenuhi untuk iterasi berikutnya.
Termination: loop berhenti ketika i == len(arr) → seluruh array tidak mengandung target → return -1 benar.

#Postcondition

Postcondition adalah kondisi yang dijamin benar setelah algoritma selesai berjalan. Ini berhubungan langsung dengan spesifikasi masalah — postcondition harus setara dengan "masalah selesai".

Contoh: postcondition dari binary search adalah "jika target ada, return indeksnya; jika tidak, return -1". Jika postcondition ini terpenuhi untuk semua kemungkinan input, algoritma dikatakan benar.

#Identifikasi Bug tanpa Kode

Salah satu latihan paling berguna adalah menemukan bug pada algoritma dari deskripsi tanpa kode. Ini melatih pemahaman konseptual:

"Untuk mencari elemen dalam array terurut, mulai dari tengah. Jika tengah lebih kecil dari target, cari di kanan. Jika lebih besar, cari di kiri. Ulangi sampai ketemu."

Bug-nya? Tidak ada base case untuk recursive version, dan tidak ada penanganan ketika low > high. Tanpa loop invariant yang jelas, bug ini sulit ditemukan — itulah mengapa invariant penting.

#Praktik: Analisis Korektivitas

Coba analisis korektivitas dari dua algoritma berikut:

Algoritma A — mencari maksimum:

python

def find_max(arr):
    maximum = arr[0]
    for x in arr[1:]:
        if x > maximum:
            maximum = x
    return maximum

Loop invariant: maximum adalah nilai maksimum dari arr[0..i-1]. Inisialisasi benar (arr[0]), maintenance benar (update jika x > maximum), termination benar (return maximum = maksimum seluruh array).

Algoritma B — mencoba mencari maksimum dengan shortcut:

python

def find_max_buggy(arr):
    for i in range(len(arr)):
        if arr[i] > arr[i + 1]:  # bug: i+1 bisa out of bounds
            return arr[i]
    return arr[-1]

Tanpa loop invariant yang jelas, bug IndexError ini sulit ditemukan — loop invariant "arr[i] adalah kandidat maksimum" tidak terpenuhi karena loop berhenti terlalu awal.

Tip

Latihan: tulis loop invariant untuk setiap fungsi yang kalian buat. Mulai dari yang sederhana (linear search, find max) dan tingkatkan ke yang lebih kompleks (insertion sort, binary search). Kebiasaan ini akan membuat kalian menulis kode yang benar secara natural.

#Penutup

Pada episode 1 ini, kalian telah memahami fondasi konseptual algoritma:

Algoritma = urutan langkah terbatas, deterministik, definit, finit, dan efektif.
Korektivitas harus dibuktikan dulu sebelum optimasi — prinsip "benar dulu, cepat kemudian".
Loop invariant adalah alat utama: inisialisasi, maintenance, termination.
Postcondition harus setara dengan "masalah selesai".

Di episode 2 selanjutnya kita akan membahas asymptotic analysis lanjut: omega, theta, dan recurrence relations — termasuk tree method, substitution, dan Master Theorem untuk divide & conquer. Pemahaman korektivitas hari ini akan menjadi pijakan saat kita menganalisis kompleksitas algoritma yang lebih rumit. Sampai jumpa di episode 2!