Nota video

Teks penuh video

Kalau kau nak cari satu bata merah dalam gudang sejuta bata bersepah, kau belek satu demi satu sampai jumpa. Pinggang sakit, mata juling, minggu depan baru siap! Tapi cara ni namanya linear search, dan dalam kes terburuk kau kena periksa kesemua sejuta bata!

Jadi, susun dulu bata ikut nombor, kemudian semak bata di tengah dan buang separuh yang pasti tiada sasaran, setiap kali. Sejuta bata cuma perlu lebih kurang dua puluh langkah. Ini namanya binary search.

Tapi kalau susun guna bubble sort, tukar dua bata bersebelahan berulang kali, sejuta bata boleh makan hampir setengah trilion perbandingan! Jadi, pilih satu bata sebagai pivot, hantar yang lebih kecil ke kiri dan yang lebih besar ke kanan. Ulang pada setiap kumpulan sampai semua tersusun, purata cuma n log n langkah.

Ini namanya quicksort. Tapi kalau kau asyik pilih bata pertama sebagai pivot pada data yang dah tersusun, setiap pecahan jadi berat sebelah dan quicksort merosot ke n kuasa dua! Jadi, pilih pivot secara rawak, atau ambil nilai tengah antara bata pertama, tengah dan terakhir supaya pecahan lebih seimbang.

Ini namanya median of three. Tapi quicksort tak stabil, jadi dua pesanan dengan harga sama boleh tertukar turutan asalnya! Jadi, belah data kepada dua berulang kali sampai tinggal sebiji, kemudian cantum semula sambil menyusun, dan bata sama nilai kekal ikut turutan asal dengan jaminan n log n dalam semua kes.

Ini namanya merge sort. Tapi kalau kau cari benda sama beribu kali sesaat, dua puluh langkah setiap carian masih membazir! Jadi, setiap bata masuk ke laci khas yang nombornya dikira terus daripada nilai bata itu melalui fungsi hash, maka carian purata cuma satu langkah.

Ini namanya hash table. Sekarang kau dah tahu rahsianya, susun dengan quicksort atau merge sort, cari dengan binary search, dan guna hash table bila nak laju maksimum. Inilah asas kecekapan algoritma yang selalu keluar dalam soalan LeetCode dan temuduga kerja.

Lepas ni nak belajar apa pula?

Siri Teknologi dan AI dalam animasi 3D LEGO (V916-028) oleh KongsikanDotCom. Tonton lagi di