DEV Community: Luthfi Aji Wicaksono

Big O: [3] Menghitung Operasi

Luthfi Aji Wicaksono — Fri, 16 Aug 2019 10:39:40 +0000

Bismillahirrahmaanirrahim,

Pada artikel sebelumnya saya katakan bahwa menggunakan waktu dengan bantuan method performance milik Javascript sebagai tolak ukur merupakan cara yang kurang bisa diandalkan. Lantas jika bukan menggunakan waktu lalu mengunakan apa?

Jadi begini, pada artikel sebelumnya kita itu ingin mengetahui kode mana yang memiliki waktu proses paling cepat dengan mengukurnya menggunakan waktu juga, waktu diukur dengan waktu.

Nah, sekarang ini kita tidak melakukan hal itu. Kita akan memprediksi kode mana yang lebih cepat dengan cara menghitung operasi-operasi pada kode tersebut yang akan dilakukan oleh komputer.

Yang namanya prediksi kita tidak akan mendapat nilai pasti berapa detik kode tersebut berjalan, namun untungnya kita tidak perlu melakukan serangkaian proses seperti pada artikel sebelumnya, dan untungnya lagi bahwa prediksi yang akan kita lakukan insyaallah 100% akurat.

Mengapa kita melakukan perhitungan operasi yang dimiliki oleh suatu kode?
Itu karena operasi-operasi yang ada pada kode tersebut selalu memiliki nilai konstan, tidak seperti waktu yang kadang berubah-ubah.

Jadi misalkan kita memiliki dua algoritma, yang satu memiliki 5 operasi dan yang satunya lagi memiliki 10 operasi. Maka kita tidak perlu lagi khawatir dengan spesifikasi komputer yang kita gunakan, entah inputan yang diberikan itu bernilai kecil ataupun besar pengaruh eksternal tidak bisa ikut campur lagi di sini.

Dan, sebuah runtime akan selalu berbanding lurus dengan jumlah operasi yang dijalankan.

Langsung saja kita bedah kode dari contoh pada artikel sebelumnya dengan menghitung operasi yang dimiliki oleh masing-masing kode. Dimulai dari sang pemenang,

Bisa kita lihat, ada 3 operasi yang berjalan pada fungsi di atas. 1 penjumlahan, 1 perkalian dan 1 pembagian. Berapapun nilai n nya maka operasi yang berjalan tetap 3. Entah itu 100 atau bahkan 1 triliun, operasi yang berjalan akan selalu 3 kali.

Sekarang kita berpindah ke kode yang ke dua, dan ini dia

Weww, sekarang kita bedah satu persatu, dimulai dari yang ini,

Yang berbeda pada kode kali ini adalah, kita menggunakan perulangan for. Maka 2 operasi di atas berjalan bergantung pada variabel n. Maka dari itu ditulis n Penjumlahan dan n Pemberian Nilai. Sebenarnya sintaks jumlah += i adalah ringkasan dari sintaks jumlah = jumlah + i.

Selanjtunya adalah,

Operasi yang berada pada i++. Operasi itu juga sama seperti yang sebelumnya, yakni penjumlahan dan pemberian nilai. Karena i++ merupakan ringkasan dari i = i + 1.

Selanjutnya,

Kita memiliki 2 operasi pemberian nilai, operasi ini tidak bergantung pada n karena berada di luar jangkauan perulangan. Operasi ini hanya berjalan satu kali saat fungsi pertama kali dipanggil untuk memberikan nilai awal.

Dan yang terakhir adalah,

n operasi perbandingan. Operasi ini akan terus membandingkan nilai i dengan n, jika masih bernilai true maka perulangan akan terus berjalan sampai akhirnya perbandingan ini bernilai false dan perulangan akan berhenti.

Hmm, lalu jumlah operasi pada kode ini ada berapa?

Jika sudah seperti ini maka akan sedikit merepotkan karena kita tidak memiliki nilai konstan seperti pada kode yang pertama tadi. Kita hanya memiliki nilai n yang sejatinya bukan nilai yang statis.

Maka kita simpulkan dari uraian di atas bahwa jumlah operasi dari perhitungan di atas adalah 5n+2. Dimana ada 5n operasi dan 2 operasi konstan. jika n = 5 maka jumlah operasi dari kode di atas adalah 27.

Selanjutnya kita sederhanakan lagi kesimpulan dari rumus 5n+2 di atas. Bahwa sebenarnya nilai pasti seperti 5 dan 2 itu tidak usah terlalu dipikirkan dan kita hanya berfokus pada pertumbuhan jumlah n saja. Kita akan melihat teori tentang ini lebih banyak lagi ke depannya.

