Pada video sebelumnya kita telah mengerjakan latihan mengenai algoritma bilangan prima dengan menggunakan function. Sekarang kita masuk ke pertanyaan berikutnya, apakah function yang kita buat sudah cukup baik? Nah, sebelum kita menjawab pertanyaannya, kita harus tau dulu nih, cukup baik itu dinilai dari kategori apa? Bisa saja waktu eksekusinya lebih cepat. Atau bisa juga dihitung dari jumlah memory yang dibutuhkan untuk menjalankan script. Atau dilihat dari souce codenya, gampang untuk ditulis dan dibaca? Khusus untuk video ini, kita akan membicarakan mengenai waktu eksekusi.

Jadi sekarang pertanyaan kita lebih spesifik ya. Apakah function yang kita tulis sudah cukup cepat? Nah, berhubungan dengan pertanyaan ini, maka ada satu hal yang perlu kita perhatikan. Semakin besar jumlah data, maka biasanya waktu yang diperlukan untuk eksekusi menjadi lebih besar.

Disinilah kita masuk ke pelajaran kita khusus untuk video ini, yaitu Notasi Big O. Notasi Big O membandingkan seberapa banyak jumlah waktu yang diperlukan apabila jumlah datanya bertambah.

Kalau kita gambarkan grafiknya. Misalkan ke arah atas adalah jumlah waktu yang diperlukan. Sedangkan ke arah kanan adalah jumlah datanya. Notasi Big O yang paling ideal adalah O(n). Artinya jumlah waktu yang diperlukan berbanding lurus dengan jumlah datanya. Apabila jumlah data meningkat 2 kali lipat, maka jumlah waktu yang diperlukan untuk eksekusi meningkat 2 kali lipat juga.

Kemudian ada fungsi yang lebih baik dari O(n), yaitu O(log n). Apabila jumlah data meningkat 2 kali lipat, maka jumlah waktu yang diperlukan meningkat namun lebih kecil dari 2 kali lipatnya. Jadi grafik penambahan waktunya landai. Fungsi seperti ini bisanya memproses data dengan menggunakan struktur data tree.

Dan ini adalah notasi Big O terbaik, yaitu O(1). Dengan membuat fungsi seperti ini, maka jumlah waktu yang diperlukan untuk eksekusi tetap sama, tidak peduli sebanyak apa pun jumlah data yang harus kita proses. Namun sayangnya tidak semua masalah bisa kita pecahkan menggunakan notasi O(1).

Diatas notasi O(n), ada yang namanya notasi O(n log n). Jadi apabila kita menggunakan fungsi kita dengan jumlah data yang meningkat 2 kali lipat, maka waktu yang diperlukan juga meningkat lebih dari 2 kali lipat.

Dan notasi O yang paling jelek dalam video ini adalah O(n2). Dengan menggunakan fungsi dengan notasi O(n2), pada saat jumlah data kita meningkat 2 kali lipat, maka jumlah waktu yang diperlukan meningkat lebih tajam, di sekitar 4 kali lipat. Jadi kita mesti berhati-hati sekali terhadap jumlah data yang akan digunakan. Nanti kita akan melihat bagaimana praktek dari notasi big o ini pada coding yang telah kita kerjakan.

Kita buka kode kita dari video sebelumnya mengenai bilangan prima. Di bagian console, kita bisa melihat bilangan prima yang lebih kecil dari 100. Nah, sebelum kita melanjutkan, kita perlu mengetahui terlebih dahulu bagaimana cara mencatat tanggal dan waktu pada Javascript. Kita bisa menggunakan objek Date. Kalau kita lihat deskripsinya di MDN, objek Date ini menyimpan tipe data Number, yang menunjukkan jumlah milidetik sejak tanggal 1 Januari 1970 zona waktu UTC.

Kita coba di console ya. Misalkan kita membuat sebuah variable dengan nama start, yang isinya adalah objek baru Date. Maka kodenya menjadi

let start = new Date();

Kalau kita panggil kembali variable start, maka browser menunjukkan tanggal dan waktu dari saat kita membuat objek Date tersebut. Perhatikan kalau kita panggil ulang, nilai variable ini tidak berubah.

