Analisis Algoritma : UKURAN EFISIENSI ALGORITMA

Soal

1.Mengapa kita memerlukan algoritma yang efisien.

2.Bagaimana langkah untuk menentukan ukuran efisiensi waktu:

• a)    Bagaiamana menentukan problem size (n).
• b)      Bagaiamana menentukan operasi dominan
• c)      Bagaiamana menentukan fungsi langkah
• d)     Bagaiamana menentukan kompleksitas waktu O(f(n))

3.Apa Efisiensi Memory.space dan berikan contohnya.

4.Apa yang dimaksud dengan kemudahan impelemntasi suatu algoritma.

5.Bagaimana menentukan Stabilitas suatu algoritma.

Jawab :

11. Karena kita mermelukan efesien waktu dan memori,meskipun algoritma memberikan keluaran yang benar (yang mendekatai) , tetapi jika harus menunggu berjam jam untuk mendapatkan keluarannya , algoritma tersebut biasanya tidak akan dipakai, karena setiap orang menginginkan keluaran yang cepat, Begitu juga dengan memori.

Dan waktu tempuh suatu program sangat bergantung pada :

·         Banyak data ke problem size.

·         Spesifikasi computer ke Hardware (RAM,PROSESOR,dll).

·         Compiler ke software.

·         Tegangan listrik.

·         Dll ke programer

22. efisiensi waktu algoritma diukur dalam satuan n (problem size). terdapat 4 langkah untuk menentukan ukuran efisiensi waktu, antara lain:

• Menentukan problem size (n)
• Menentukan operasi dominan
• Menentukan Fungsi langkah → g(n)
• Menentukan kompleksitas waktu O(f(n)) (Big Oh function)

a. menentukan problem size (n).  
 

        b. menentukan operasi dominan.

operasi dominan merupakan operasi yang paling banyak dilakukan, sesuai konteks permasalahan. misalkan pada algoritma menentukan nilai max/ min, operasi dominannya adalah operasi perbandingan ">" atau "<". pada algoritma searching operasi dominannya adalah operasi "=".

b.  C. Menentukan Fungsi langkah → g(n)

-          g (n) = banyak kali operasi dominan dilakukan (dalam n )

 

Pada contoh algoritma ini di perboleh keadaan  best case, yakni ketika data terurut ascending ; dan sebaliknya akan di perbolehkan keadaan worst case , yakni ketika data terurut descending atau data terbesar berada di X(1)

ad. Menentukan kompleksitas waktu O(f(n)) (Big Oh function)

Suatu algoritma dengan fungsi langkah g(n) di katakana mempunyai konpleksitas waktu O(f(n)) jika terdapat konstanta c > 0 sedemikian hingga : g(n) ≤ c.f(n) untuk n > n₀

Ø  Algoritma MaxMin,CountingSort            - g(n) = 2n – 2             - O(n) linier

Ø  Algoritma Bubblesort                               - g(n) = n²/2 – n/ 2       - O(n²) kwadratik

Ø  Algoritma perkalian 2 Matrix _{n x n}                  - g(n) = n³ + kn            - O(n³) kubik

Ø  Algoritma MergeSort ,QuickSort                         - g(n) = (n log n)          - O(nlogn) logaritmik

23. Efesiensi Memory/space adalah menentukan besar memory yang di perlukan oleh suatu algoritma.

Kebutuhan memory (space ) suatu algoritma jiga tidak bias di ukur dalam satuan memory (byte,KB) ,karena kebutuhan memory yang sebenarnya bergantung dari banyak data dan struktur datanya . kebutuhan memory dari suatu algoritma di ukur dalam satuan problem size n.

Contoh : penulihsan sebuah algoritma di dalam sebuah program.

  4. kemudahan impelemntasi suatu algoritma adalah mengukur seberapa mudah / sederhana algoritma tersebut di buat programnya , hal ini biasa di lihat dari teknik perancangannya atau struktur data yang di gunakan .

  5. stabilitas suatu algoritma dapat di lihat dari kesetabilan index data untuk data yang sama

contoh :

 

contoh fungsi pembangkit untuk permutasi

pascal program singel Linked List

program singellinkedlist;
uses crt;
type
 pointer=^typedata;
 typedata=record
  nama :string;
  berikutnya: pointer;
  end;
var list, akhir :pointer;

procedure masuk_depan(var L :pointer; X:string);
var baru: pointer;
begin
new (baru);
baru^.nama :=X;
baru^.berikutnya :=nil;
 if L = nil then
  begin
  L:= baru ;
  akhir:=baru;
  end
  else
 begin
 baru^.berikutnya :=L;
 L :=baru;
 end;
 end;

