Nota video

Teks penuh video

Kalau kau nak cari satu bata merah dalam gudang sejuta bata, kau angkat dan periksa setiap bata satu per satu sampai jumpa. Kalau nasib malang, bata tu ada paling bawah! Tapi bila bata bertambah sepuluh kali ganda, masa carian pun naik sepuluh kali ganda, dan kau tak tahu bila sistem kau akan tersekat!

Jadi, kau ukur kadar pertumbuhan langkah kerja berbanding saiz data n, bukan masa jam. Carian satu per satu tadi tumbuh seiring data, dipanggil O n atau masa linear. Ini namanya notasi Big O.

Tapi untuk cari bata kembar, mesin kau bandingkan setiap bata dengan semua bata lain, satu gelung dalam gelung yang jadi O n kuasa dua! Jadi, setiap bata dicampak ke laci berlabel ikut kod warnanya, dan semak laci itu ambil masa tetap tak kira berapa besar gudang. Ini namanya hash table, carian purata O satu.

Tapi robot kau masih semak bata satu per satu walaupun rak dah tersusun ikut nombor! Jadi, dia periksa bata tengah rak, buang separuh yang salah, dan ulang, sampai sejuta bata cuma perlukan kira-kira dua puluh langkah. Ini namanya binary search, kerumitan O log n.

Tapi sebelum boleh guna binary search, data mesti disusun, dan mesin penyusun kau tukar bata bersebelahan berulang kali, lambat pada kadar O n kuasa dua! Jadi, kau belah timbunan bata kepada kumpulan kecil, susun setiap satu, kemudian cantumkan semula secara teratur. Ini namanya merge sort, kerumitan O n log n.

Tapi kod laju tak bermakna sempurna, sebab hash table dan merge sort makan ruang tambahan sampai gudang memori penuh melimpah! Jadi, kau ukur juga berapa banyak ruang yang membesar ikut saiz data, dan pilih imbangan antara laju dan jimat memori. Ini namanya space complexity.

Sekarang kau tahu Big O ukur cara kod membesar, dari O satu yang kilat hingga O n kuasa dua yang merangkak. Bila data berjuta, algoritma yang tepat jimatkan masa dan kos pelayan. Lepas ni nak belajar apa pula?

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