Jadi, kesimpulan yang sebenarnya adalah Pertumbuhan n akan memengaruhi jumlah operasi. Karena jumlah operasi akan selalu berbanding lurus dengan pertumbuhan n.

Oke, cukup sekian dulu pembahasan kali ini. Di artikel selanjutnya kita akan membahas mengenai Time Complexity.

Jika ada kritik dan saran bisa langsung disampaikan. Terimakasih dan Sampai Jumpa ! :D

Big O: [2] Pengaturan Waktu Pada Kode Kita

Luthfi Aji Wicaksono — Thu, 15 Aug 2019 16:56:56 +0000

Bismillahirrahmanirrahim, Mari kita lanjutkan pembahasan tentang Big O Notation dari artikel sebelumnya. Bagi yang belum membaca artikel sebelumnya mungkin bisa dibaca terlebih dulu : Pendahuluan Big O

Sekarang kita akan masuk pada contoh konkrit yang akan sedikit menyenggol Big O Notation

Contoh:
Kita misalkan bahwa kita akan menulis sebuah fungsi yang akan menjumlahkan bilangan 1 sampai dengan n, 1+2+3. . .+n dan satu contoh solusi yang paling mudah dari permasalahan tersebut adalah sebagai berikut:

function jumlahDeret(n) {
 var jumlah = 0;

 for(var i = 1; i <= n; i++) {
  jumlah += i;
 };

 return jumlah;
}

Kita men-set nilai awal dari variabel jumlah sebesar 0. Kemudian for akan melakukan perulangan mulai dari bilangan 1 berdasarkan statement var i = 1; sampai dengan bilangan n berdasarkan statement i <= n;
dan kemudian pada setiap iterasinya i akan dijumlahkan dengan variabel jumlah berdasarkan aksi jumlah += i;

Setelah perulangan selesai maka fungsi akan mengembalikan nilai jumlah.

Selanjutnya kita panggil fungsi tersebut untuk melakukan penjumlahan, untuk melihat hasilnya kita dapat menggunakan console.log.

console.log(jumlahDeret(3));

Dan output-nya adalah 6, yang berarti 1+2+3.

Oke, selanjutnya contoh solusi yang kedua adalah sebagai berikut:

function jumlahDeret(n) {
 return n * (n + 1) / 2;
}

Dari contoh yang kedua ini kita bisa melihat banyak sekali perbedaan, bahkan benar-benar berbeda dari contoh yang pertama. Pada contoh yang kedua ini kita tidak menggunakan perulangan, melainkan kita hanya menggunakan formula matematika yaitu n * (n + 1) / 2

Jika kita jalankan dengan memberikan nilai n yang sama yaitu 3 maka outputnya pun akan sama, 6.

console.log(jumlahDeret(3));

// 3 * (3 + 1) / 2

Nah, di sinilah topik utama pembahasan kita kali ini. Mana solusi yang lebih baik? Contoh 1 atau Contoh 2 ?

Sebelum melangkah jauh ke sana, mari kita uraikan lagi tentang arti lebih baik.

Apa yang dimaksud lebih baik di sini?

Apakah maksudnya adalah lebih cepat saat melakukan penghitungan? bahkan dengan bilangan yang lebih besar? seperti bilangan 1 juta misalnya, atau 1 miliar?
Apakah lebih sedikit memakan memori? yang digunakan untuk menyimpan hasil penghitungan yang dilakukan saat fungsi dipanggil?
Atau apakah kodenya mudah dibaca oleh orang lain?

Hmm baiklah, sebenarnya semua arti di atas adalah arti yang valid. Dimana arti kata lebih baik mencakup dari ketiganya. Namun kita akan memfokuskan pembahasan kita pada arti lebih cepat dan lebih sedikit memakan memori karena kedua hal tersebut lebih penting ketimbang arti mudah dibaca.

Kita akan lebih dulu fokus mengevaluasi mana solusi yang memiliki runtime paling cepat. 1 atau 2?

Kita akan menggunakan fungsi bawaan milik Javascript untuk melakukan perhitungan waktu yaitu dengan method performance. Jadi kodenya seperti ini,

Contoh 1

function jumlahDeret(n) {
 var jumlah = 0;

 for(var i = 1; i <= n; i++) {
  jumlah += i;
 };

 return jumlah;
}

var w1 = performance.now();
jumlahDeret(1000000000);
var w2 = performance.now();

console.log(`Waktu berlalu: ${(w2 - w1) / 1000} detik`);

Variabel w1 akan memberitahu kita berapa milidetik yang berlalu sejak document dibuat. Terutama waktu yang didapatkan pada saat window terbuka, kemudian kita menyimpan waktu yang sudah didapatkan tersebut ke dalam variabel w1 sebelum fungsi jumlahDeret() kita panggil.

