3. Kompleksitas Algoritma (Ruang dan Waktu)

Summary:silahkansaja

Kita memerlukan suatu cara untuk mengukur apakah sebuah algoritma lebih baik jika dibandingkan dengan algoritma yang lain untuk menyelesaikan permasalahan yang sama. Oleh karena itu kita bahas teori kompleksitas dari sebuah algoritma.


Kompleksitas dapat kita bagi menjadi dua: kompleksitas waktu dan kompleksitas ruang. Kompleksitas waktu adalah waktu yang dibutuhkan oleh komputer untuk menjalankan sebuah algoritma sampai selesai. Kompleksitas ruang adalah memori yang dibutuhkan oleh komputer untuk menjalankan sebuah algoritma sampai selesai.


Kompleksitas Ruang


Perhatikan contoh dibawah ini:


Algorithm hitung(x,y,z)
{
return x+y*z+(x+y-z)/(y+z) +13
}


Algorithm jumlah(a,n)
//a adalah array dengan ukuran n
{
s:=0.0;
for i=1 to n do
s:=s+a[i];
return s;
}
Memori yang dibutuhkan untuk menjalankan algoritma diatas bergantung pada jumlah dari:
1. Bagian yang konstan dan tidak tergantung pada input dan output. Bagian ini biasanya terdiri dari memori yang dibutuhkan untuk sourcecode, variable aggregate, konstanta, dll.
2. Bagian variabel yang kebutuhan memorinya bergantung pada instans permasalahan yang hendak diselesaikan. Kita sebut bagian ini sebagai karakteristik instans.


Dengan demikian kompleksitas ruang dapat dirangkum dalam persamaan:
S(P) = c + Sp, dimana c adalah konstanta dan Sp adalah karakteristik instans.


Dalam analisa kompleksitas ruang, kita hanya akan memperhitungkan Sp dan tidak terlalu terfokus pada konstanta c. Pada algoritma hitung diatas, karakteristik instans ditentukan oleh x,y dan z. Dengan asumsi masing masing x,y,z dan return value bisa disimpan dalam 1 word (16 bits), maka dapat kita lihat bahwa memori yang dibutuhkan oleh algoritma hitung tidak tergantung pada karakteristik instans x,y dan z, dengan demikian Sp = 0.


Pada algoritma jumlah, karakteristik instans ditentukan oleh n (jumlah elemen yang akan dipanggil). Karena variabel a harus mampu menampung float sejumlah n elemen, maka memori yang dibutuhkan adalah n word. Variable s, i dan n masing-masing membutuhkan 1 word. Dengan demikian kita dapatkan pertidaksamaan Sp[jumlah](n) >= (n+3).




Kompleksitas Waktu


Total waktu yang dibutuhkan oleh sebuah program adalah jumlah dari kebutuhan waktu kompilasi dan kebutuhan waktu eksekusi. Kita akan memfokuskan diri pada waktu eksekusi karena program biasanya hanya dikompilasi sekali dan dijalankan berulang-ulang. Karena waktu yang dibutuhkan untuk mengeksekusi sebuah program bergantung pada banyak faktor dan sulit untuk dijalankan, maka yang dapat kita lakukan adalah melakukan pendekatan yang salah satunya adalah dengan menghitung jumlah langkah. Langkah disini kita definisikan sebagai bagian dari program yang memiliki waktu eksekusi yang tidak tergantung pada karakteristik instans.


Untuk menghitung jumlah langkah, kita akan menggunakan variable hitung yang dimulai dengan nilai 0 dan terus bertambah dengan bertambahnya jumlah langkah. Untuk lebih jelasnya kita akan menggunakan variable hitung pada algoritma jumlah diatas sehingga akan terlihat sebagai berikut:


