13
2.3.1.3 Notasi Big O
Dalam teori
perhitungan
kompleksitas,
notasi
Big
O
digunakan
untuk
menggambarkan bagaimana ukuran data input
mempengaruhi kecepatan dan
penggunaan
memori. Notasi
Big O
juga disebut sebagai notasi
Bachman-Landau,
atau
notasi
asimtotis.
Notasi
Big
O juga
digunakan
pada
matematika
untuk
menghasilkan estimasi yang mirip.
Berikut adalah contoh dari notasi Big O:
Tabel 2.1 Notasi Big O
Notasi
Nama
Contoh
?1
Konstan
Menentukan genap-ganjil suatu angka
???
??
Ackermann invers
?log?
?
Logaritmik beriterasi
Hopcroft and Ullman search dengan
menggunakan disjoint set
?log
?
Logaritmik
Binary search
??log
?
Polilogaritmik
Tes Primalitas AKS
?
?
Akar
Pencarian pada KD-Tree
?
?
Linear
Sequencial search
?
log
?
Linearitmik, Loglinear
Heapsort, Fast Fourier Transform
?
?
?
Kuardratik
Insertion Sort
?
?
Polinomial
Algoritma Floyd-Warshall
?
?
?
Eksponensial
Travelling Sales Problem
?
!?
Faktorial
Brute Force
?
?
?
Eksponensial n
?
1
?
?
?
Eksponensial ganda
Notasi
Big
O
sangat
berguna
dalam
analisa
algoritma
dalam hal
efisiensi.
Contohnya, waktu atau jumlah langkah yang dibutuhkan untuk menyelesaikan
suatu persoalan dengan ukuran data n dapat dihitung sebagai berikut
?
?
4
?
2
2
 |