Selanjutnya kita memanggil fungsi jumlahDeret() yang argumennya berupa bilangan sebesar 1 miliar.

Kemudian kita dapatkan lagi waktu performance setelah fungsi jumlahDeret() dijalankan. Seharusnya ada penambahan beberapa milidetik akibat proses dari fungsi jumlahDeret() yang dipanggil.

Oke, kita sudah memiliki dua bilangan sekarang yaitu w1 dan w2. Untuk mendapatkan selisih waktunya maka kita gunakan formula matematika w2 - w1 / 1000. Kenapa dibagi 1000? itu karena untuk mengonversi dari milidetik ke detik.

Dan output yang saya dapatkan dari contoh 1 adalah sebagai berikut:

Waktu berlalu: 1.3605600000009872 detik

Output bisa berubah-ubah karena berkaitan dengan waktu proses.

Selanjutnya kita lakukan cara yang sama pada contoh 2:

function jumlahDeret(n) {
 return n * (n + 1) / 2;
}

var w1 = performance.now();
jumlahDeret(1000000000);
var w2 = performance.now();

console.log(`Waktu berlalu: ${(w2 - w1) / 1000} detik`);

Dan output yang saya dapatkan adalah:

Waktu berlalu: 0.00009499999578110874 detik

Sekarang kita sudah mengetahui mana solusi yang memiliki runtime atau waktu proses yang lebih singkat dengan data inputan yang sama yaitu 1 miliar.

Dan jreng jreng jreng, pemenangnya adalah Contoh 2.

Proses yang saya contohkan di atas sebenarnya bukanlah yang paling dapat diandalkan dalam pengaturan waktu.

Seperti sebelum dan sesudah kemudian membandingkannya dengan fungsi yang lain. Bagaimana fungsi yang ini lebih efisien daripada fungsi yang itu? apakah berdasarkan persentase kecepatannya? atau apakah karena saya melakukan pengurangan terhadap milidetiknya? ini jadi agak sedikit kurang jelas.

Itu semua membawa kita pada permasalahan terhadap waktu, yang menjadikannya kurang dapat diandalkan. Apa saja masalahnya?

Mesin yang berbeda akan merekam penggunaan waktu yang berbeda pula, pengaturan waktu jadi bergantung pada spesifikasi komputer/laptop yang kita punya.
Bahkan mesin yang sama pun akan merekam penggunaan waktu yang berbeda,
Jadi, untuk mendapatkan algoritma yang cepat, menggunakan metode kecepatan waktu tidaklah cukup

Lalu bagaimana cara kita menelusuri kode kita dan berbicara secara umum tentang kode mana yang lebih baik?

Saya tidak bilang kalau menggunakan metode ini merupakan ide yang buruk. Tapi alangkah baiknya jika ada cara lain yang tidak perlu melibatkan men-setup file baru untuk mendapatkan waktu seperti cara di atas.

Sekarang kita hanya melakukan tes pada kode yang hanya memakan waktu tidak sampai lima detik.

Lalu bagaimana jika kita memiliki kode yang membutuhkan waktu satu jam untuk sesuatu yang besar dan kita membandingkannya dengan versi lain yang membutuhkan waktu empat jam?

Kita tidak ingin melakukan tes tersebut untuk mencari tahu mana yang lebih cepat. Yang kita mau hanya memberikan nilai dan kemudian berbicara secara umum bagaimana membandingkan kode tanpa harus melakukan semua cara di atas.

Itulah yang akan dilakukan oleh Big O, dan akan hadir di artikel berikutnya. Sampai Jumpa ! :)

Big O: [1] Pendahuluan Big O

Luthfi Aji Wicaksono — Thu, 15 Aug 2019 09:57:40 +0000

Bismillahirrahmanirrahim,

Dimulai dari artikel ini, saya akan mencoba merangkum materi yang sudah saya kumpulkan tentang Big O Notation dari berbagai sumber yang sudah tersedia di internet. Dan bahasa pemrograman yang akan saya gunakan sebagai pengantar adalah bahasa Javascript.

Mengenai pembahasan tentang Big O ini, saya akan menjadikannya ber-series dan membaginya per bagian-bagian supaya lebih ringkas, cepat dan urut dalam memahami dan mempelajarinya.

Akan ada beberapa bagian yang sedikit mengandung unsur matematik. Tapi tenang, kuasai dan jangan panik! Karena untuk memahami Big O tidak terlalu diperlukan pemahaman matematika yang pekat. Cukup siapkan mental dan keinginan yang kuat seperti saat kau ingin mendapatkan hatinya, eh.

