Memahami Notasi Big O: Panduan Pemula untuk Kerumitan Masa dan Ruang

Bayangkan kita mempunyai cara yang berbeza untuk menulis kod yang sama. Bagaimanakah kita mengetahui yang mana satu yang terbaik? Di situlah notasi Big O masuk. Ia membantu kami mengukur berapa banyak masa dan ruang yang diperlukan oleh kod, menjadikannya lebih mudah untuk membandingkannya.

Apakah Notasi Big-O?

Big O, juga dikenali sebagai "Order of," ialah cara untuk menerangkan berapa lama algoritma mungkin mengambil masa untuk dijalankan dalam senario terburuk. Ia memberi kita idea tentang masa maksimum yang diperlukan oleh algoritma berdasarkan saiz input. Kami menulisnya sebagai O(f(n)), dengan f(n) menunjukkan berapa banyak langkah yang diambil oleh algoritma untuk menyelesaikan masalah dengan saiz input n.

Mari cuba fahami melalui contoh “Tulis fungsi yang menerima input rentetan dan mengembalikan salinan terbalik“

Baiklah, saya berkongsi penyelesaian Stack Overflow dengan anda, bersama-sama dengan imej di atas, seperti yang anda boleh lihat. Ia menunjukkan 10 cara berbeza untuk menyelesaikan masalah yang sama, setiap satu dengan pendekatan yang unik.

Sekarang, persoalannya ialah: bagaimana kita tahu yang mana satu yang terbaik?

Matlamat kami adalah untuk memahami kerumitan masa dan ruang. Untuk melakukan ini, mari kita terokai contoh konkrit dengan dua coretan kod yang berbeza, supaya kita dapat melihat dengan jelas bagaimana konsep ini penting.

Berikut ialah fungsi yang dipanggil addUpTo. Fungsi ini menggunakan gelung for yang berjalan sehingga mencapai panjang n dan mengembalikan jumlah keseluruhan.

Sekarang, mari lihat contoh lain yang mencapai fungsi yang sama:

Mana satu lebih baik?

Sekarang, apakah maksud 'lebih baik' sebenarnya dalam konteks ini?

• Adakah lebih pantas?

• Adakah ia menggunakan kurang memori?

• Adakah ia lebih mudah dibaca?

Lazimnya, orang menumpukan pada dua yang pertama—kelajuan dan penggunaan memori—sebelum mempertimbangkan kebolehbacaan. Dalam kes ini, kita akan menumpukan pada dua yang pertama. Untuk mengukur prestasi kedua-dua contoh kod, kami akan menggunakan fungsi pemasaan terbina dalam JavaScript untuk menganalisis dan membandingkan masa pelaksanaannya.

Dalam kod di atas, saya telah menambah t1 dan t2, yang menggunakan fungsi performance.now() terbina dalam JavaScript. Fungsi ini membantu kami mengukur masa yang diambil oleh kod untuk dilaksanakan, membolehkan kami membandingkan prestasi kedua-dua pendekatan dengan tepat.

Tepat sekali, masa pelaksanaan berbeza-beza bergantung pada faktor yang berbeza dan anda boleh melihatnya pada komputer saya juga—masanya tidak konsisten. Fungsi performance.now() tidak memberi kita masa tetap, tetapi ia memberikan anggaran yang berguna untuk perbandingan.

Sekarang, mari kita lihat contoh kedua:

Sekarang, perhatikan perbezaan masa pelaksanaan antara contoh kod pertama dan kedua. Yang kedua nyata lebih pantas daripada yang pertama.

Tetapi apakah masalahnya bergantung pada ukuran masa semata-mata?

• Mesin yang berbeza merekodkan masa yang berbeza.

• Malah mesin yang sama akan merakam masa yang berbeza pada setiap larian.

• Untuk algoritma yang sangat pantas, ukuran kelajuan mungkin tidak cukup tepat untuk memberikan perbandingan yang tepat.

Faktor ini menjadikan penilaian prestasi berasaskan masa tidak boleh dipercayai, terutamanya untuk algoritma pantas.

Baiklah, kalau bukan masa apa?

Di situlah Big O akan membantu kita mengukur kerumitan masa dan ruang kedua-duanya. So Big O Notation ialah satu cara untuk memformalkan pengiraan kabur. Ia membolehkan kami bercakap secara rasmi tentang cara masa jalan algoritma berkembang apabila input berkembang.

