Algoritma dan Kompleksitas

3.1 Model Perhitungan Kebutuhan Waktu/Ruang

(i) Operasi pengisian nilai (jumlah¬0, k¬1, jumlah¬jumlah+ak, k¬k+1, dan r ¬ jumlah/n) Jumlah seluruh operasi pengisian nilai adalah t1 = 1 + 1 + n + n + 1 = 3 + 2n (ii) Operasi penjumlahan (jumlah+ak, dan k+1) Jumlah seluruh operasi penjumlahan adalah t2 = n + n = 2n (iii) Operasi pembagian (jumlah/n) Jumlah seluruh operasi pembagian adalah t3 = 1 Total kebutuhan waktu algoritma Hitung Rerata: t = t1 + t2 + t3 = (3 + 2n)a + 2nb + c detik Model perhitungan kebutuhan waktu seperti di atas kurang dapat diterima: Dalam praktek kita tidak mempunyai informasi berapa waktu sesungguhnya untuk melaksanakan suatu operasi tertentu Komputer dengan arsitektur yang berbeda akan berbeda pula lama waktu untuk setiap jenis operasinya. Selain bergantung pada komputer, kebutuhan waktu sebuah program juga ditentukan oleh compiler bahasa yang digunakan. Model abstrak pengukuran waktu/ruang harus independen dari pertimbangan mesin dan compiler apapun. Besaran yang dipakai untuk menerangkan model abstrak pengukuran waktu/ruang ini adalah kompleksitas algoritma. Ada dua macam kompleksitas algoritma, yaitu kompleksitas waktu dan kompleksitas ruang. Kompleksitas waktu, T(n), diukur dari jumlah tahapan komputasi yang dibutuhkan untuk menjalankan algoritma sebagai fungsi dari ukuran masukan n. Kompleksitas ruang, S(n), diukur dari memori yang digunakan oleh struktur data yang terdapat di dalam algoritma sebagai fungsi dari ukuran masukan n. Dengan menggunakan besaran kompleksitas waktu/ruang algoritma, kita dapat menentukan laju peningkatan waktu (ruang) yang diperlukan algoritma dengan meningkatnya ukuran masukan n.