Kompleksitas algoritma – O(log n), O(n), O(n log n), O(n²) dan balapan pengurutan
InformatikaAlgoritma dan pemecahan masalahUsia 15–16
Untuk apa Anda paling sering menggunakan simulasi ini?
Gunakan di kelas Anda: siswa membukanya lewat tautan atau kode QR, tanpa perlu akun.
Grafik menggambarkan banyaknya langkah terhadap ukuran masukan n untuk fungsi log₂n, n, n·log₂n, dan n², beserta jumlah perbandingan yang diukur langsung untuk bubble sort dan quicksort. Siswa menyeret penanda n pada grafik untuk membaca nilainya, lalu mengeklik Balapan untuk melihat kedua algoritma mengurutkan larik yang sama dengan laju langkah yang sama: quicksort (n log n) selesai lebih dulu daripada bubble sort (n²), dan selisihnya makin besar saat n bertambah. Layar kedua, Pedagang keliling, menempatkan kota-kota pada peta dan membandingkan brute force (coba semua), yang memeriksa semua (n − 1)!/2 rute sehingga segera memerlukan waktu yang tidak wajar, dengan heuristik tetangga terdekat yang cepat.
Pelajaran: Menilai algoritma: banyak operasi terhadap ukuran masukan, notasi Big O, membandingkan bubble sort dan quicksort
Yang ditunjukkan
Kompleksitas algoritma menggambarkan bagaimana jumlah operasi bertambah ketika ukuran masukan n membesar, tanpa memperhitungkan faktor konstanta. Grafik membandingkan log₂n, n, n·log₂n, dan n²; hasil pengukuran menunjukkan bubble sort sekitar n²/2 perbandingan dan quicksort sekitar 1,4·n·log₂n. Beberapa masalah jauh lebih buruk. Layar pedagang keliling mencoba setiap rute: ada (n − 1)!/2 rute, sehingga setiap tambahan satu kota melipatgandakan pekerjaan dan 16 kota akan memakan waktu berjam-jam. Heuristik seperti tetangga terdekat menjawab dalam n(n − 1)/2 langkah, dengan cepat tetapi tidak selalu dengan rute terpendek.
Cara menggunakan
Seret pada grafik untuk mengubah n, dan aktifkan Skala log untuk sumbu langkah jika kurva terlalu berjauhan; tekan Balapan untuk melihat pengurutan. Lalu tekan Pedagang: ketuk peta untuk menambah kota, tekan Coba semua dan Tetangga terdekat, lalu bandingkan rute dan langkahnya. Ubah Jumlah kota dan Kecepatan komputer untuk melihat waktunya meledak.
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, n, n², 2ⁿ dan n!
- Skala log untuk sumbu langkah
- Kecepatan balapan 5–200 langkah/s
- Layar Grafik kompleksitas, Pedagang keliling
- Jumlah kota (pedagang keliling) 4–16
- Benih acak untuk kota-kota 1–999
- Kecepatan komputer 10⁶ langkah per detik, 10⁹ langkah per detik, 10¹² langkah per detik
Pertanyaan untuk dijelajahi
- Ketika n berlipat dua dari 50 menjadi 100, n² menjadi berapa kali lipat, dan kira-kira n·log₂n menjadi berapa kali lipat?
- Mengapa kurva log₂n tetap hampir datar sementara kurva n² naik tajam?
- Untuk n = 10, berapa banyak perbandingan tambahan yang dilakukan bubble sort dibanding quicksort, dan apakah selisih itu penting dalam praktik?