Kami mengatakan bahawa algoritma ialah O(f(n)) jika bilangan operasi mudah yang perlu dilakukan oleh komputer akhirnya kurang daripada pemalar dikali f(n), apabila n bertambah.

• f(n) boleh menjadi linear (f(n) = n)

• f(n) boleh menjadi kuadratik (f(n) = n2)

• f(n) boleh menjadi malar (f(n) = 1)

• f(n) boleh jadi sesuatu yang berbeza sama sekali!

Berikut ialah contoh:

Dalam kes ini, kami hanya mempunyai 3 operasi, dan tidak kira saiz input, ia akan sentiasa kekal 3 operasi. Inilah sebabnya kita boleh mengatakan bahawa kerumitan masa fungsi ini adalah malar, atau O(1).

Sekarang inilah contoh pertama:

Dalam kes ini, apabila input n bertambah, bilangan operasi juga meningkat secara berkadar. Oleh itu, kerumitan masa bergantung pada saiz input, menjadikannya O(n).

Sekarang, mari lihat contoh lain:

Dalam contoh ini, kita mempunyai dua gelung bersarang, kedua-duanya bergantung pada n—input. Ini bermakna apabila input n bertambah, bilangan operasi meningkat dengan ketara. Akibatnya, kerumitan masa kod ini ialah O(n²), juga dikenali sebagai kerumitan masa kuadratik.

Sekarang, mari permudahkan Big O Notation. Apabila menentukan kerumitan masa sesuatu algoritma, terdapat beberapa peraturan berguna yang perlu diingat. Garis panduan ini timbul daripada takrifan formal tatatanda Big O dan menjadikannya lebih mudah untuk menganalisis algoritma.

Pemalar tidak penting

• O(2n) = O(n)

• O(500) = O(1)

• O(13n²) = O(n²)

• O(n 10) = O(n)

• O(1000n 500) = O(n)

• O(n² 5n 8) = O(n²)

Big O Shorthands

1. Operasi aritmetik adalah malar

2. Tugasan pembolehubah adalah malar

3. Mengakses elemen dalam tatasusunan (mengikut indeks) atau objek (mengikut kunci) adalah malar

4. Dalam gelung, kerumitan ialah panjang gelung dikali gandakan kerumitan apa sahaja yang berlaku di dalam gelung

Berikut ialah Carta O Besar:

Setakat ini, daripada contoh, kami telah belajar tentang O(n) (kerumitan masa linear), O(1) (kerumitan masa malar) dan O(n²) (kerumitan masa kuadratik). Ini merangkumi corak asas di mana operasi berkembang dengan saiz input.

Kita akan membincangkan O(log n) dan O(n log n)—kerumitan masa logaritma dan linearitma—sedikit kemudian.

Kerumitan Ruang

Setakat ini, kami memfokuskan pada kerumitan masa: bagaimana kami boleh menganalisis masa jalan algoritma apabila saiz input meningkat?

Kami juga boleh menggunakan notasi O besar untuk menganalisis kerumitan ruang: berapa banyak memori tambahan yang perlu kami peruntukkan untuk menjalankan kod dalam algoritma kami?

Bagaimana pula dengan input?

Kadangkala anda akan mendengar istilah kerumitan ruang tambahan untuk merujuk kepada ruang yang diperlukan oleh algoritma, tidak termasuk ruang yang diambil oleh input. Melainkan dinyatakan sebaliknya, apabila kita bercakap tentang kerumitan ruang, secara teknikalnya kita akan bercakap tentang kerumitan ruang tambahan.

Kerumitan Angkasa dalam JS

• Kebanyakan primitif (boolean, nombor, tidak ditentukan, null) ialah ruang malar

• String memerlukan ruang O(n) (di mana n ialah panjang rentetan) Jenis rujukan biasanya O(n), dengan n ialah panjang (untuk tatasusunan) atau bilangan kekunci (untuk objek)

Ingat, kita bercakap tentang kerumitan ruang, bukan kerumitan masa. Dalam kod ini, kita dapat melihat kita hanya mempunyai dua pembolehubah. Tidak kira berapa besar input berkembang, kedua-dua pembolehubah ini akan sentiasa wujud dalam kod. Memandangkan kami tidak menambah sebarang pembolehubah baharu apabila input meningkat, kami boleh mengatakan bahawa kerumitan ruang ialah O(1), bermakna ia adalah kerumitan ruang yang berterusan.

