Big O Notation
3 min readMay 17, 2021
CARA MENENTUKAN KOMPLEKSITASKita dapat menentukan kompleksitas berdasarkan jenis pernyataan yang digunakan oleh suatu program. Contoh berikut ada di java tetapi dapat dengan mudah diikuti jika Anda memiliki pengalaman pemrograman dasar dan menggunakan notasi O besar, kami akan menjelaskan nanti mengapa notasi O besar umum digunakan:
Constant time: O(1)
Operasi berikut membutuhkan waktu yang konstan:- Menetapkan nilai ke beberapa variabel
- Memasukkan elemen dalam sebuah array
- Menentukan apakah bilangan biner genap atau ganjil.
- Mengambil elemen i dari larik
- Mengambil nilai dari tabel hash (kamus) dengan kunciMereka membutuhkan waktu yang konstan karena itu adalah pernyataan "sederhana". Dalam hal ini kita katakan waktu pernyataan adalah O (1)
Seperti yang Anda lihat pada grafik di bawah ini, waktu konstan tidak berbeda dengan ukuran input. Mendeklarasikan variabel, memasukkan elemen dalam tumpukan, memasukkan elemen ke dalam daftar tertaut yang tidak diurutkan, semua pernyataan ini membutuhkan waktu yang konstan.
Linear time: O(n)
Loop berikutnya mengeksekusi N kali, jika kita menganggap pernyataan di dalam loop adalah O (1), maka total waktu untuk loop adalah N * O (1), yang sama dengan O (N) juga dikenal sebagai waktu linierPada grafik berikut kita dapat melihat bagaimana waktu berjalan meningkat secara linier dalam kaitannya dengan jumlah elemen n:
Quadratic time: O(n2)
Dalam contoh ini loop pertama mengeksekusi N kali. Untuk setiap kali loop luar dijalankan, loop dalam mengeksekusi N kali. Oleh karena itu, pernyataan dalam loop bersarang mengeksekusi total N * N kali. Di sini kompleksitasnya adalah O (N * N) yang sama dengan O (N2). Ini harus dihindari karena kompleksitas ini tumbuh dalam waktu kuadrat
Logarithmic time: O(Log n)
Waktu logaritmik tumbuh lebih lambat saat N tumbuh. Cara mudah untuk memeriksa apakah sebuah loop adalah log n adalah dengan melihat apakah variabel penghitungan (dalam hal ini: i) berlipat ganda dan bukan bertambah 1. Dalam contoh berikut int i tidak bertambah 1 (i ++), itu berlipat ganda dengan setiap proses sehingga melintasi loop dalam waktu log (n):
Linearithmic time: O(n*Log n)
Algoritme linieritmik mampu berkinerja baik dengan kumpulan data yang sangat besar. 
Kesimpulan
Seperti yang mungkin telah Anda ketahui, notasi Big O menggambarkan kemungkinan terburuk. Saat Anda mengulang melalui sebuah larik untuk menemukan apakah itu berisi item X, kasus terburuknya adalah larik itu ada di akhir atau bahkan tidak ada dalam daftar. Membuat Anda mengulang melalui semua n item, jadi O (n). Kasus terbaik adalah item yang kita cari berada di awal sehingga setiap kali kita mengulang membutuhkan waktu yang konstan untuk mencari tetapi ini sangat tidak umum dan menjadi lebih tidak mungkin karena daftar item bertambah. Di bagian selanjutnya kita akan melihat lebih dalam mengapa O besar berfokus pada analisis kasus terburuk.Perbandingan empat kerumitan pertama, mungkin memungkinkan Anda memahami mengapa untuk kumpulan data besar kita harus menghindari waktu kuadrat dan berusaha menuju waktu logaritmik atau linieritmik:
