Panduan Permulaan untuk Notasi Big O

Big O Notation adalah cara untuk mewakili berapa lama algoritma akan dilaksanakan. Ia membolehkan Jurutera perisian menentukan seberapa berkesan pendekatan berbeza untuk menyelesaikan masalah.

Berikut adalah beberapa jenis kerumitan masa yang biasa dalam Notasi Big O.

  • O (1) - Kerumitan masa yang berterusan
  • O (n) - Kerumitan masa linear
  • O (log n) - Kerumitan masa logaritma
  • O (n ^ 2) - Kerumitan masa kuadratik

Semoga pada akhir artikel ini anda akan dapat memahami asas-asas Big O Notation.

O (1) - Masa Tetap

Algoritma masa yang berterusan akan memerlukan masa yang sama untuk dilaksanakan. Masa pelaksanaan algoritma ini tidak bergantung pada ukuran input. Contoh masa O (1) yang baik adalah mengakses nilai dengan indeks tatasusunan.

var arr = [ 1,2,3,4,5];
arr[2]; // => 3

Contoh lain termasuk: operasi push () dan pop () pada array.

O (n) - Kerumitan masa linear

Algoritma mempunyai kerumitan masa linear jika masa untuk melaksanakan algoritma berkadar terus dengan ukuran input n . Oleh itu, masa yang diperlukan untuk menjalankan algoritma akan meningkat secara berkadar apabila ukuran input n meningkat.

Contoh yang baik ialah mencari CD dalam timbunan CD atau membaca buku, di mana n adalah bilangan halaman.

Contoh di O (n) adalah menggunakan carian linear:

//if we used for loop to print out the values of the arrays
for (var i = 0; i < array.length; i++) { console.log(array[i]);}
var arr1 = [orange, apple, banana, lemon]; //=> 4 steps
var arr2 = [apple, htc,samsung, sony, motorola]; //=> 5 steps

O (log n) - Kerumitan masa logaritma

Algoritma mempunyai kerumitan masa logaritmik jika masa yang diperlukan untuk menjalankan algoritma berkadaran dengan logaritma ukuran input n . Contohnya ialah carian binari, yang sering digunakan untuk mencari set data:

//Binary search implementationvar doSearch = function(array, targetValue) { var minIndex = 0; var maxIndex = array.length - 1; var currentIndex; var currentElement; while (minIndex <= maxIndex) { currentIndex = (minIndex + maxIndex) / 2 | 0; currentElement = array[currentIndex]; if (currentElement  targetValue) { maxIndex = currentIndex - 1; } else { return currentIndex; } } return -1; //If the index of the element is not found.};
var numbers = [11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33];
doSearch(numbers, 23) //=>; 6

Contoh lain kerumitan masa logaritma termasuk:

Example 1;
for (var i = 1; i < n; i = i * 2) console.log(i);}
Example 2;
for (i = n; i >= 1; i = i/2) console.log(i);}

O (n ^ 2) - Kerumitan masa kuadratik

Algoritma mempunyai kerumitan waktu kuadratik jika waktu pelaksanaannya sebanding dengan kuadrat ukuran input. Contoh yang baik ialah memeriksa sama ada terdapat pendua dalam setumpuk kad.

Anda akan menghadapi kerumitan waktu kuadratik dalam algoritma yang melibatkan lelaran bersarang, seperti bersarang untuk gelung. Sebenarnya, gelung bersarang yang lebih dalam akan menghasilkan O (n ^ 3), O (n ^ 4), dll.

for(var i = 0; i < length; i++) { //has O(n) time complexity for(var j = 0; j < length; j++) { //has O(n^2) time complexity // More loops? }}

Contoh lain kerumitan waktu kuadratik termasuk jenis gelembung, jenis pemilihan, dan jenis penyisipan.

Artikel ini hanya menggaru permukaan Notasi Big O. Sekiranya anda ingin mengetahui lebih lanjut mengenai Big O Notation, saya cadangkan untuk memeriksa Big-O Cheat Sheet.