Karena bahasa yang saya gunakan disini adalah Javascript, maka akan sangat membantu jika kamu sudah menguasai sintaksis dasar milik Javascript. Tapi tak mengapa jika kamu ingin mencoba mengikuti materi dengan bahasa pemrograman yang sudah kamu kuasai sekarang, saya yakin kamu pasti bisa.

Oke, objektif-objektif kita pada materi ini adalah:

Memotivasi kebutuhan akan sesuatu seperti Big O Notation, sebagai seorang programmer atau developer terkadang kita hanya peduli pada kode yang kita tulis, asalkan kode itu berhasil berjalan tanpa error, kita senang dan kita tidak peduli pada performanya. Disinilah kita akan menumbuhkan rasa ~~sayang~~ peduli kita akan performa kode yang kita tulis.
Mendeskripsikan Apa itu Big O Notation?
Menyederhanakan ekspresi-ekspresi Big O
Menjelaskan tentang Time Complexity dan Space Complexity
Mengevaluasi Time Complexity dan Space Complexity dari algoritma yang berbeda menggunakan Big O Notation
Mendeskripsikan apa itu logaritma

Baiklah, tarik napas dalam-dalam dan keluarkan perlahan lewat pori-pori kulit.

Kita akan mulai objektif kita pada poin pertama yaitu Menumbuhkan rasa butuh pada Big O Notation.

Pembahasan materi ini sejatinya adalah tentang Algoritma, yaitu tentang memecahkan tantangan-tantangan dan masalah-masalah.

Pada setiap bagian nantinya akan ada banyak cara untuk memecahkan tantangan yang bermacam-macam dan semuanya berhasil diimplementasikan.

Tapi selanjutnya bagaimana kita bisa tahu mana cara yang terbaik untuk diterapkan?

Oke, mari kita ambil sebuah contoh; jika kita memiliki dua cara implementasi berbeda pada satu fungsi yang sama, lalu bagaimana cara kita menentukan mana implementasi yang terbaik?

Disinilah peran Big O hadir, Big O adalah sebuah cara untuk menggeneralisasi kode, kemudian membandingkan kode tersebut dan membandingkan performanya dengan kode yang lain.

Misalkan, Tulislah sebuah fungsi yang menerima string sebagai argumennya dan mengembalikan string tersebut secara terbalik.

reverse('helloww') => 'wwolleh'

Ada 10 cara berbeda yang saya temukan di stackoverflow, kamu bisa lihat di sini.

Nah, akan lebih baik jika ada sebuah sistem yang mengurutkan klasifikasi kode tersebut sehingga kita bisa memberi label dari yang terbaik hingga yang terburuk. Ilustrasi nya seperti di bawah ini,

Big O memiliki ekspresi yang mewakili label-label di atas, tetapi agak sedikit matematis. Untuk sekarang gambar di atas akan sedikit lebih membantu kita untuk membayangkan seperti apa Big O itu.

WHO CARES?

Siapa yang peduli pada hasil dari fungsi di atas tadi? tidak ada yang peduli!

Yang harus kita pedulikan sekarang adalah bagaimana cara kita memilih performa terbaik dari algoritma yang kita buat untuk fungsi tersebut.

Karena yang ditanyakan dalam interview-interview perusahaan besar, yang memiliki ribuan data, adalah bagaimana kita membuat sebuah algoritma yang dapat menghemat waktu sesingkat-singkatnya dan secepat-cepatnya dalam memroses data tersebut.

Performa akan sangat diperhatikan disini dan dari situlah hadir solusi atau algoritma terbaik.

Maka:

Penting untuk memilih diksi atau kosa kata yang tepat untuk menjelaskan bagaimana kode kita berjalan
Akan sangat baik mendiskusikan kekurangan dari masing-masing cara yang digunakan
Ketika kode kita berjalan lambat atau bahkan crash, identifikasilah bagian kode mana yang tidak efisien sehingga kita dapat memperbaiki kualitas kode yang dibuat. Jadi jangan hanya mencari error nya saja, tapi juga pahami cara kerja dari setiap baris kode yang ditulis, dan itulah yang akan di bahas pada materi Big O.

Sedikit informasi, bahwa pada saat kamu menjalani interview kerja, maka teori Big O ini seringkali ditanyakan untuk mengetahui seberapa paham kamu dengan apa yang kamu tuliskan. Jadi ikuti terus materi tentang Big O ini, Oke?

Sepertinya kita cukupkan dulu sedikit perkenalan tentang Big O Notation di sini. Dan pada artikel selanjutnya kita akan mulai membahas contoh-contoh kode dan mencari tahu efisiensi dari kode tersebut.

Semoga yang sedikit ini bisa bermanfaat, sampai bertemu lagi :)