Pencarian Linear, Set, dan Biaya Operasi

Tujuan belajar

Kamu dapat menelusuri pencarian linear, menjelaskan batas biaya O(n), dan memilih set untuk pemeriksaan keanggotaan berulang dengan mempertimbangkan biayanya.

Bekal awal

Kamu memahami list, perulangan, fungsi, dan perbandingan nilai. Notasi n di sini berarti banyaknya elemen data.

Menghitung pekerjaan, bukan hanya waktu jam

Untuk mencari satu nama di list tanpa informasi urutan, program dapat memeriksa elemen dari depan. Jika nama berada di awal, satu pemeriksaan cukup. Jika berada di akhir atau tidak ada, program harus memeriksa hingga n elemen. Karena jumlah pemeriksaan terburuk bertambah sebanding dengan panjang list, kita menyebutnya O(n). Notasi ini menjelaskan pola pertumbuhan, bukan berapa milidetik sebuah komputer tertentu akan bekerja. Ukuran input dan jenis operasi yang dihitung harus selalu disebutkan.

Set menyimpan anggota unik dan menyediakan pemeriksaan keanggotaan yang biasanya cepat melalui hashing. Membentuk set dari list sendiri memerlukan pekerjaan dan memori. Maka mengganti satu pencarian kecil dengan konversi set belum tentu bermanfaat. Bila data yang sama akan dicari berkali-kali dan urutan tidak diperlukan untuk pencarian itu, membangun set sekali dapat masuk akal. Perhatikan pula bahwa set menghilangkan duplikasi: jumlah anggota set tidak selalu sama dengan jumlah baris awal. Jika jumlah kemunculan tiap nama penting, jangan membuang data asal.

Contoh kerja 1: pencarian linear

def posisi(data, target):
    for indeks, item in enumerate(data):
        if item == target:
            return indeks
    return -1

print(posisi(["Ayu", "Bima", "Cici"], "Cici"))

Jejak: pemeriksaan 1 membandingkan Ayu dengan Cici, salah; pemeriksaan 2 Bima, salah; pemeriksaan 3 Cici, benar, lalu fungsi mengembalikan indeks 2. Keluaran “2”. Untuk target “Danu”, tiga pemeriksaan gagal dan return -1 tercapai. Untuk target “Ayu”, fungsi berhenti sesudah satu pemeriksaan. Ini menunjukkan kasus terbaik dan terburuk berbeda, walaupun algoritmanya sama.

Contoh kerja 2: banyak pertanyaan pada data sama

peserta = ["Ayu", "Bima", "Cici", "Ayu"]
daftar_unik = set(peserta)
print("Bima" in daftar_unik)
print(len(daftar_unik))

Set berisi Ayu, Bima, dan Cici; Ayu yang kedua tidak menambah anggota baru. Keluaran dua baris ialah “True” dan “3”. Jangan mengandalkan urutan cetak set, karena contoh tidak mencetak set itu sendiri. Untuk banyak pemeriksaan nama, daftar_unik dapat dipakai kembali tanpa membuat set pada setiap pertanyaan.

Kesalahan umum dan debugging

Kesalahan konsep yang sering muncul ialah menyebut setiap penggunaan set “O(1) pasti”. Hashing biasanya memberi waktu rata-rata yang baik, tetapi biaya membentuk set, kualitas hash, dan kondisi terburuk tetap relevan. Kesalahan kode lain adalah memakai if item == target lalu mengembalikan nilai item ketika kontrak fungsi meminta posisi indeks. Tulis kontrak keluaran terlebih dahulu, lalu uji target di awal, di akhir, dan tidak ditemukan. Jangan memakai -1 sebagai indeks list tanpa sengaja: dalam Python, data[-1] berarti elemen terakhir, bukan “tidak ada”.

Pikirkan kontrak dan ukuran input

Jika fungsi posisi mengembalikan -1, pemanggil harus memeriksa nilai itu sebelum mengakses list. Menggunakan hasil -1 langsung sebagai indeks justru mengambil elemen terakhir dan menyamarkan “tidak ditemukan”. Catat juga apa yang terjadi pada list kosong: perulangan menjalankan nol pemeriksaan dan fungsi mengembalikan -1. Saat membandingkan dua pendekatan, ukur pekerjaan yang sama. Untuk satu pencarian pada tiga elemen, kode yang paling mudah dipahami bisa lebih baik. Untuk ribuan pencarian pada data sama, biaya membuat set dapat dibagi ke banyak pertanyaan. Tulislah asumsi ini saat menjelaskan pilihan algoritma.

Ringkasan dan latihan

Pencarian linear memeriksa hingga n elemen; set berguna untuk banyak uji keanggotaan pada data yang sama bila duplikasi tidak diperlukan. Buat list sepuluh nama dan hitung berapa perbandingan yang dilakukan pencarian linear untuk target pertama, terakhir, dan tidak ada. Lalu jelaskan kapan biaya membangun set sekali layak dibayar.

def posisi(data, target):
    for indeks, item in enumerate(data):
        if item == target:
            return indeks
    return -1

print(posisi(["Ayu", "Bima", "Cici"], "Cici"))

Sumber belajar

• Python Tutorial: Data Structures
• Python Tutorial: More Control Flow Tools
• Python Wiki: TimeComplexity
• MIT OpenCourseWare: Lecture 12, Searching and Sorting

Penjelasan dan contoh disusun ulang untuk materi ini; sumber dapat dibuka untuk belajar lebih lanjut.