Notasi Big O

Contoh

Contoh-contoh berikut ini semuanya menggunakan kode yang ditulis dalam Python. Perhatikan bahwa ini bukan daftar lengkap tipe Big O.

Konstan

O ( 1 ) {\displaystyle O(1)} . Selalu membutuhkan jumlah waktu yang sama terlepas dari inputnya. Sebagai contoh, ambil sebuah fungsi yang menerima sebuah bilangan bulat (disebut x) dan mengembalikan nilainya dua kali lipat:

Setelah menerima input, fungsi ini akan selalu mengambil satu langkah untuk mengembalikan output. Hal ini konstan karena akan selalu mengambil jumlah waktu yang sama, sehingga O ( 1 ) {\displaystyle O(1)} .

Linear

O ( n ) {\displaystyle O(n)} . Meningkat sesuai dengan ukuran input, diwakili oleh n {\displaystyle n} . Mari kita asumsikan sebuah fungsi menerima n, dan mengembalikan setiap angka dari 1 sampai n:

Jika kita memasukkan nilai 5 maka ini akan menghasilkan 1 , 2 , 3 , 4 , 5 {\displaystyle 1,2,3,4,5}. , membutuhkan 5 loop untuk menyelesaikannya. Demikian pula, jika kita memasukkan 100 maka akan menghasilkan 1 , 2 , 3...98 , 99 , 100 {\\displaystyle 1,2,3...98,99,100} , yang membutuhkan 100 loop untuk menyelesaikannya. Jika masukannya adalah n {\displaystyle n} maka waktu berjalan algoritma ini tepat n {\displaystyle n} loop setiap kali, oleh karena itu O ( n ) {\displaystyle O(n)} .

Faktorial

O ( n! ) {\displaystyle O(n!)} . Meningkat dalam jumlah faktorial, yang berarti waktu yang dibutuhkan meningkat secara besar-besaran dengan input. Sebagai contoh, katakanlah kita ingin mengunjungi lima kota di seluruh dunia dan ingin melihat setiap kemungkinan urutan (permutasi). Algoritma yang dapat kita tulis menggunakan library itertools Python adalah sebagai berikut:

Algoritma ini akan menghitung setiap permutasi unik dari kota-kota kita dan kemudian mengeluarkannya. Contoh keluaran akan mencakup:

('London', 'Paris', 'Berlin', 'Amsterdam', 'Roma') ('London', 'Paris', 'Berlin', 'Roma', 'Amsterdam') ('London', 'Paris', 'Amsterdam', 'Berlin', 'Roma') ... ('Roma', 'Amsterdam', 'Paris', 'Berlin', 'London') ('Roma', 'Amsterdam', 'Berlin', 'London', 'Paris') ('Roma', 'Amsterdam', 'Berlin', 'Paris', 'London')

Di sini daftar input kita terdiri dari 5 item, dan untuk setiap pilihan, pilihan yang tersisa berkurang 1. Dengan kata lain, 5 input kita memilih 5 × 4 × 3 × 2 × 1 {\\displaystyle 5\kali 4\kali 3\kali 2\kali 1} item (atau 5 ! {\\displaystyle 5!} ). Jika input kita adalah n {\displaystyle n} kota maka jumlah outputnya adalah n ! {\displaystyle n! } ; dengan kata lain, dengan asumsi kita melalui setiap permutasi, kita akan memerlukan O ( n! ) {\displaystyle O(n!)} loop untuk menyelesaikannya.

Notasi Little-o

Versi yang lebih ketat dari Big O adalah little-o. Perbedaan antara big O dan little-o adalah bahwa little-o adalah batas atas yang ketat: sementara O ( n ) {\displaystyle O(n)} berarti waktu penyelesaian akan meningkat hingga maksimum ini berdasarkan ukuran input, o ( n ) {\displaystyle o(n)} berarti waktu penyelesaian umumnya akan berada di bawah jumlah waktu ini. Dengan kata lain, Big O mengasumsikan setiap loop akan mengambil jalur terpanjang dan prosesnya akan memakan waktu selama mungkin, sedangkan little-o lebih realistis tentang waktu penyelesaian yang sebenarnya; jika jumlah loop didasarkan pada lemparan dadu 6 sisi Big O akan selalu mengasumsikan angka 6 yang dilempar, sedangkan little-o akan memperhitungkan probabilitas yang sama dengan angka-angka lain yang dilempar.