Algoritma dan Kompleksitas

3.2 Kompleksitas Waktu

Contoh 2. Tinjau algoritma menghitung rerata pada Contoh 1. Operasi yang mendasar pada algoritma tersebut adalah operasi penjumlahan elemen-elemen ak (yaitu jumlah¬jumlah+ak), Kompleksitas waktu Hitung Rerata adalah T(n) = n. Contoh 3. Algoritma untuk mencari elemen terbesar di dalam sebuah larik (array) yang berukuran n elemen. Kompleksitas waktu algoritma dihitung berdasarkan jumlah operasi perbandingan elemen larik (A[i] > maks). Kompleksitas waktu CariElemenTerbesar : T(n) = n – 1. Kompleksitas waktu dibedakan atas tiga macam : 1. Tmax(n) : kompleksitas waktu untuk kasus terburuk (worst case), atau kebutuhan waktu maksimum. 2. Tmin(n) : kompleksitas waktu untuk kasus terbaik (best case), atau kebutuhan waktu minimum. 3. Tavg(n): kompleksitas waktu untuk kasus rata-rata (average case), atau kebutuhan waktu secara rata-rata