Binary Search Recursive
FUNCTION BinarySearch(input a1,a2,..., an: array of integer, i:integer, j:integer, cari:integer)
KAMUS
i, j, mid : integer
ketemu : boolean
i ← 1
j ← n
ALGORITMA
if (i <= j) then
mid ← (i + j) / 2
if (cari = a[mid]) then
return mid // data ditemukan
else if (cari < a[mid]) then
return BinarySearch(a, i, mid - 1, cari)
else
return BinarySearch(a, mid + 1, j, cari)
endif
endif
return -1 // tidak ditemukan
| ||
Operator Utama
=
| ||
Tmax(n)=log n
|
Tavg(n)=log n
|
Tmin(n)=1
|
Quick Sort
FUNCTION partition (input/output a :
array[1..n] of integer, input x,y :
integer, output p,q : integer)
KAMUS
pivot, temp : integer
ALGORITMA
pivot ← a [(x+y) div 2]
p ← x
q ← y
repeat
while (a[p] < pivot) do
p ← p + 1
endwhile
while (pivot < a[q]) do
q ← q – 1
endwhile
if (p <= q) then
temp ← a[p]
a[p] ← a[q]
a[q] ← temp
p ← p + 1
q ← q – 1
endif
until (p > q)
FUNCTION quicksort (input/output a :
array [1..n] of integer, input x,y :
integer)
KAMUS
k : integer
ALGORITMA
if (x < y) then
partition(a,x,y,k)
quicksort(a,x,k)
quicksort(a,k+1,y)
endif
| ||
Operator Utama
<
| ||
Tmax(n)= n log n
|
Tavg(n)= n log n
|
Tmin(n)=1
|
MaksMin
Procedure MaksMin (Input M :TabelInt, a, b, c : integer output Mn, Mks : integer)
KAMUS
Mn1, Mn2, Mks1, Mks2 : integer
ALGORITMA
if a=b then
Mn←Ma
Mks←Ma
elsed
if (a=b-1) then
if Ma < Mb then
Mks←Mb
Mn←Ma
else
Mks←Ma
Mn←Mb
endif
else
c ←(a+b) div 2
MnMks2(M, a, c, Mn1, Mks1)
MnMks2(M, c+1, Mn2, Mks2)
If Mn1 < Mn2 then
Mn←Mn1
Else
Mn←Mn2
Endif
If Mks1<Mks2 then
Mks←Mks1
Else
Mks←Mks2
Endif
|
T(n)=0 , n=1
=1 , n =2
=2T(n/2) + 2 . n > 2
|
T(n) = 3n / 2 - 2
|
Fibonacci
Procedure fibonacci(Input n : integer)
KAMUS
ALGORITMA
If n <= 1 then
return n
else
return fibonacci(n - 1) + fibonacci(n - 2)
endif
| ||
Operator Utama : +
T(n) = 0 untuk n <= 1
T(n) = T(n-1) + T(n-2) untuk n > 1
Substitute :
T(n-1) = T(n-2) + T(n-3)
T(n-2) = T(n-3) + T(n-4)
T(n) = [ T(n-2) + T(n-3) ] + [ T(n-3)+T(n-4) ]
T(n) = O(2n-1) + O(2n-2) + O(1)
T(n) = O(2n)
|