procedure sisip_tengah (var L :pointer; X, Y:string);
var baru,bantu :pointer;
begin
bantu :=L;
while bantu^.berikutnya <> nil do
 begin
 if bantu^.nama = y then
 begin
 new (baru);
 baru^.nama:=x;
 baru^.berikutnya := bantu^.berikutnya;
 bantu^.berikutnya := baru;
 end;
 bantu :=bantu^.berikutnya;
 end;
 end;

 procedure masuk_belakang (var L : pointer; X : string);
 var
 baru,bantu : pointer;
 begin
 new (baru);
 baru^.nama := X;
 baru^.berikutnya :=nil;
 bantu :=L;
 while bantu^.berikutnya <> nil do
    bantu := bantu^.berikutnya;
 bantu^.berikutnya :=baru;
 {akhir^.next:=baru;
 akhir:=baru;akhir^.next:=nil;}
 end;

 procedure hapus_depan(var L:pointer);
 var
 bantu : pointer;
 begin
 bantu :=L;
 if L = nil then writeln ('list kosong...')
 else
 begin
 L:= L^.berikutnya;
 dispose(bantu);
 end;
 end;

 procedure hapus_tengah (var L: pointer; X:string);
 var
 bantu,hapus :pointer;
 begin
 bantu :=L;
 if L = nil then writeln ('list kosong..')
 else
 begin
 bantu :=L;
 new(hapus);
 while bantu^.berikutnya <> nil do
 begin
 if bantu^.berikutnya^.nama =  X then
 begin
  hapus :=bantu^.berikutnya;
  bantu^.berikutnya :=hapus^.berikutnya;
  dispose (hapus);
  end
  else
  bantu:=bantu^.berikutnya;
  end;
  end;
  end;

  procedure hapus_belakang (var L: pointer);
  var
  baru,bantu : pointer;
  begin
  bantu:= L;
  if bantu = nil then writeln ('list kosong...')
  else
  begin
  while bantu^.berikutnya^.berikutnya <> nil do
   bantu :=bantu^.berikutnya;
   new(baru);
   baru := bantu^.berikutnya;
   bantu^.berikutnya :=nil;
   dispose (baru)
   end;
   end;

   procedure cetak (L : pointer);
   var
   bantu: pointer;
   begin
   bantu :=L;
   while bantu <> nil do
   begin
    write (bantu^.nama, ' ');
    bantu:= bantu^.berikutnya;
    end;
    end;

  var
  namabaru,namasisip, namahapus :string;
  pil,n : integer;
  lagi: boolean;
  begin
  lagi:=true;
  new (list) ; list:= nil;
  while lagi do
  begin
  clrscr;
  writeln('1.Tambahkan Nama Depan');
  writeln('2.Tambahkan Nama Belakang');
  writeln('3.Sisipkan nama dimana pun yang anda mau');
  writeln('4.Cetak Data List');
  writeln('5.Hapus Nama Nepan');
  writeln('6.Hapus Nama Tengah');
  writeln('7.Hapus Nama Belakang');
  writeln('8.Exit Kalau Selesai');
  writeln('pilih ++> (1-8) '); readln (pil);
  case pil of
  1:begin
    writeln('masuk nama depan');
    writeln('masukan nama baru : ');readln (namabaru);
    masuk_depan (list, namabaru);
    end;
  2:begin
     writeln('masuk nama belakang');
    writeln('masukan nama baru : ');readln (namabaru);
    masuk_belakang (list, namabaru);
    end;
  3:begin
    writeln('sisipkan nama');
    write('masukan nama baru yang akan disisip : ');
    readln (namabaru);
    write('disisip setelah nama  :  ') ;readln (namasisip);
    sisip_tengah (list,namabaru,namasisip);
    end;
  4:cetak(list);
  5:begin
    writeln('hapus nama depan');
    hapus_depan (list);
    cetak (list);
    writeln;
    end;
  6:begin
    writeln('hapus nama tengah');
    write('masukan nama yang akan dihapus :  ');
    readln (namahapus);
    hapus_tengah (list,namahapus);
    cetak(list);
    end;
  7: begin
    writeln('hapus nama belakang');
    hapus_belakang (list);
    cetak (list);
    writeln;
    end;
  8: begin
  writeln ('terimakasih');
  lagi :=false
  end;
  end;
  readln;
  end;
  end.

contoh pascal

program datapasienRSKARIADI;

uses crt;

type
  datab = ^data;
  data= record
  nama,png,jk,nk:String;
end;

