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

InformatikaAlgoritma dan pemecahan masalahUsia 15–16

Gunakan di kelas saya

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

  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?