Seberapa efisien dan terukur program Anda?
Big O, ini benar-benar topik yang penting untuk dibahas. Anda hampir tidak dapat melihat wawancara tanpa topik ini.
Dan ini adalah konsep yang akan bertahan lama di dunia pengembang. Baik Anda seorang pengembang senior yang sudah lama melakukan coding atau pemula, ini adalah konsep yang sangat penting untuk diketahui.
Ini tidak hanya membantu dalam wawancara tetapi juga memainkan peran penting dalam cara Anda menulis program.
Jadi izinkan saya memulai dengan berbagi pengalaman kecil yang menuntun saya mempelajari Struktur Data & Algoritma dalam pendekatan praktis.
Beberapa hari yang lalu, saya berpartisipasi dalam Google Code Jam pertama saya: sebuah kompetisi coding online di mana Anda akan diberikan serangkaian masalah untuk menemukan solusinya. Dan saya baru saja lolos ke Putaran Pertama. Ada 3 masalah yang harus diselesaikan dalam waktu 2,30 jam. Saya yakin bahwa saya tidak akan mampu menyelesaikan semuanya tetapi setidaknya ingin menyelesaikan satu masalah. Jadi saya mencoba menyelesaikan salah satunya tetapi sebagian besar upaya saya menghasilkan Kesalahan Terlampaui Batas Waktu(Ada beberapa jawaban yang salah juga..).
Dan ini karena solusi saya tidak sesuai algoritmik yang tepat.
Apa yang menyebabkan Kesalahan TLE itu?
Dengan baik. Jawabannya sederhana. Itu karena O Besar yang tidak sempurna. Saya telah menggunakan begitu banyak loop bersarang yang menyebabkan program berjalan secara eksponensial karena kumpulan data menjadi semakin besar. Dan di sinilah saya menyadari pentingnya Struktur Data & Algoritma. Jika saya mengikuti pendekatan yang benar, saya dapat menghemat sebagian besar waktu dan program saya juga akan sempurna. Oleh karena itu saya mulai dengan mempelajari Big O, langkah pertama dalam menguasai struktur data & algoritma.
Ngomong-ngomong, pada akhirnya, aku bahkan tidak menyelesaikan satu pun di Putaran 1. LOL :)
Barang-barangku sudah cukup. Mari kita mulai. Namun sebelum kita mulai, saya ingin mengajukan pertanyaan kepada Anda.
Bagaimana Anda mendefinisikan Kode yang Baik?
Katakanlah ada 2 orang teman Tim & Tom dimana keduanya mempunyai solusi suatu masalah. Dalam hal ini, bagaimana kita bisa mengetahui kode mana yang lebih baik? Jawabannya adalah, ada 2 hal yang membuat sebuah kode menjadi bagus, lebih baik dan terbaik. Mereka
- Keterbacaan
- Skalabilitas
Dalam artikel ini, kita akan membahas skalabilitas karena Big O termasuk dalam kategori ini. Jadi bagaimana kita mengukur skalabilitas? Untuk memahaminya dengan lebih baik, misalkan kita mempunyai fungsi yang menemukan bumi dalam serangkaian planet.
Untuk fungsi di atas, mari kita ukur skalabilitasnya dalam kaitannya dengan kompleksitas waktu dengan mengetahui berapa banyak waktu yang diperlukan untuk menjalankannya.
Perlu diperhatikan bahwa skalabilitas diukur dalam bentuk Kompleksitas Waktu & Kompleksitas Ruang. Namun untuk saat ini, mari kita fokus pada kompleksitas waktu saja.
Kita dapat melakukan ini dalam javascript dengan menambahkan performace.now() di awal & akhir fungsi. Terakhir, kita kurangi t1-t0 untuk mendapatkan total waktu yang dibutuhkan fungsi tersebut. Dan karena ini adalah fungsi kecil, waktu yang dibutuhkan adalah 0 milidetik (kira-kira).
Namun bagaimana jika ada lebih dari 10.000 elemen dalam array. Waktunya akan bertambah tapi tidak terlalu signifikan kan?. Komputer sangat cepat saat ini. Namun mungkin ada sedikit perbedaan waktu setiap kali Anda menjalankan program.
Dan itu sepenuhnya bergantung pada seberapa cepat CPU komputer Anda, program apa yang sudah digunakan, dll.
Jadi jika kita menerapkan metodologi ini pada kode Tim dan Tom, dapatkah kita mengatakan bahwa kode Tim (4 milidetik) lebih baik daripada kode Tom (6 milidetik) karena memerlukan waktu 2 milidetik lebih sedikit untuk menjalankannya? Tidak, itu bukan cara menilai yang benar. Seperti yang dikatakan sebelumnya, waktu dapat bervariasi tergantung pada faktor eksternal lainnya seperti CPU apa yang Anda gunakan, program lain apa yang berjalan secara bersamaan? dll..
Oke. lalu bagaimana kita mengukurnya?
Jawabannya adalah Big O.
Jadi apa itu Big O?
Big O adalah cara untuk mengukur seberapa efisien program Anda. Seperti yang dikatakan sebelumnya, setiap orang dapat menulis solusi suatu masalah asalkan ada waktu yang cukup seperti Tim dan Tom, bukan? Jadi masalahnya adalah, seberapa baik kinerja program kita selama runtime. Apakah peningkatan masukan menjadi rumit? Dan inilah yang dicari oleh sebagian besar raksasa teknologi terkemuka seperti Google, Amazon, dll.
Jadi Big O adalah bahasa yang kita gunakan untuk menentukan berapa lama waktu yang dibutuhkan suatu fungsi/algoritma untuk berjalan.
Kita dapat menggunakan Big O untuk membandingkan dua algoritme berbeda seperti kode Tim dan Tom & menentukan mana yang lebih baik terlepas dari performa komputernya. Dan suatu algoritme dapat memiliki Big O yang berbeda-beda berikut ini.
Ini mungkin tampak rumit tetapi akan menjadi lebih mudah untuk dipahami seiring kita melangkah lebih jauh.
Dari bagan di atas, Anda dapat melihat jumlah operasi meningkat secara signifikan pada peningkatan elemen dalam beberapa kasus [O(n!), O(2^n), O(n²)]. Dan jumlah operasinya tetap hampir sama dalam beberapa kasus [O(log n), O(1), dll.].
Dan inilah cara kami mendefinisikan kode yang baik dalam kaitannya dengan kompleksitas waktu menggunakan Big O. Kami pastinya tidak ingin algoritme/fungsi kami tetap berada di area merah karena Anda melihatnya sangat buruk.
Setiap kali kami mendefinisikan skalabilitas dalam kaitannya dengan kompleksitas waktu menggunakan Big O, yang kami maksud adalah,
Ketika masukan bertambah besar dan besar, seberapa besar kecepatan algoritma kita melambat. Semakin sedikit perlambatannya, semakin baik seperti wilayah hijau & kuning.
Jadi, mulai sekarang, daripada menggunakan performance.now() untuk menghitung waktu, kita akan menggunakan O Besar untuk mengukur jumlah langkah yang diperlukan algoritme seiring bertambahnya masukan.
Dan kita akan belajar bagaimana menghitung O Besar?, apa itu O(n), O(1), dan seterusnya? di artikel berikutnya karena ini sudah cukup panjang. Saya tidak ingin memuat terlalu banyak hal dalam satu artikel. Jadi mari kita kembali ke artikel selanjutnya :)
Ngomong-ngomong, semua pengetahuan ini berasal dari Andrei. Seorang instruktur yang sangat baik bagi saya dan banyak siswa lainnya. Setiap tepuk tangan di sini didedikasikan untuknya :)
