Algoritma adalah urutan
langkah-langkah logis penyelesaian masalah yang disusun secara sistematis dan
logis.
Sebuah algoritma tidak saja harus benar, tetapi juga harus efisien. Algoritma yang bagus adalah algoritma
yang efektif dan efisien. Untuk dapat mengetahui seberapa
efisien suatu algoritma, dipakailah teori kompleksitas algoritma sebagai dasar
kajian. Kompleksitas terbagi atas dua, yaitu kompleksitas waktu dan
kompleksitas ruang.
Kompleksitas Waktu, T(n), adalah jumlah operasi yang dilakukan untuk melaksanakan
algoritma sebagai fungsi dari ukuran masukan n.
Maka, dalam mengukur kompleksitas waktu dihitunglah banyaknya operasi yang dilakukan
oleh algoritma. Idealnya, kita memang harus menghitung semua operasi yang ada
dalam suatu algoritma. Namun, untuk lasan praktis, cukup menghitung jumlah
operasi abstrak yang mendasari suatu algoritma. Operasi abstrak ini disebut
Operasi Dasar.
Pada algoritma pengurutan, terutama pada pengurutan dengan
perbandingan, operasi dasar adalah operasioperasi perbandingan elemen-elemen
suatu larik dan operasi pertukaran elemen. Kedua hal itu dihitung secara terpisah,
karena jumlah keduanya tidaklah sama. Biasanya kompleksitas algoritma
dinyatakan secara asimptotik dengan notasi big-O. Jika kompleksitas
waktu untuk menjalankan suatu algoritma dinyatakan dengan T(n), dan
memenuhi T(n) ≤ C(f(n)) untuk n ≥ n0, maka kompleksitas dapat
dinyatakan dengan:
Terdapat
2 jenis penggunaan notasi Big O, yaitu :
- Infinite asymptotics
- Infinitesimal asymptotics
Perbedaan
kedua jenis penggunaan notasi ini hanya pada aplikasi. Sebagai contoh, pada infinite
asymptotics dengan persamaan
Untuk
n yang besar, pertumbuhan T(n) akan sebanding dengan n2 dan dengan mengabaikan suku
yang tidak mendominasi kita, maka kita tuliskan:
Pada
infinitesimal asymptotics, Big O digunakan untuk menjelaskan kesalahan
dalam aproksimasi untuk sebuah fungsi matematika, sebagai contoh:
Kesalahannya
memiliki selisih:
