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) 

Mariana E.K Zagoto
Fakultas Teknologi & Informasi Komputer
Universitas Prima Indonesia

Pengertian dan Rumus Barisan Geometri

Barisan Geometri dapat didefinisikan sebagai barisan yang tiap-tiap sukunya didapatkan dari hasil perkalian suku sebelumnya dengan sebuah konstanta tertentu.

Contoh Barisan Geometri

untuk lebih memahami apa yang dimaksud dengan barisan geometri perhatikan contoh berikut:

3, 9, 27 , 81, 243, ...

barisan di atas adalah contoh barisan geometri dimana setiap suku pada barisan tersebut merupakan hasil dari perkalian suku sebelumnya dengan konstanta 3. maka bisa disimpulkan bahwa rasio pada barisan di atas adalah 3. rasio pada suatu barisan dapat dirumuskan menjadi:

r = a_k+1/a_k

dimana a_k adalah sembarang suku dari barisan geometri yang ada. sementara a_k+1 adalah suku selanjutnya setelah a_k.

untuk menentukan suku ke-n dari sebuah barisan geometri, kita dapat menggunakan rumus:

U_n = ar^n-1

dimana a merupakan suku awal dan r adalah nilai rasio dari sebuah barisan geometri.

Mari kita pelajari penggunaan rumus-rumus barisan geometri di atas dalam menyelesaikan soal:

Contoh Soal 1:

Sebuah Bakteri mampu melakukan pembelahan diri menjadi 4 setiap 12 menit. berapakah jumlah bakteri yang ada setelah 1 jam apabila sebelumnya terdapat 3 buah bakteri?

Penyelesaian:

a = 3

r = 4

n = 1 jam/12 menit = 60/12 = 5

Masukkan ke dalam rumus:

U_n = ar^n-1

U₅ = 3 x 4^5-1

U₅ = 3 x 256 = 768 bakteri

Apabila suku ke-n dari suatu barisan geometri digambarkan dengan rumus: a_n = a₁r^n-1, maka deret geometrinya dapat dijabarkan menjadi:

S_n = a₁ + a₁r + a₁r² + a₁r³ + ... + a₁r^n-1

Apabila kita mengalikan deret geometri di atas dengan -r, lalu kita jumlahkan hasilnya dengan deret aslinya, maka kita akan memperoleh:

Pengertian Algoritma Euclid

 Algoritma euclid merupakan suatu algoritma yang digunakan untuk mencari Greatest Common Divisor (GCD) atau biasa dikenal dengan Faktor Persekutuan Terbesar (FPB) dari dua bilangan, khususnya untuk bilangan-bilangan yang sangat besar sehingga tidak perlu mencari faktorisasi prima dari kedua bilangan tersebut. Algoritma euclid ini biasanya diperkenalkan kepada mahasiswa yang sedang mempelajari mata kuliah teori bilangan tetapi tidak jarang juga soal-soal olimpiade matematika dan ujian universitas membutuhkan cara ini untuk menyelesaikan soal yang diberikan. Oleh karena itu Istana Matematika ingin menjelaskan tentang pengertian dari algoritma yang menarik ini - Algoritma Euclid.

Pengertian Algoritma Euclid - Teori Bilangan
Teorema Algoritma Euclid
Misalkan a
dan b adalah dua bilangan bulat dengan syarat b>0. Jika a dibagi dengan b maka terdapat dua buah bilangan bulat lainnya, yaitu h (hasil bagi) dan s (sisa), sedemikian sehingga:

a=h×b+s

dengan 0⩽s<b. Contoh: Jika 16 dibagi dengan 7 akan memberikan hasil bagi 2 dan sisa 2, sedemikian sehingga:

16=2(7)+2

Teorema Algoritma Euclid atau Teorema Algoritma Euclidean ini yang digunakan untuk membentuk rumus umum dari Polinomial 

Contoh :
Tentukan FPB dari 437 dan 621 !
621 = 437 . 1 + 184
437 = 184 . 2 + 69
184 = 69 . 2 + 46
69   = 46 . 1 + 23
46   = 23 . 2               —–> tidak bersisa
FPB(437 , 621) = 23
Jadi, FPB dari 437 dan 621 adalah 23.
Contoh 5:
Berapakah FPB dari 3087 dan 6958 ?
6958 = 3087 . 2 + 784
3087 = 784 . 3 + 735
784   = 735 . 1 + 49
735   = 49 . 15                 —–> tidak bersisa
FPB(3087 , 6958) = 49
Jadi, FPB dari 3087 dan 6958 adalah 49.

EKSPONENSIAL

