KOMPLESITAS ALGORITMA

KOMPLESITAS ALGORITMA

Hitung kompleksitwaktu algoritma berikut berdasarkan jumlah operasi kali. 

Procedure MinMaks1 (input A : TabelInt, n : integer, output min, maks : integer)
( Mencari nilai minimum dan maksimum di dalam tabel A yang berukuran n elemen, secara brute force.
Masukan : tabel A yang sudah terdefinisi elemen-elemennya
Keluaran: nilai maksimum dan nilai minimum tabel)

Deklarasi:
i : integer

Algoritma:
min ← Ai  ( inisialisasi nilai minimum )
maks ← Ai  (inisialisasi nilai maksimum )
for i ←2 to n do

  if Ai  < min then
   min ← Ai
  endif

  if Ai  > maks then
   maks ← Ai
  endif

endfor 

Hitung Kompleksitas Waktu Asimptotik. T(n) dari algorithma tersebut diatas

Jawaban:

-Kondisi yang diketahui bahwa n > 2

Contoh 

Jika n = 100 maka akan dilakukan sistem bruteforce untuk mencari bilangan terkecil dan tebesar antara 2 sampai 100.

maka codingnya:

Menggunakan pascal:

program MinMax;
uses crt;

var A : array[2..100] of integer;
var n  : integer;
var min, maks : integer;
var i : integer;

begin
<clrscr>;

maks :- A[1];

write<'masukkan jumlah :'>;readIn<n>;
for i :-2 to n do
begin
A[i]:=random<10>;
write<A[i],' '>;
<readln<x[i]>;>
end;

begin
if A[i] < min then
min:=A[i];
end;

begin
min :- a[2];
if A[i] > maks then
maks:-A[i];
end;

writeln;
writeln<'max =',maks>;
writeln<'min =',min>;

end.

Hasil :

Masukkan Jumlah : 4 (misal)
9 10 12 15
max = 15
min = 9

maka bilangan Ai Maks adalah 15 dan Ai Min adalah 9

 Kompleksitas Waktu Asimptotik 

T(n) = (n – 1) + (n – 1) = 2n – 2  = O(n)