Sekarang kita buat objek Date baru, tapi kali ini kita simpan di variable baru end.

let end = new Date();

Perhatikan kalau kita panggil kembali variable end. Nilainya ada perbedaan beberapa detik dibandingkan dengan variable start.

Kita bisa melakukan operasi pengurangan terhadap kedua variable ini. Jadi kalau end dikurangi dengan start, maka kita akan mendapatkan jumlah milidetik yang merupakan jarak waktu antara pertama kali kita mencatat waktu start dengan pada saat kita mencatat waktu end. Nah, dengan menggunakan cara seperti ini, kita bisa membuat semacam stopwatch untuk menghitung berapa jumlah waktu yang diperlukan untuk eksekusi fungsi yang telah kita buat.

Kita kembali ke kode kita. Namun sebelum melanjutkan, ada perlu saya ubah dahulu ya. Di bagian fungsi showPrimes. Saya tidak mau console.log ini berada di dalam loop. Karena kalau kita taruh di dalam loop, maka console.log dipanggil secara berkali-kali sehingga hasilnya menjadi terpisah dalam banyak baris. Saya ingin console.log dikeluarkan dan hanya dipanggil 1 kali saja setelah loop. Caranya? Pertama kita buat dahulu sebuah variable penampung hasil dengan nama result, dengan nilai awalnya string kosong. Di dalam loop, kita menambahkan variable result ini dengan nilai i dan spasi. Dan kemudian di luar loop, barulah kita panggil console.log untuk menampilkan nilai result. Terakhir kita kembalikan nilai result. Maka fungsi kita menjadi:

function showPrimes(max)
{
  let result = "";
  for(let i = 2; i <= max; i++)
  {
    if(isPrime(i))
    {
      result += i + " ";
    }
  }
  console.log(result);
  return result;
}

Kita simpan dan refresh browser. Sekarang hasil bilangan prima kita menjadi berurutan ke samping. Sudah bukan berurutan ke bawah lagi ya.

Selanjutnya kita buat fungsi baru profiler, untuk menghitung berapa jumlah waktu yang diperlukan untuk eksekusi fungsi kita. Parameter yang diperlukan adalah func, yaitu nama function yang ingin di eksekusi. Dan parameter kedua adalah max, yaitu jumlah data yang harus diproses. Isi fungsinya adalah objek Date seperti yang kita coba di console barusan ya. Jadi pertama kita buat dahulu variable start yang isinya adalah objek Date baru. Kemudian kita jalankan parameter func dengan menggunakan max sebagai argumentnya. Setelah itu kita buat lagi variable end yang isinya objek Date baru. Dan terakhir, kita tampilkan di console.log, kita gunakan template literal `Waktu eksekusi ${(end – start) / 1000} detik`. Lalu kita hapus kode yang memanggil fungsi showPrimes(100).

function profiler(func, max)
{
  let start = new Date();
  func(max);
  let end = new Date();
  console.log(`Waktu eksekusi ${(end - start)/1000} detik`);
}

Kita simpan dan jalankan di browser ya. Di console tidak ada hasil apa-apa. Harus kita yang memanggil fungsinya. Kita bisa memanggil fungsi profiler, dengan menggunakan argument nama fungsi showPrimes dan jumlah datanya. Pertama kita coba di jumlah data 100 terlebih dahulu.

profiler(showPrimes, 100);

Nah, waktu eksekusinya masih 0 detik ya. Kita naikkan jumlah datanya ke 1000. Sekarang hasilnya di sekitar 1 atau 2 milidetik ya. Kalau kita coba jalankan secara berulang-ulang, bisa dilihat hasil perhitungan waktunya ada sedikit berubah-ubah.

Kalau kita naikkan lagi jumlah datanya ke 10.000, maka hasilnya ada di sekitar 44 milidetik. Lalu kita naikkan lagi ke 100.000. Dan sekarang sudah mulai kelihatan lama ya. Di sekitar 2,3 detik.