Fungsi eksponensial

 adalah salah satu fungsi yang paling penting dalam matematika. Biasanya, fungsi ini ditulis dengan notasi exp(x) atau e^x, dimana e adalah basis logaritma natural yang kira-kira sama dengan 2.71828183.

Fungsi eksponensial (merah) terlihat hampir mendatar horizontal (naik secara sangat perlahan) untuk nilai x yang negatif, dan naik secara cepat untuk nilai x yang positif.

Sebagai fungsi variabel bilangan real x, grafik e^x selalu positif (berada di atas sumbu x) dan nilainya bertambah (dilihat dari kiri ke kanan). Grafiknya tidak menyentuh sumbu x, namun mendekati sumbu tersebut secara asimptotik. Invers dari fungsi ini, logaritma natural, atau ln(x), didefinisikan untuk nilai x yang positif.

Secara umum, variabel x dapat berupa bilangan real atau bilangan kompleks, ataupun objek matematika yang lain

Contoh:

clear;clc;

  disp('Kurva Eksponensial Pangkat Positif dengan Konstanta a Positif, Negatif, dan Desimal')

x=-10:1:10;

c=5;

y1=exp(x);

y2=-exp(x);

y3=0.9*exp(x);

y4=-0.9*exp(x);

subplot(221)

plot (x,y1,'m*-'); grid;

title ('Eksponensial y1=exp(x)')

xlabel ('X')

ylabel ('Y')

subplot(222)

plot (x,y2,'m*-'); grid;

title ('Eksponensial y2=-exp(x)')

xlabel ('X')

ylabel ('Y')

subplot(223)

plot (x,y1,'m*-'); grid;

title ('Eksponensial y3=0.9*exp(x)')

xlabel ('X')

ylabel ('Y')

subplot(224)

plot (x,y2,'m*-'); grid;

title ('Eksponensial y4=-0.9*exp(x)')

xlabel ('X')

ylabel ('Y')

OOP adalah seuah konsep pemrograman yang memandang program bukan lagi cara tetapi merupakan objek yang saling berinteraksi satu sama lain

Pemrograman berorientasi objek (Inggris: object-oriented programming disingkat OOP) merupakan paradigma pemrograman yang berorientasikan kepada objek. Semua data dan fungsi di dalam paradigma ini dibungkus dalam kelas-kelas atau objek-objek. Bandingkan dengan logika pemrograman terstruktur. Setiap objek dapat menerima pesan, memproses data, dan mengirim pesan ke objek lainnya, Sedangkan untuk Structural Programming adalah kebalikan dari object oriented programming yaitu sebuah cara pemrosesan data yang terstruktur dalam analisa, cara dan penulisan pemrograman. Dikarenakan harus terstruktur sehingga dalam pembuatannya antara satu line pemrograman dengan yang lainnya berhubungan. Konsep utama dari Pemrograman Berbasis Objek terletak pada kondisi kode/line pemrogramanannya dimana merupakan sebuah kesatuan modular.

Untuk program yang simpel/sederhana biasanya menggunakan pemrograman terstruktur karena masih mudah dan tidak banyak dilakukan perubahan yang berarti, sedangkan untuk line lebih dari 100 atau bisa dikatakan rumit, maka digunakan pemrograman berorientasi objek.

Pemrograman Terstruktur terdiri dari pemecahan masalah yang besar menjadi masalah yang lebih kecil dan seterusnya, sedangkan untuk pemrograman berorientasi objek terdiri dari pengkelompokan kode dengan data yang mana setiap objek berfungsi secara independen sehingga untuk setiap perubahan kode tidak tergantung pada kode yang lainnya, atau lebih dikenal dengan modular.

Untuk programming terstruktur bersifat task-centric dan berorientasi objek bersifat data-centric. Terdapat juga perbedaan secara spesifik antara objek oriented dengan non-oop, yaitu pada kelas dan objek. Pada Pemrograman  Terstruktur tidak terdapat kelas dan objek.

Sifat-sifat dari pemrograman terstruktur dapat diuraikan sebagai berikut :

a. Memuat teknik pemecahan masalah yang logis dan sistematis

b. Memuat algoritma yang efisien, efektif dan sederhana

c. Program disusun dengan logika yang mudah dipahami

d. Tidak menggunakan perintah GOTO

e. Biaya pengujian program relatif rendah

f. Memiliki dokumentasi yang baik

g. Biaya perawatan dan dokumentasi yang dbuthkan relatif rendah

Berbeda dengan OOP. Suatu program disebut dengan pemrograman berbasis obyek (OOP) karena terdapat :

– Encapsulation (pembungkusan) Encapsulation adalah mekanisme pemrograman yang membungkus kode dan data yang dimanipulasi dan menjaganya supaya terhindar dari interferensi dan penggunaan yang tidak perlu. Salah satu caranya dengan membentuk objek.

