Mengukur kecepatan algoritma

Mengukur kecepatan dengan stopwatch kurang adil: komputer yang lebih baru tentu lebih cepat. Ilmuwan komputer mengukur banyaknya langkah dasar dan, yang terpenting, bagaimana banyaknya langkah itu bertambah ketika datanya membesar.

Notasi Big-O

Notasi Big-O menggambarkan laju pertumbuhan banyaknya langkah terhadap banyak data n, dengan mengabaikan konstanta dan suku yang kecil.

Seberapa besar bedanya?

1import math23print(f"{'n':>9} {'log n':>6} {'n log n':>12} {'n kuadrat':>16}")4for n in [10, 100, 1_000, 1_000_000]:5    log = math.ceil(math.log2(n))6    print(f"{n:>9} {log:>6} {n * log:>12} {n * n:>16}")

        n  log n      n log n        n kuadrat
       10      4           40              100
      100      7          700            10000
     1000     10        10000          1000000
  1000000     20     20000000    1000000000000

Untuk sejuta data, algoritma O(n²) butuh sekitar satu triliun langkah. Jika komputer menjalankan satu miliar langkah per detik, itu sekitar 17 menit. Algoritma O(n log n) hanya butuh dua puluh juta langkah, selesai dalam sekejap.

Cara memperkirakan Big-O

• Satu perulangan sebanyak n kali: O(n).
• Perulangan di dalam perulangan, masing-masing n kali: O(n²).
• Perulangan yang membagi dua datanya setiap putaran: O(log n).
• Langkah yang berurutan dijumlahkan, lalu ambil yang terbesar: O(n) + O(n²) = O(n²).

1def ada_pasangan_berjumlah(data, target):2    for i in range(len(data)):3        for j in range(i + 1, len(data)):4            if data[i] + data[j] == target:5                return True6    return False78print(ada_pasangan_berjumlah([3, 9, 14, 20, 25], 34))9print(ada_pasangan_berjumlah([3, 9, 14, 20, 25], 50))

True
False

Dua perulangan bersarang membuat fungsi ini O(n²): untuk n data, ada sekitar n × n / 2 pasangan yang diperiksa.

1def ada_pasangan_cepat(data, target):2    dilihat = set()3    for x in data:4        if target - x in dilihat:5            return True6        dilihat.add(x)7    return False89print(ada_pasangan_cepat([3, 9, 14, 20, 25], 34))10print(ada_pasangan_cepat([3, 9, 14, 20, 25], 50))

True
False