Nah sekarang perhatikan. Kalau misalkan jumlah datanya saya naikkan ke 200.000. Artinya jumlah data naik 2 kali lipat ya. Kira-kira waktu yang dibutuhkannya naik berapa kali lipat? Jadi berapa detik?

Hasilnya ternyata di 8,9 detik ya. Jadi perkiraan kasarnya naik sekitar 4 kali lipat. Padahal jumlah datanya hanya naik 2 kali lipat saja ya. Sekarang jumlah datanya kita naikkan lagi 2 kali lipat menjadi 400.000. Kira-kira jadinya berapa detik?

Sekarang sudah lebih kelihatan lagi ya, seolah-olah komputer kita lagi hang. Padahal scriptnya sedang bekerja di background untuk menghasilkan bilangan prima yang lebih kecil dari 400.000. Dan waktu eksekusinya sudah keluar, yaitu di sekitar 34 detik. Artinya naik lagi di sekitar 4 kali lipat.

Artinya fungsi showPrimes yang kita buat ini, memiliki notasi O(n2). Setiap ada peningkatan jumlah data sebanyak 2 kali lipat, maka waktu yang diperlukan untuk menjalankan prosesnya meningkat sebanyak 4 kali lipat.

Kita lihat lagi ke dalam source codenya ya. Yang menyebabkan jumlah waktu meningkat secara signifikan adalah jumlah looping di dalam fungsi kita. Kalau kita lihat di dalam fungsi showPrimes, disini ada sebuah loop sebanyak jumlah datanya. Kemudian kita lihat lagi di dalam loop, kita memanggil fungsi isPrime, dimana di dalam fungsi ini terdapat sebuah loop lagi sebanyak jumlah data. Jadi disini ada looping bertingkat 2 sebanyak jumlah data. Oleh karena itu notasi dari fungsi kita adalah O(n2).

Sekarang pertanyaannya, apakah kita bisa melakukan optimasi terhadap fungsi showPrimes, sehingga bisa berjalan dengan lebih cepat? Dalam hal ini, optimasi yang memiliki efek paling besar adalah di bagian loopingnya.

Kalau kita mendalami lagi, rumus matematika untuk mencari faktor dari suatu bilangan, maka kita akan menemukan bahwa sebenarnya yang perlu kita tes di dalam fungsi isPrime, hanya bilangan 2 hingga akar dari n. Sebagai contoh, bilangan 27 yang nilai akarnya di sekitar 5,2. Artinya kita hanya perlu tes apakah 27 habis dibagi 2, apakah 27 habis dibagi 3, apakah 27 habis dibagi 4 dan apakah 27 habis dibagi 5? Dalam contoh ini 27 habis dibagi 3, artinya 27 bukanlah bilangan prima.

Dengan optimasi seperti ini, kita sudah tidak perlu melakukan tes apakah 27 habis dibagi dengan bilangan diantara 6 hingga 26. Mengapa sudah tidak perlu tes? Karena hasilnya sudah ketahuan dari keempat angka yang kita tes di awal tadi. Dalam contoh ini, ternyata 27 habis dibagi 3.

Kita ambil contoh bilangan lain yaitu 29. Akar dari 29 berada di sekitar 5,4. Artinya kita hanya perlu tes apakah 29 habis dibagi angka diantara 2 hingga 5. Dan berhubung angka 29 tidak ada yang habis dibagi 2, 3, 4, dan 5, maka kita sudah bisa langsung menyimpulkan bahwa 29 adalah bilangan prima.

Dengan menggunakan teori ini, maka kita bisa menuliskan kode baru yang jauh lebih cepat. Kita copy dahulu fungsi isPrime dan showPrimes. Kita paste di bagian bawah. Lalu kedua fungsi baru ini kita tambahkan angka 2 di nama fungsinya. Artinya ini versi kedua ya. Nah, di dalam fungsi isPrime2, kita ganti kondisi loop menjadi i <= Math.sqrt(n);. Sedangkan di dalam fungsi showPrimes2, kita memanggil fungsi isPrime2. Maka fungsi kita menjadi:

function isPrime2(n)
{
  for(let i = 2; i <= Math.sqrt(n); i++)
  {
    if(n % i == 0)
    {
      return false;
    }
  }
  return true;
}