– Inheritance (pewarisan) Inheritance memungkinkan programer meletakkan member yang sama dalam satu class dan class-class lain dapat mewarisi member tersebut. Class yang mengandung member yang sama dari beberapa class lain dinamakan superclass atau parent class. Class yang mewarisi dinamakan subclass atau child class. Inheritance menghasilkan class hierarchy.

– Polymorphism (polimorfisme –perbedaan bentuk) Polymorphisme artinya mempunyai banyak bentuk. Dua objek atau lebih dikatakan sebagai polymorphic, bila objek-objek itu mempunyai antar muka yang identik namun mempunyai perilaku-perilaku yang berbeda

Bisa dikatakan pada pemrograman berorientasi objek, dapat dilakukan sebuah programming terhadap code yang lebih baik daripada pemrograman terstruktur, itu juga untuk kaliber atau skala rumit atau besar, sedangkan untuk coding yang skala kecil lebih mudah menggunakan pemrograman terstruktur dikarenakan lebih singkat dan mudah tanpa banyak perubahan yang penting.

Perbedaan antara Object-oriented Programming dan Structural Programming

Object – oriented programming (OOP)

Structural Programming

Biasa digunakan untuk program untuk line lebih dari 100 / rumit

Biasa digunakan untuk program yang simpel/sederhana.

Bersifat modular (pengkelompokan kode dengan data yang mana setiap objek berfungsi secara independen sehingga untuk setiap perubahan kode tidak tergantung pada kode yang lainnya, atau lebih).

Pemecahan masalah dari besar menjadi maslah yang lebih kecil.

Data-centric

Task-centric

Terdapat kelas dan objek

tidak terdapat kelas dan objek

Kesimpulan Perbedaan antara prosedural dan OOP

• Prosedural : Fokus pada bagaimana cara komputer menangani masalah

• OOP : Fokus pada masalah yang ditangani dengan menggunakan komputer.

Dengan OOP, kita dapat mengimplementasikan objekt data yang tidak hanya memiliki ciri khas (attribut), melainkan juga memiliki metode untuk memanipulasi attribut tersebut. Singkatnya, OOP memiliki keunggulan dari konsep pemrograman terstruktur, selain itu juga memiliki kemampuan untuk mengimplementasikan objek dalam kehidupan nyata

  

KARAKTERISTIK PEMROGRAMAN BERORIENTASI OBJEK (OOP)

Pemrograman berorientasi Objek  mempunyai karakterisitik sebagai berikut:

a. Abstraksi (abstraction)

b. Pembungkusan (encapsulation)

c. Pewarisan (inheritence)

d. Polimorfisme – banyakrupa (polymorphism)

A.                Abstraksi (abstraction).

Kemampuan sebuah program untuk melewati aspek informasi yang diproses olehnya, yaitu kemampuan untuk memfokus pada inti. Setiap objek dalam sistem melayani sebagai model dari "pelaku" abstrak yang dapat melakukan kerja, laporan dan perubahan keadaannya, dan berkomunikasi dengan objek lainnya dalam sistem, tanpa mengungkapkan bagaimana kelebihan ini diterapkan

Abstraksi adalah pengabstrakan atau penyembunyian kerumitan suatu proses.

Abstraksi menjelaskan definisi dari objek pada class dalam suatu fungsi (method) atau

fungsi khusus (constructor). Sebuah kelas dapat  dideklarasikan sebagai kelas abstrak.

Tujuan membuat kelas abstrak adalah agar satu kelas lain dapat memperluasnya (extend)

dengan jalan menjadi subclass darinya.

B. Pembungkusan (encapsulation).

Memastikan pengguna sebuah objek tidak dapat mengganti keadaan dalam dari sebuah objek dengan cara yang tidak layak; hanya metode dalam objek tersebut yang diberi ijin untuk mengakses keadaannya

Selain dengan menggunakan metoda abstraksi dalam menyembunyikan method

pada super class, maka juga dapat dilakukan dengan proses pembungkusan suatu fungsi.

Dengan kata lain, sebenarnya proses pembungkusan  itu sendiri merupakan salah satu

metoda atau mekanisme untuk melakukan abstraksi.

Dalam pemrograman tradisional, proses semacam ini sering juga disebut dengan

penyembunyian informasi (information hiding).

Dalam melakukan pembungkusan kode dan data dalam java terdapat tiga tingkatan

akses data yang perlu diketahui  yaitu:

Engkapsulasi berhubungan class control yang diberlakukan terhadap class member yang

ada di dalamnya

1. Tingkat akses Private.

2. Tingkat akses Protected.

3. Tingkat akses Public.