Algorithm jumlah(a,n)
{
s:=0.0;
hitung:=hitung+1; //kita tambah 1 pada nilai hitung untuk assignment s

for i=1 to n do
{
hitung:=hitung+1; //untuk "for i"
s:=s+a[i];
hitung:=hitung+1; //untuk assignment s
}
hitung:=hitung+1; //untuk akhir dari "for i"
hitung:=hitung+1; //untuk return
return s;
}


Jika kita hanya memperhitungkan hitung, maka algoritma diatas dapat kita sederhanakan menjadi:
Algorithm jumlah(a,n)
{
for i=1 to n do
hitung:=hitung+2;
hitung:=hitung+3;
}


Dengan demikian jumlah langkah untuk algoritma hitung diatas adalah 2n+3.


Kompleksitas Algoritma (Ruang dan Waktu) Originally published in Shvoong: http://id.shvoong.com/internet-and-technologies/software/2063318-kompleksitas-algoritma-ruang-dan-waktu/

2. Cara Menulis Algoritma

Summary:silahkansaja
Ada berbagai cara menuliskan algoritma yang antara lain dengan menggunakan bahasa sehari-hari, menggunakan flowchart, menggunakan pseudocode dan lain-lain. Yang akan saya jelaskan adalah cara menuliskan algoritma dengan menggunakan pseudocode yang menyerupai bahasa C. Aturan-aturan yang diterapkan untuk menulis adalah:

1. Komentar diawali dengan // untuk tiap baris
2. Blok ditulis dalam kurung kurawal {}
3. Setiap pernyataan diakhiri dengan titik koma ;
4. Identifikasi (nama variabel, fungsi, dll) dimulai dengan huruf.
5. Tipe data dari variabel tidak di deklarasikan secara eksplisit. Tipe data dapat diketahui melalui konteks pernyataan. Tipe data berjenjang dapat didefiniskan dengan record layaknya berikut:
elemen = record
{
tipe_data1 data1;
.
.
.
tipe_data_n data_n;
elemen *link;
}
6. Pernyatan assignment dituliskan dengan := layaknya berikut:
<variable> := <nilai>;
7. Pernyataan for, while, if dituliskan sebagai berikut:
while <kondisi> do
{
<pernyataan 1>
.
.
.
<pernyataan n>
}


for variabel := nilai1 to nilai2 step langkah do
{
<pernyataan 1>
.
.
.
<pernyataan n>
}


if <kondisi> then <pernyataan>
if <kondisi> then <pernyataan 1> else <pernyataan 2>


case
{
:<kondisi 1> : <pernyataan 1>
:<kondisi 2> : <pernyataan 2>
.
.
.
:else: <pernyataan default>
}
8. Input dan output dinyatakan dengan read dan write. Format untuk menyatakan ukuran input dan output tidak digunakan.
9. Fungsi atau prosedur dituliskan dengan kata kunci Algorithm layaknya berikut:
Algorithm Nama (<paramenter-parameter> )

Contohnya adalah sebagai berikut:
Algorithm Maks(A,n)
//A adalah array dengan ukuran n
{
hasil := A[1];
for i :=2 to n do
if A[i]> hasil then hasil := A[i];
return hasil;
}
Cara Menulis Algoritma Originally published in Shvoong: http://id.shvoong.com/internet-and-technologies/software/2062814-cara-menulis-algoritma/

1. What Is an Algorithm

Summary:silahkansaja
The word algorithm comes from a Persian mathematician, Abu Ja'far Mohammed ibn Musa al Khorwarizmi (825 A.D.). The word has taken on special significance in mathematics, computer science and related subject in which it refer to methods that can be used to solved a problem. In formal definition algorithm is a finite sequences of instructions to accomplish a particular task.

The following criteria should be met to achieve a good algorithm:
It may has zero or more input.
It must produce one or more output.
Each instruction should be clear and unambiguous.
It should terminate after a finite steps of instruction.
It must be feasible.

What Is an Algorithm Originally published in Shvoong: http://www.shvoong.com/internet-and-technologies/software/2062634-algorithm/