function showPrimes2(max)
{
  let result = "";
  for(let i = 2; i <= max; i++)
  {
    if(isPrime2(i))
    {
      result += i + " ";
    }
  }
  console.log(result);
  return result;
}

Kita simpan dan jalankan di browser. Kita panggil fungsinya

showPrimes2(100);

Kemudian kita coba bandingkan hasil dari fungsi pertama.

showPrimes(100);
showPrimes(100) == showPrimes2(100);

Hasil keduanya sama persis ya. Sekarang kita tes lagi di perhitungan waktunya. Kita coba jalankan ulang showPrimes pertama dengan jumlah data 100.000 ya. Hasilnya di sekitar 2 detik. Kalau kita coba jalankan fungsi showPrimes2, dengan jumlah data yang sama hasilnya di sekitar 20 milidetik. Jauh lebih cepat ya.

profiler(showPrimes, 100000);
profiler(showPrimes2, 100000);

Selanjutnya kita coba gunakan lagi showPrimes2 dengan jumlah data 2 kali lebih banyak, di 200.000. Kira-kira berapa jumlah waktu yang diperlukan?

profiler(showPrimes2, 200000);

Ternyata di sekitar 49 milidetik ya. Jumlah waktu yang diperlukan meningkat di sekitar 2,2 kali lipat. Hampir setara dengan peningkatan jumlah datanya. Perbedaannya jauh kalau dibandingkan dengan showPrimes yang versi pertama, dimana jumlah waktunya meningkat sekitar 4 kali lipat. Sekarang kita coba lagi di jumlah data 400.000

profiler(showPrimes2, 400000);

Dan sekarang jumlah waktu yang diperlukannya meningkat ke 109 milidetik. Peningkatanya masih disekitar 2,2 kali lipat juga.

Jadi optimasi kita pada fungsi isPrime2, dimana loopingnya kita persingkat dari awalnya mesti sebanyak n, menjadi sebanyak akar dari n, menyebabkan notasi big O dari fungsi kita juga turut berubah. Yang awalnya fungsi kita adalah O(n2), berubah menjadi O(n log n). Dan untuk jumlah data yang besar, teman-teman bisa melihat sendiri ya perbedaannya. Di jumlah data 400.000, versi pertama membutuhkan waktu 32 detik. Sedangkan versi kedua hanya memerlukan waktu 0,1 detik.

Pertanyaan berikutnya, apakah fungsi untuk mencari bilangan prima ini masih bisa dioptimasi lagi menjadi O(n), sehingga waktu eksekusinya bisa lebih cepat lagi? Jawabannya adalah bisa. Namun kita perlu menggunakan struktur data array, yang masih belum pernah dibahas dalam video kita. Jadi untuk saat ini kita tidak membahas lebih lanjut mengenai bilangan prima. Namun bila teman-teman penasaran, bisa mencoba melakukan research sendiri ya.

Selanjutnya kita akan mencoba untuk membuat fungsi baru dengan notasi O(n). Misalkan kita buat fungsi dengan nama showSum, dengan menggunakan satu parameter max. Jadi kalau misalkan kita memanggil fungsi showSum dengan argument 5, maka fungsi kita akan menghitungkan nilai dari 1+2+3+4+5, dan mengembalikan hasilnya. Jadi di dalamnya kita buat dahulu variable result dengan nilai awal 0. Lalu kita lakukan looping dari 1 hingga <= max. Di dalam loop, kita tambahkan variable result dengan i. Lalu di luar looping, kita tampilkan nilai result. Dan akhirnya kita kembalikan nilai result.

Kita simpan dan coba hasilnya di browser. Misalkan kita panggil showSum(5). Hasilnya 15. Kita coba hitung di kalkulator ya. 1+2+3+4+5, dan hasilnya benar 15. Kalau kita coba lagi showSum(6) seharusnya menjadi 21.

Artinya fungsi kita sudah berjalan dengan benar ya. Sekarang kita sudah memiliki fungsi dengan notasi O(n). Sekarang kita coba jalankan fungsi ini untuk jumlah data 100.000. Jumlah waktunya di sekitar 1 atau 2 milidetik. Jauh lebih cepat ya kalau kita bandingkan dengan notasi O(n log n) pada fungsi showPrimes versi kedua.

