Apa itu Big Oh? sebuah pertanyaan besar

Big Oh

Big Oh adalah fungsi yang berkaitan dengan kelajuan proses, dan biasanya digunakan dalam analisis suatu algoritma untuk menentukan efisiensi dan kompleksitasnya.

-T(n) = O(f(n))

 Bila ada suatu konstanta C, maka :

-T(n) ≤ C.(f(n))

Contoh Lain :

·        Jika f(n) = 5n² maka T(n) = O(n²)

·        Jika f(n) = 7n² + 3n + 5 maka T(n) = O(n²)

·        Jika f(n) = n³ – 2n + 8 maka T(n) = O(n³)

Klasifikasi Algoritma berdasarkan notasi Big Oh :

1.      T(n) = c

Disebut sebagai algoritma konstan, dimana programnya hanya dieksekusi dengan suatu nilai yang konstan. Bersifat konstan dan tidak dipengaruhi parameter atau banyak ada yang dieksekusi. Merupakan algoritma yang paling ideal.

Contoh Program Pascal :

Begin

A:=7;

End.

Maka T(n) = O(1), karena program hanya dieksekusi satu kali, dan konstan.

2.      T(n) = O(n)

Disebut algoritma linear, dimana waktu eksekusinya sebanding dengan jumlah data, dan merupakan kondisi optimal dalam membuat algoritma.

Contoh Program Pascal :

Begin

For I := 1 to n do

            Begin

            A:=A+1;

            End;

End.

Maka T(n) = O(n) karena program dieksekusi sejumlah n kali.

3.      T(n) = O(n²)

Disebut algoritma kuadratik, karena waktu eksekusi program akan sebanding dengan jumlah kuadrat jumlah data. Biasanya timbul karena adanya nested loop atau loop bersarang pada suatu program.

Contoh Program Pascal :

Begin

For I := 1 to n do

            Begin

            For J:=1 to n do

                        Begin

A:=A+1;

                        End;

            End;

End.

Loop dalam di eksekusi n kali. Loop luar di eksekusi n kali. Oleh karena itu T(n) = O(n²) dan program di eksekusi n x n atau n².

4.      T(n) = O(log n)

Disebut algoritma logaritmik, karena waktu eksekusi sebanding dengan logaritma dari jumlah data. Biasanya algoritma ini digunakan untuk memecahkan masalah besar menjadi masalah yang lebih kecil.

Contoh : algoritma Binary Search dan algoritma fungsi rekursif.

5.      T(n) = O(n log n)

Disebut algoritma linearitmik, karena merupakan gabungan dari linear dan logaritmik, biasanya digunakan untuk memecahkan masalah yang besar menjadi masalah yang lebih kecil dan diselesaikan secara terpisah, lalu kemudian hasilnya digabungkan.

Contoh : algoritma Quick Sort.

6.      T(n) = O(n³)

Merupakan algoritma yang buruk dan sebisa mungkin dihindari, biasanya algoritma ini dihasilkan dari 3 buah nested loop atau 3 buah loop bersarang.

Contoh program Pascal :

Begin

For I := 1 to n do

            Begin

            For J:=1 to n do

                        Begin

For K:= 1 to n do

            Begin

            A:=A+1;

            End;

                        End;

            End;

End.

Loop terdalam di eksekusi n kali. Loop tengah di eksekusi n kali. Loop luar di eksekusi n kali. Oleh karena itu T(n) = O(n³) dan program di eksekusi n x n x n atau n³.

Program Pascal Binary Search

program binary_search;
uses crt;
var input:Array [1..30,1..3] of integer;
    jumlah,i,j,cari,langkah:integer;
    isi:boolean;

procedure mencari;

function cektengah(var z:integer):integer;
var     x:integer;
    ada: boolean;
begin
    x := 1;
    ada := false;
    while not(ada) do
    begin
        if (z = input[x,2]) then
        begin
            cektengah := x;
            ada := true;
        end
        else
            x := x+1;
    end;
end;

function cekkirkan(var z:integer): integer;
var     x:integer;
    ada: boolean;
begin
    x := 1;
    ada := false;
    while not(ada) do
    begin
        if (z = input[x,1]) or (z =input[x,3]) then
        begin
            cekkirkan := x;
            ada := true;
        end
        else
            x := x+1;
    end;
end;

begin
j := cektengah(cari); langkah := 1;
        while (j > 1) do
        begin
            i := input[j,2]; j := cekkirkan(i);
            if (input[j,1] = i) or (input[j,3] = i) then
            begin
                langkah := langkah + 1;
            end;
        end;
writeln('Angka ditemukan dalam ',langkah,' langkah');
end;


