Untuk menyelesaikan suatu masalah, akan terdapat berbagai algoritma yang dapat digunakan, sesuai dengan salah satu pepatah popular, “Ada banyak jalan menuju Roma.” Akan tetapi, algoritma manakah yang harus dipilih agar masalah itu dapat diselesaikan dengan efektif? Tentu harus ada parameter yang bisa dibandingkan.
Dalam aplikasinya, setiap algoritma memiliki dua buah ciri khas yang dapat digunakan sebagai parameter pembanding, yaitu jumlah proses yang dilakukan dan jumlah memori yang digunakan untuk melakukan proses. Jumlah proses ini dikenal sebagai kompleksitas waktu yang disimbolkan dengan T(n), sedangkan jumlah memori ini dikenal sebagai kompleksitas ruang yang disimbolkan dengan S(n).
Kompleksitas waktu diukur berdasarkan jumlah proses khas suatu algoritma, bukan berdasarkan run-time secara nyata ketika aplikasi dilakukan. Hal ini disebabkan oleh arsitektur komputer dan kompiler yang berbeda-beda, sehingga suatu algoritma yang sama akan menghasilkan waktu eksekusi yang berbeda, pada komputer dan kompiler yang berbeda.
Dalam setiap algoritma, terdapat berbagai jenis operasi, di antaranya :
- Operasi baca tulis.
- Operasi aritmatika (+ - / *)
- Operasi pengisian nilai (assignment)
- Operasi pengaksesan elemen larik
- Operasi pemanggilan fungsi ataupun
prosedur.
Dalam perhitungan kompleksitas algoritma, kita hanya menghitung operasi khas (tipikal) yang mendasari
algoritma tersebut.
Kompleksitas Waktu Asimptotik
Kenyataannya, jarang sekali kita membutuhkan kompleksitas waktu yang detil dari suatu algoritma. Biasanya yang kita butuhkan hanyalah hampiran dari kompleksitas waktu yang sebenarnya. Kompleksitas waktu ini dinamakan kompleksitas waktu asimptotik yang dinotasikan dengan “O” (baca : “O-besar”). Kompleksitas waktu asimptotik ini diperoleh dengan mengambil term terbesar dari suatu persamaan kompleksitas waktu. Sebagai contoh, dapat dilihat pada persamaan di bawah ini.
T(n)=4n^3 + 5n^2 + 7n + 3 (1)
O(n^3) (2)
O(n^3) (2)
* ( "^" Pangkat )
Dari persamaan (1) di atas diperoleh persamaan (2). Dapat dilihat bahwa nilai O adalah term terbesar dari T(n), tanpa faktor pengalinya.
Kompleksitas algoritma tersebut memiliki suatu spektrum, yang menunjukkan tingkat kompleksitas suatu algoritma, dengan urutan sebagai berikut. O(1)<O(log n)<O(n)<O(n log n)<O(n2)<…<O(2n)<O(n!)
::. Selamat Belajar, Semoga Bermanfaat .::
Post a Comment