· Faktor-faktor yg mempengaruhinya adalah :
- Banyak langkah
- Tipe data kecepatan
- Operator-operator
- Alokasi memori -> space memori, berkaitan dgn * struktur data dinais
* procedure/function
call
* recursif
· Tipe Data
- integer
- real
Dua nilai yg sama dgn operator yg sama tapi dgn variabel yg berbeda, maka terdapat perbedaan kecepatan/proses penyelesaiannya.
Contoh :
-> 250 + 17 = 267 (lebih cepat dari)
-> 250.0 + 17.0 = 0.25*103 + 0.17*102
-> 250.0 + 17.0 = 0.25*103 + 0.17*102
= 0.25*103 + 0.017*103
= (0.25+ 0.17)*103
= 0.267*103
= 267.0
· Operator
Urutan penggunaan operator/penempatan operator bisa mempengaruhi efisiensi.
Contoh perkalian (*) lebih lama daripada penjumlahan (+)
· Tetapi dalam perkembangan teknologi, perbedaan penggunaan operator maupun tipe data dasar tidak terlalu signifikan.
· Yang perlu diperhatikan adalah banyaknya operasi aritmatika dan logika yang dilakukan.
Operator aritmatika : +,-,*,/,^,div,mod
Operator logika : AND,OR,NOT masing-masing 1.
Operator adalah jika hasil perhitungannya termasuk dalam himpunan itu sendiri.
2 < 5 -> bukan operator tapi konstanta logika karena tidak menghasilkan nilai yang sejenis
Operator : H x H -> H
x = 2<5
x = True Tidak ada operation ( 0 operation)
y = 5
y = 5+0 -> 1 operation
y = 2+3*5 -> 2 operation
y = 3*5+2 -> 2 operation
· Banyak langkah dalam suatu algoritma dinyatakan dengan banyaknya operasi aritmatika dan logika yang dilakukan. Dengan demikian hal ini bergantung pada statement dan jenis algoritma :
- sequensial
- branching
- looping
- subroutine call (bisa memanggil prosedur dan bisa memanggil fungsi)
Banyak langkah (waktu tempuh) + memori
= kompleksitas waktu
- Sequensial
Statement s1 dgn banyak langkah n(s1)
Statement s2 dgn banyak langkah n(s2)
banyak langkah = n(s1)+n(s2)Assigment dgn konstanta mempunyai waktu tempuh 0
x = 0
y = 1 1 operation
n = x+y
Built in subroutine call mempunyai waktu tempuh 1
Sin(x) -> 1 op
Sin(x*pi/1000) -> 3 op
- Branching (percabangan)
If (kondisi) Then statement s1
Else statement s2
contoh
Jika n(kondisi) = waktu tempuh kondisi -> 2 op
n(s1) = waktu tempuh statement s1 -> 5 op
n(s2) = waktu tempuh satement s2 -> 3 op
Maka
waktu tempuh = n(kondisi) + max(n(s1),n(s2))
= 2 + 5
= 7
- Loop
For Loop
For var ß awal to akhir step diff.
Statement S(var)
Statement S(var) tidak tergantung var tergantung var
Jika statement dalam inner loop tidak bergantung pada var,
maka statement tersebut diulang sebanyak
|
Misalnya waktu tempuh untuk statement tersebut adalah Ts, maka waktu tempuh dengan loop tsb adalah t*Ts.
Waktu tempuh untuk control loop adalah t*1.
Jadi waktu tempuh untuk loop tersebut adalah t * Ts + t = t (Ts+1)
Contoh :
1. for i ß 2 to 30 step 5
Ts = 2
x ß x+1
Ts = 2 |
y ß x+y
Berapa waktu tempuhnya ?
T = t (Ts+1)
= 6 (2+1)
= 18
2. n=20
for i ß 2 to 2*n step 5
Ts = 2
x ß x+1
Ts = 2 |
y ß x+y
Berapa waktu tempuhnya ?
Looping à
Tfor = t (Ts+1)
= 8 (2+1)
= 24
Waktu tempuh perkalian 2*n à T2*n = 1
Jadi waktu tempuhnya = T = 24 + 1
= 25
3. for iß1 to 10
x ß x+1 à 1 op
if x>=1 then
|
|
else
y ß x+y à 1 op
Berapa waktu tempuhnya ?
Waktu tempuh dlm percabangan = max(2,1)
Ts = 1 + max(2,1) = 3
T = t (Ts+1) = 10 (3+1) = 40
Jika statement tergantung nilai var
For var ß awal to akhir step diff
S(var)