procedure masuk;

function cektengah(var z:integer):integer;
var     x:integer;
    ada: boolean;
begin
    x := 1;
    ada := false;
    while not(ada) do
    begin
        if (z = input[x,2]) then
        begin
            cektengah := x;
            ada := true;
        end
        else
            x := x+1;
    end;
end;

begin
j:=1;isi:=false;
while not(isi) do
      begin
           if (input[i,2]>input[j,2])then
           begin
                if (input[j,3]=0)then
                begin
                input[j,3]:=input[i,2];
                isi:=true;
                end
                else j:=cektengah(input[j,3]);
           end
           else
           begin
                if (input[j,1]=0) then
                begin
                input[j,1]:=input[i,2];
                isi:=true;
                end
                else j:=cektengah(input[j,1]);
           end;
      end;
end;

begin
clrscr;
writeln('***************************');
writeln('  Program  Binary  Search  ');
writeln('***************************');
writeln('*****PROGRAM DIMULAI*******');
write('Masukan jumlah input : ');readln(jumlah);
for i:= 1 to jumlah do
    begin
    write('Masukkan elemen ke -',i,' : ');readln(input[i,2]);
    input[i,1]:=0;input[i,3]:=0;
    end;
for i:= 2 to jumlah do
    begin
    masuk;
    end;
writeln('****************************');
write('Masukan angka yang dicari : ');readln(cari);
mencari;
writeln('***********************************');
writeln('Terima kasih atas partisipasi anda!');
writeln('*********PROGRAM SELESAI***********');
readln;
end.

Tugas Pascal Moving Text

Program berikut ini akan membuat tulisan berjalan ke samping lalu ke bawah :

uses crt;
var
a,b:string;
i,j:integer;
x,y:byte;
begin
j:=45;
clrscr;
a:='HELLO WORLD';
for i:=length(a) downto 1 do
    begin
    j:=j-1;x:=1;y:=1;
    b:=copy(a,i,1);
    repeat
        delay(20);
        gotoxy(x,y);write(b);
        gotoxy(x-1,y);write(' ');
        x:=x+1;
        until x>j;
    end;
x:=44;
for i:=length(a) downto 1 do
    begin
    for y:=1 to 20 do
        begin
        gotoxy(x,y);write(A[i]);
        gotoxy(x,y-1);write(' ');
        delay(20);
        end;
    x:=x-1;
    delay(50);
    end;
readln;
end.

Program Pascal STACK

program infix_postfix;
uses crt;
type s100 = string[100];
stacks = record
stack : s100;
top : 0..100
end;
var infix, postfix : s100;
operator : set of char ;
x,y:byte;
i:integer;

procedure push (var s : stacks; elements : char);
begin
s.top := s.top + 1;
s.stack[s.top] := elements
end;

function pop (var s : stacks) : char;
begin
pop := s.stack[s.top];
s.top := s.top - 1;
end;

function priority (tanda : char) : integer;
begin
case tanda of
'^' : priority := 3;
'*', '/' : priority := 2;
'+', '-' : priority := 1;
'(' : priority := 0
end
end;

procedure convert (infix : s100);
var i : integer;
test : boolean;
temp, kar : char;
s : stacks;
begin
postfix:='';
for i := 1 to length(infix) do
    begin
    kar := infix[i];
    if kar = '(' then push(s, kar)
    else if kar = ')' then
        begin
        while s.stack[s.top] <> '(' do
        postfix:=postfix + pop(s);
        temp := pop(s)
        end
    else if kar in operator then
        begin
        while (s.top <> 0) and (priority(kar) <= priority(s.stack[s.top])) do
        postfix:=postfix + pop(s);
        push(s, kar)
        end
    else if kar <> ' ' then postfix:=postfix + kar;
    end;
    if s.top <> 0 then
        repeat
        postfix:=postfix + pop(s)
        until s.top = 0;
end;

procedure animate(postfix:string);
begin
x:=13;
    for i:=1 to length(postfix) do
        begin
        for y:=7 to 14 do
            begin
            gotoxy(x,y);write(postfix[i]);
            gotoxy(x,y-1);write(' ');
            delay(20);
            end;
    x:=x+1;
    delay(50);
    end;
end;

begin
clrscr;
operator:= ['^','*','/','+','-'];
writeln('===================================');
writeln('|  mengubah infix menjadi postfix  |');
writeln('===================================');
gotoxy (5,7);
write('infix = ');
readln(infix);
gotoxy (5,14) ;
write('hasil = ');
convert (infix);
animate(postfix);
gotoxy(13,7); write(infix);
gotoxy (5,16);
writeln('terimakasih atas partisipasi anda');
readln;
end.