Kompleksitas algoritma – O(log n), O(n), O(n log n), O(n²) dan balapan pengurutan

Yang ditunjukkan

Kompleksitas algoritma menggambarkan bagaimana jumlah operasi bertambah ketika ukuran data n membesar, tanpa memperhitungkan faktor konstanta. Grafik membandingkan empat laju pertumbuhan: log₂n hampir tidak naik, n tumbuh sebanding, n·log₂n tumbuh sedikit lebih cepat, dan n² menjadi empat kali lipat setiap kali n berlipat dua. Hasil pengukuran mendukung teori: pada larik acak, bubble sort melakukan sekitar n²/2 perbandingan, sedangkan quicksort sekitar 1,4·n·log₂n. Untuk n kecil selisihnya hampir tidak berarti; untuk data besar, pilihan algoritma menentukan apakah program selesai dalam hitungan detik atau jam.

Cara menggunakan

Mulailah dengan Kurva teoretis yang ditampilkan berisi keempat fungsi, lalu seret pada grafik untuk mengubah n dan baca nilai setiap kurva. Jika kurva terlalu berjauhan untuk dibandingkan, aktifkan Skala log untuk sumbu langkah. Kemudian tekan Balapan agar kedua algoritma mengurutkan larik yang sama dengan laju langkah yang sama, lalu ulangi dengan Larik baru dan n yang lebih besar untuk melihat selisihnya melebar.

Parameter yang dapat diubah

• Ukuran data n 4–100
• Kurva teoretis yang ditampilkan log₂n, n, n·log₂n, n², n dan n², log₂n, n dan n·log₂n
• Skala log untuk sumbu langkah
• Kecepatan balapan 5–200 langkah/s

Pertanyaan untuk dijelajahi

1. Ketika n berlipat dua dari 50 menjadi 100, n² menjadi berapa kali lipat, dan kira-kira n·log₂n menjadi berapa kali lipat?
2. Mengapa kurva log₂n tetap hampir datar sementara kurva n² naik tajam?
3. Untuk n = 10, berapa banyak perbandingan tambahan yang dilakukan bubble sort dibanding quicksort, dan apakah selisih itu penting dalam praktik?