Mari kita fahami dengan contoh lain:

Dalam kod ini, fungsi mengembalikan newArr selepas menggandakan setiap elemen dalam tatasusunan input. Oleh kerana saiz newArr adalah berkadar terus dengan saiz arr input, ruang yang digunakan oleh newArr berkembang dengan saiz input. Tidak seperti contoh sebelumnya, di mana ruang adalah malar, di sini kerumitan ruang bergantung pada saiz tatasusunan input. Oleh itu, kerumitan ruang ialah O(n), bermakna ia adalah linear.

Saya harap ini menjadikan kerumitan ruang lebih jelas—sama seperti kerumitan masa, kami mengukurnya menggunakan tatatanda Big O. Setakat ini, anda telah mempelajari tentang kerumitan masa yang berbeza, dalam susunan kerumitan yang semakin meningkat: O(1), O(log n), O(n), O(n log n), O(n²), O(n³) dan sebagainya. Walau bagaimanapun, kami belum lagi meneroka kerumitan masa logaritma.

Seterusnya, kita akan menyelami kerumitan masa logaritma dan lihat cara ia berfungsi.

Logaritma

Kami telah menemui beberapa kerumitan yang paling biasa: O(1), O(n), O(n2). Kadangkala ungkapan O besar melibatkan ungkapan matematik yang lebih kompleks. Satu yang muncul lebih kerap daripada yang anda mungkin suka ialah logaritma!

Apa itu log lagi?

log2 (8) = 3 → 2³ = 8

log2 (nilai) = eksponen → 2^eksponen = nilai

Kami akan meninggalkan 2, yang bermaksud:

log === log2

Logaritma nombor secara kasar mengukur berapa kali anda boleh membahagikan nombor itu dengan 2 sebelum ia menjadi kurang daripada atau sama dengan 1. Ini menjadikan kerumitan masa logaritma sangat cekap. Seperti yang anda lihat dalam carta, O(1) (masa malar) sangat hampir dengan O(log n), yang sangat hebat! Perlu juga diperhatikan bahawa O(n log n) jauh lebih baik daripada O(n²) dari segi kecekapan, menjadikannya kerumitan pilihan untuk banyak algoritma.

• Algoritma carian tertentu mempunyai kerumitan masa logaritma.

• Algoritma pengisihan yang cekap melibatkan logaritma.

• Rekursi kadangkala melibatkan kerumitan ruang logaritma.

Hebat! Kami telah membincangkan kebanyakan perkara utama mengenai kerumitan ruang dan masa. Perlu diingat bahawa menguasai konsep ini memerlukan latihan, jadi jangan berasa terharu jika ia tidak benar-benar jelas serta-merta. Luangkan masa anda, semak bahan berkali-kali dan semak semula contoh seperti yang diperlukan. Ia selalunya memerlukan beberapa ulangan untuk idea ini benar-benar meresap, jadi bersabarlah dengan diri sendiri!

Akhir sekali, mari kita buat sekali lagi rekap:

• Untuk menganalisis prestasi algoritma, kami menggunakan Notasi O Besar

• Notasi O Besar boleh memberi kita pemahaman peringkat tinggi tentang kerumitan masa atau ruang sesuatu algoritma

• Big O Notation tidak mementingkan ketepatan, hanya mengenai trend umum (linear? kuadratik? malar?)

Sekali lagi, Big O Notation ada di mana-mana, jadi dapatkan banyak latihan!

---

Kami di CreoWis percaya dalam berkongsi pengetahuan secara terbuka untuk membantu komuniti pembangun berkembang. Mari berkolaborasi, mencipta idea dan menjana semangat untuk menyampaikan pengalaman produk yang mengagumkan kepada dunia.

Jom sambung:

• X/Twitter

• LinkedIn

• Tapak web

Artikel ini dihasilkan oleh Syket Bhattachergee, pembangun yang bersemangat di CreoWis. Anda boleh menghubunginya di X/Twitter, LinkedIn, dan mengikuti hasil kerjanya di GitHub.

Atas ialah kandungan terperinci Memahami Notasi Big O: Panduan Pemula untuk Kerumitan Masa dan Ruang. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!