Untuk mengukur waktu eksekusi dari fungsi ini, kita perlu menggunakan jumlah data yang lebih besar, yaitu 1.000.000. Dan ternyata jumlah waktunya adalah 6 milidetik.

Kita coba naikkan jumlah datanya 2 kali lipat, menjadi 2.000.000. Sekarang jumlah waktunya menjadi 12 milidetik. Jadi peningkatan jumlah waktunya kurang lebih sama dengan peningkatan jumlah datanya.

Dan untuk contoh terakhir, kita akan membuat versi kedua dari fungsi showSum, namun kali ini kita menggunakan notasi O(1), yang artinya fungsi tetap berjalan dalam jumlah waktu yang sama tidak peduli berapapun jumlah datanya. Ini adalah notasi yang paling bagus untuk semua fungsi, namun sayangnya tidak semua masalah bisa kita pecahkan dengan menggunakan notasi O(1). Untuk fungsi showSum, kebetulan ada rumus matematikanya yang bisa memberikan hasil yang sama persis tanpa perlu menghitung menggunakan looping.

Kita mulai buat fungsinya ya. Kita deklarasikan fungsi showSum2 dengan parameter max. Di dalamnya kita deklarasikan variable result yang nilainya menggunakan rumus ajaib matematika, yaitu max * (max + 1) / 2. Kemudian kita panggil console.log untuk menampilkan result. Dan terakhir kita kembalikan resultnya. Perhatikan bahwa fungsi ini tidak menggunakan loop sama sekali, sehingga waktu eksekusinya akan sama.

Kita simpan dan jalankan di browser. Kita coba jalankan dulu profiler untuk fungsi showSum pertama dengan jumlah data 10 juta sebagai bahan perbandingan ya. Kemudian kita jalankan lagi showSum2 dengan jumlah data 10 juta juga. Lihat ada perbedaan waktu eksekusi yang cukup besar ya. Versi pertama di sekitar 20 milidetik, sedangkan versi kedua tetap di 0 hingga 1 milidetik. Sedangkan nilai hasilnya tetap sama. Kalau kita panggil lagi showSum2 dengan jumlah data 1 triliun, waktu eksekusinya tetap sama di 0 hingga 1 milidetik. Sedangkan kalau kita memanggil fungsi lain dengan jumlah data 1 triliun, jumlah waktu eksekusinya akan lama sekali.

Oke sampai disini dulu video kita kali ini. Kita sudah mencoba berbagai fungsi dengan menggunakan berbagai notasi big O. Dimulai dari versi pertama dari showPrime yang menggunakan notasi O(n2), yang sudah mulai berasa berat di 100 ribu data. Kemudian kita membuat versi kedua showPrime dengan notasi O(n log n) yang bisa memproses hingga 1 juta data. Kita juga telah membuat fungsi showSum dengan notasi O(n) yang sanggup memproses hingga 10 juta data. Dan yang terakhir kita membuat versi kedua dari showSum yang menggunakan notasi O(1), yang sanggup memproses berapapun jumlah data yang kita kirimkan dalam waktu 1 milidetik.

Pelajaran yang bisa kita petik disini adalah komputer memerlukan waktu untuk memproses setiap data yang kita kirimkan ke dalam function. Semakin banyak data yang kita kirimkan, maka waktu prosesnya juga menjadi semakin lama. Yang paling mempengaruhi jumlah waktu eksekusi adalah jumlah loop yang kita gunakan di dalam function. Semakin banyak jumlah loop, maka jumlah waktunya menjadi semakin lama pula. Dan dengan mempelajari notasi big o ini, kita bisa menyadari kira-kira berapa jumlah data maksimal yang sanggup diproses oleh fungsi buatan kita.

Dengan menggunakan fasilitas tanya jawab, maka Anda bisa bertanya dan akan dijawab langsung oleh instruktur kursus.

Anda belum terdaftar pada kursus ini sehingga tidak bisa mengajukan pertanyaan.