var
  x,i,a,b,y:integer;
  pasien:array[1..100] of data;


        procedure garis();
            begin
                writeln('________________________________________________________________________________');
            end;


        procedure input();
            begin
               for i:=1 to x do
                 begin
                   with pasien[i] do
                    begin
                      write(i,'.NAMA PASIEN         = ');readln(nama);
                      write(  '  JENIS PENYAKIT      = ');readln(png);
                      write(  '  JENIS KELAMIN       = ');readln(jk);
                      write(  '  NOMOR KAMAR         = ');readln(nk);
                      writeln;
                    end;
                 end;
            end;


        procedure output();
            begin
               garis;
               write('No':3); write('NAMA PASIEN':10); write('JENIS PENYAKIT':20); write('PEMBAYARAN':22); writeln('LAMA DIRUMAH SAKIT':25);
               garis;
                 for a:=1 to x do
                   begin
                     with pasien[a] do
                       begin
                         writeln(a:2,' ':2,nama,' ':3,png:18,jk:21,nk:25);
                       end;
                   end;
               garis;
            end;


        procedure hapus(y:integer);
          var z:integer;
            begin
               if (y > x) or (y < 1)then
                 begin
                   writeln;
                   writeln('pasien dengan no ',y,' tidak tersedia');
                   write('Masukkan nomor pasien yang akan dihapus = ');readln(z);
                   writeln;
                   hapus(z);
                 end

                else
                 begin
                    for b:=y to x do
                       begin
                          if x=1 then
                             begin
                               x:=1;
                             end
                          else
                             pasien[y]:=pasien[y+1];
                       end;

                    x:=x-1;
                    writeln('Data pasien berhasil diHapus');
                    writeln;
                    writeln('Data pasien setelah dihapus');
                    output();
                 end;
            end;



        begin
          clrscr;
            write('Masukkan Jumlah pasien = ');readln(x);
              input();
              output();
            write('Masukkan nomor pasien yang akan dihapus = ');readln(y);
              hapus(y);
          readln;
        end.

SEGITIGA PASCAL REKURSIF

program SEGITIGA_PASCAL_REKURSI;
 uses crt;
  var c,i,j,n,batas:integer;

procedure segitigapascal;
    var num:array[1..100] of longint;
        begin
         if c < 1 then
          begin
           num[1]:=1;
           writeln(1);
            for i:=1 to n do
         begin
        batas:=(i+1) div 2;
        if not odd(i)then
                 num[batas+1]:=num[batas]*2;
        for j:=batas downto 2 do
        num[j]:=num[j]+num[j-1];
                for j:=1 to batas do
        write(num[j],' ');
        if not odd(i)then write (num[batas+1],' ');
        for j:=batas downto 1 do
        write(num[j],' ');
        writeln;
             end;
            c := c+1;
           segitigapascal;
          end;
        end;

begin
clrscr;
writeln('SEGITIGA PASCAL');
writeln('===============');
writeln;
write(' Inputkan panjang n segitiga pascal :'); readln(n);
segitigapascal;
readln;
end.

SEGITIGA PASCAL

program SEGITIGA_PASCAL_BIASA;
 uses crt;
  var c,i,j,n,batas:integer;

procedure segitigapascal;
    var num:array[1..100] of longint;
          begin
           num[1]:=1;
           writeln(1);
            for i:=1 to n do
         begin
        batas:=(i+1) div 2;
        if not odd(i)then
                 num[batas+1]:=num[batas]*2;
        for j:=batas downto 2 do
        num[j]:=num[j]+num[j-1];
                for j:=1 to batas do
        write(num[j],' ');
        if not odd(i)then write (num[batas+1],' ');
        for j:=batas downto 1 do
        write(num[j],' ');
        writeln;
             end;
          end;

begin
clrscr;
writeln('SEGITIGA PASCAL');
writeln('===============');
writeln;
write(' Inputkan panjang n segitiga pascal :'); readln(n);
segitigapascal;
readln;
end.

pascal MENARAHANOI REKURSIF

program MENARA_HANOI;
uses crt;
var
  L,J : integer;
  A, B , C : char;

procedure MenaraHanoi(J:integer; A,B,C:char; Var L:integer);
begin
  if J = 1 then
  begin
    L := L + 1;
    write('Langkah : ',L,' ');
    writeln('Pindahkan piringan 1 dari menara ',A,' ke menara ',C);
  end
  else
  begin
  MenaraHanoi(J-1,A,B,C,L);
  L:= L + 1;
  write('Langkah : ',L,' ');
  writeln('Pindahlkan piringan ',J,' dari menara ',A,' ke menara ',C);
  MenaraHanoi(J-1,B,C,A,L)
  end;
end;

begin
clrscr;
write('Masukkan Jumlah Piringan = ');readln(J);
L := 0;
A := 'A';
B := 'B';
C := 'C';
MenaraHanoi(J,A,B,C,L);
readln;
end.