Algoritma yang Selesai Tepat Waktu: Pemeriksaan Gut Kompleksitas

Anda menulis fungsi, menjalankannya pada data uji Anda, dan berfungsi dengan baik. Kemudian ia mencapai data produksi — 500.000 baris alih-alih 500 — dan permintaan habis waktu. Ini terjadi terus-menerus, dan hampir selalu masalah kompleksitas yang tersembunyi di balik kode yang terlihat masuk akal pada skala kecil.

Mengapa laptop Anda membohongi Anda

Algoritma O(n²) yang berjalan pada 100 item melakukan 10.000 operasi. Itu instan di mesin apa pun. Jalankan algoritma yang sama pada 100.000 item dan Anda berada di 10 miliar operasi — menit atau jam bukan milidetik. Lompatan dari n ke n² tidak terasa berbahaya sampai n menjadi besar, yang persis mengapa itu terlewat dalam tinjauan kode dan pengujian lokal.

Contoh klasik: memeriksa duplikat dengan loop bertingkat.

def has_duplicates(items):
    for i in range(len(items)):
        for j in range(i + 1, len(items)):
            if items[i] == items[j]:
                return True
    return False

Ini adalah O(n²). Tukarkan dengan set:

def has_duplicates(items):
    seen = set()
    for item in items:
        if item in seen:
            return True
        seen.add(item)
    return False

Sekarang ini O(n). Pencarian set rata-rata O(1), jadi seluruh fungsi berskala linier alih-alih kuadratik. Pada 10.000 item itu perbedaan antara kira-kira 100 juta perbandingan dan 10.000.

Ukur sebelum Anda mengoptimalkan

Jangan menebak. Gunakan timeit untuk microbenchmark:

import timeit
timeit.timeit(lambda: has_duplicates(list(range(5000))), number=10)

Untuk fungsi yang lebih besar, profil dengan cProfile:

python -m cProfile -s cumulative myscript.py

Lihat kolom cumtime. Jika satu fungsi menghabiskan 90% runtime, itu target Anda. Mengoptimalkan kode yang bukan bottleneck membuang waktu Anda dan menambah kompleksitas tanpa keuntungan.

Pola umum yang diam-diam menjadi lambat

Pemeriksaan keanggotaan list berulang. if x in my_list adalah O(n) untuk list tetapi O(1) rata-rata untuk set atau dict. Jika Anda memeriksa keanggotaan di dalam loop, pemeriksaan O(n) di dalam loop O(n) memberi Anda O(n²) keseluruhan. Tukarkan list dengan set dan Anda kembali ke O(n).

Penggabungan string dalam loop. Di Python, result += chunk di dalam loop atas string adalah O(n²) dalam kasus terburuk karena string tidak dapat diubah dan setiap penggabungan menyalin semuanya. Gunakan ''.join(chunks) sebagai gantinya — ini membangun string sekali.

Mengurutkan ketika Anda tidak perlu. sorted() adalah O(n log n). Jika Anda memanggilnya di dalam loop hanya untuk menemukan max atau min setiap iterasi, gunakan max()/min() (O(n)) atau lebih baik, heap (heapq) jika Anda memerlukan ekstrem yang berjalan berulang kali. heapq.nlargest(k, data) adalah O(n log k), jauh lebih murah daripada mengurutkan seluruh list ketika k kecil.

Fungsi rekursif tanpa memoization. Fibonacci rekursif naif adalah O(2ⁿ) karena ia menghitung ulang subproblem yang sama berulang kali. Tambahkan functools.lru_cache dan itu turun ke O(n):

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

Membaca Big O dari kode nyata, cepat

Hitung loop bertingkat atas input yang sama — itu biasanya eksponen Anda. Single loop adalah O(n). Loop di dalam loop adalah O(n²) kecuali range loop dalam menyusut (seperti dalam bubble sort bentuk teroptimalkan, masih O(n²) kasus terburuk tetapi lebih sedikit perbandingan). Panggilan rekursif yang membagi masalah menjadi dua, seperti binary search atau merge sort, menunjukkan O(log n) atau O(n log n). Panggilan rekursif yang bercabang menjadi banyak panggilan per level, seperti Fibonacci naif, menunjukkan waktu eksponensial — sinyal kuat bahwa Anda memerlukan memoization atau penulisan ulang iteratif.

Kebiasaan yang baik: sebelum Anda menulis loop bertingkat atau rekursi atas data yang dihadap pengguna, tanyakan apa yang realistis di produksi, bukan di file uji Anda. Jika n dapat mencapai enam digit, solusi O(n²) memerlukan pandangan kedua sebelum dikirim.

Untuk informasi lebih lanjut tentang analisis kompleksitas, algoritma pengurutan, dan alat profiling, periksa segmen Python dan Computer Science di Korra Studio.