Senin, 19 Desember 2011

Algoritma dan Kompleksitas Waktu


1. Algoritma
Algoritma adalah deskripsi langkah-langkah penyelesaian masalah yang tersusun secara logis atau urutan logis pengambilan keputusan untuk pemecahan suatu masalah. Algoritma ditulis dengan notasi khusus, notasi mudah dimengerti dan notasi dapat diterjemahkan menjadi sintaks suatu bahasa pemrograman.
Algoritma merupakan salah satu cabang ilmu komputer yang membahas prosedur penyelesaian suatu permasalahan. Dengan algoritma yang baik maka komputer bisa menyelesaikan perhitungan dengan cepat dan benar. Sebaliknya jika algoritma kurang baik maka penyelesaian lambat dan bahkan tidak didapat solusi yang diharapkan.
Suatu algoritma akan memerlukan masukan (input) tertentu untuk memulainya, dan akan menghasilkan keluaran (output) tertentu pada akhirnya. Hal-hal yang perlu diperhatikan dalam algoritma adalah mencari langkah-langkah yang paling sesuai untuk penyelesaian suatu masalah, karena setiap algoritma memiliki karakteristik tertentu yang memiliki kelebihan dan kekurangan. Beberapa hal yang harus dipahami dalam mencari algoritma antara lain:
1.      Masalah seperti apa yang hendak diselesaikan.
2.      Gagasan apa yang ada pada algoritma tersebut.
3.      Berapa lama yang diperlukan untuk menyelesaikan masalah.
4.      Berapa jumlah data yang dapat ditangani oleh suatu algoritma.

2.    Kompleksitas Waktu
Sebuah algoritma tidak saja harus menghasilkan keluaran yang benar, tetapi juga harus mangkus (efisien). Kebenaran suatu algoritma harus diuji dengan jumlah masukan tertentu untuk melihat kinerja algoritma berupa waktu yang diperlukan untuk menjalankan algoritmanya dan ruang memori yang diperlukan untuk struktur datanya.
Algoritma yang bagus adalah algoritma yang mangkus (efisien). Kemangkusan algoritma diukur dari berapa jumlah waktu dan ruang memori yang dibutuhkan untuk menjalankan algoritma tersebut. Algoritma yang mangkus adalah algoritma yang meminimumkan kebutuhan waktu dan ruang.
Implementasi sebuah algoritma dapat dikatakan baik atau efisien adalah memerlukan kriteria formal yang digunakan untuk menilai algoritma tersebut yaitu kemangkusan algoritma dengan kompleksitasnya. Besaran yang dipakai untuk menerangkan model penilaian waktu/ruang algoritma adalah dengan menggunakan kompleksitas algoritma.
Ada dua macam kompleksitas algoritma, yaitu kompleksitas waktu dan kompleksitas ruang. Kompleksitas waktu dari algoritma adalah mengukur jumlah perhitungan (komputasi) yang dikerjakan oleh komputer ketika menyelesaikan suatu masalah dengan menggunakan algoritma. Ukuran yang dimaksud mengacu ke jumlah langkah-langkah perhitungan dan waktu tempuh pemrosesan.
Kompleksitas waktu merupakan hal penting untuk mengukur efisiensi suatu algoritma. Kompleksitas waktu dari suatu algoritma yang terukur sebagai suatu fungsi ukuran masalah.
Kompleksitas waktu dari algoritma berisi ekspresi bilangan dan jumlah langkah yang dibutuhkan sebagai fungsi dari ukuran permasalahan. Kompleksitas ruang berkaitan dengan sistem memori yang dibutuhkan dalam eksekusi program. Pada tabel di bawah diperlihatkan kelompok algoritma berdasarkan kompleksitas waktu asimptotiknya.
  
Kelompok Algoritma
Nama
O(1)
Konstan
O(log n)
Logaritmik
O(n)
Linear
O(n log n)
n log n
O(n2)
Kuadratik
O(n3)
Kubik
O(2n)
Eksponensial
O(n!)
Faktorial


Berdasarkan tabel di atas, maka dapat digambarkan grafik kelompok algoritma dengan kompleksitas waktu asimptotiknya seperti yang terlihat pada gambar berikut:

 
Kebutuhan waktu dan ruang suatu algoritma bergantung pada ukuran masukan, yang secara khas adalah jumlah data yang diproses. Ukuran masukan itu disimbolkan dengan n. Setelah menetapkan ukuran masukan, maka langkah selanjutnya dalam mengukur kompleksitas waktu adalah menghitung banyaknya operasi yang dilakukan algoritma sehingga didapatkan notasi kompleksitas waktunya dalam fungsi n yaitu f(n).
Untuk mengukur kebutuhan waktu sebuah algoritma yaitu dengan mengeksekusi langsung algoritma tersebut pada sebuah komputer, lalu dihitung berapa lama durasi waktu yang dibutuhkan untuk menyelesaikan sebuah persoalan dengan n yang berbeda-beda. Kemudian dibandingkan hasil komputasi algoritma tersebut dengan notasi kompleksitas waktunya untuk mengetahui efisiensi algoritmanya.




DAFTAR PUSTAKA / REFERENSI

Gloor, P. A., Johnson, D. B., Makedon, F., Metaxas, P., (1993), A Visualization System for Correctness Proofs of Graph Algorithms, http://www.wellesley.edu/CS/pmetaxas/visual_proofs.pdf, Computer Science Education, [19 Maret 2010].

Greenberg, H. J., (1998), Greedy Algorithm for Minimum Spanning Tree, http://glossary.computing.society.informs.org/notes/spanningtree.pdf, University of Colorado, Denver, [19 Maret 2010].

Kristanto, A., (2008), Perancangan Sistem Informasi dan Aplikasinya, Gava Media, Yogyakarta.

Mehta, D. P., Sahni, S., (2005), Handbook of Data Structures and Applications, Chapman & Hall/CRC Computer and Information Science Series, United States of America.

Munir, R., (2009), Matematika Diskrit, Edisi 3, Informatika, Bandung.

Oetomo, B. S., (2002), Perencanaan dan Pembangunan Sistem Informasi, Andi, Yogyakarta.

Pop, P. C., Zelina, I., (2004), Heuristic Algorithms for the Generalized Minimum Spanning Tree Problem, http://emis.library.cornell.edu/ journals/AUA/acta8/Pop_Zelina.pdf, Proceedings of the International Conference on Theory and Applications of Mathematics and Informatics (ICTAMI), Thessaloniki, Greece, [19 Maret 2010].

Purbasari, I. Y., (2007), Desain Dan Analisis Algoritma, Edisi 1, Graha Ilmu, Yogyakarta.

Purwanto, E. B., (2008), Perancangan Dan Analisis Algoritma, Edisi 1, Graha Ilmu, Yogyakarta.

Zakaria, T. M., Prijono, A., (2006), Konsep Dan Implementasi Struktur Data, Informatika, Bandung.
Diposting oleh di 04.50 0 komentar

Latihan Pemrograman C (1)

/* Program membalik Array */

#include <stdio.h>

int main ()
{
                int data[] = {2, 2, 7, 9, 3, 1};

                int i;
                for (i = 5; i > 0; i--)
                printf("%d", data[i]);

                                printf("\n");

                return 0;
}
//Menjumlahkan Matriks

#include <stdio.h>
#include <conio.h>
main()
{
                                int a[4]={3,7,4,6};
                                int b[4]={8,0,5,2};
                                int c[4],i;

                                for (i=0;i<4;i++) printf("a[%d]= %d\n",i+1,a[i]);
                                printf("\n\n");
                                for (i=0;i<4;i++) printf("a[%d]= %d\n",i+1,b[i]);
                                printf("\n\n");
                                printf("  A   +    B  =    C\n\n");
                                for (i=0;i<4;i++)
                                {
                                                 c[i]=a[i]+b[i];
                                                 if (i==1) printf("|%3d| + |%3d| = |%3d|\n",a[i],b[i],c[i]);
                                                 else printf("|%3d|   |%3d|   |%3d|\n",a[i],b[i],c[i]);
                                }
                                getch();
}


//Menjumlahkan Matriks A + Matriks B hasilnya Matriks C

#include <stdio.h>
main()
{
  int i,j;
  int A[4][3],B[4][3],C[4][3]; /* deklarasi array */
  /* Membaca A data dari keyboard */
  printf("\tMasukkan matriks A : \n");
  for (i=0;i<4;i++)
                 {
                  for(j=0;j<3;j++)
                                 {
                                  printf("\t\tA(%d,%d): ",i,j);
                                  scanf("%d", &A[i][j]);
                                 }
                 }

  printf("\n\tMasukkan matriks B : \n");
  for (i=0;i<4;i++)
                 {
                  for(j=0;j<3;j++)
                                 {
                                  printf("\t\tB(%d,%d): ",i,j);
                                  scanf("%d", &B[i][j]);
                                 }
                 }

                for (i=0;i<4;i++)
                 {
                  for(j=0;j<3;j++)
                                                C[i][j]=B[i][j]+A[i][j];
                 }

printf("\n\n");
/* Menampilkan data matriks yang telah dimasukkan */
printf("\n   Matriks A    +      Matriks B   =                 Matriks C\n");
for (i=0;i<4;i++)
  {
                 for(j=0;j<3;j++)
                                  printf("%4d",A[i][j]);
                 printf("        ");
                 for(j=0;j<3;j++)
                                  printf("%4d",B[i][j]);
                 printf("        ");
                 for(j=0;j<3;j++)
                                  printf("%4d",C[i][j]);
                 printf("\n");


}
}


/* Program membalik Array */

#include <stdio.h>

int main ()
{
int data[] = {3, 1, 7, 9, 2};

int tmp;
int i;
for (i = 0; i < 4; i +=2)
{
tmp = data [i];
data[i] = data[i+1];
data [i+1] = tmp;
}

/* Tampilkan isi Larik*/

for (i = 0; i < 5; i++)

printf("%d", data[i]);

printf("\n");

return 0;
}


/* ------------------------------------------------ */
/* File program : baca.c */
/* Contoh pengaksesan array satu dimensi */
/* ------------------------------------------------ */
#include <stdio.h>
#define maks_tes 5
main()
{
int i;
float nilai_tes[maks_tes]; /* deklarasi array */
/* Membaca data dari keyboard */
for (i=0;i<maks_tes;i++)
{
printf("Nilai tes ke-%d: ",i+1);
scanf("%f", &nilai_tes[i]);
}
/* Menampilkan data yang telah dimasukkan */
for (i=0;i<maks_tes;i++)
{
printf("Nilai tes ke-%d: %4.2f\n",i+1,nilai_tes[i]);
}
}
/* ------------------------------------------------ */
/* File program : baca2.c */
/* Contoh pengaksesan array dua dimensi */
/* ------------------------------------------------ */
#include <stdio.h>
main()
{
int i,j;
int matriks[4][3]; /* deklarasi array */
/* Membaca data dari keyboard */
for (i=0;i<4;i++)
{
for(j=0;j<3;j++)
{
printf("matriks (%d, %d): ",i,j);
scanf("%d", &matriks[i][j]);
}
}
printf("\n\n");
/* Menampilkan data matriks yang telah dimasukkan */
for (i=0;i<4;i++)
{
for(j=0;j<3;j++)
{
printf(" Matriks(%d, %d): %d",i,j,matriks[i][j]);
}
printf("\n");
}
}
/***************************************************
*  TUGAS PEMROGRAMAN   *
*  ----------------------------------------------  *
*    Tugas  : Mencari Rerata Semua Bilangan    *
***************************************************/
#include <stdio.h>
#define max 5

int main()
{
                float A[max], jumlah=0, rata_rata;
                int j;

                /*Memasukkan nilai ke dalam elemen array*/

                printf("Memasukkan Nilai :\n\n");
                for (j=0; j<max; j++)
                {
                                printf("Nilai Ke-%d = ",j+1);
                                scanf("%f", &A[j]);
                                jumlah += A[j];
                }
                /*Melakukan proses perhitungan rata-rata*/

                rata_rata = jumlah/max;

                /*Menampilkan hasil perhitungan*/
                printf("\nNilai Rata-Rata = %.2f", rata_rata);
                return 0;
}
/*Cari Nilai Yang Terbesar*/

#include <stdio.h>
#define max 5

main()
{
                int i, besar;
                int A[max];   /*deklarasi array*/


                /*Membaca data dari keyboard*/

                for (i=0; i<max; i++)
                {
                                printf("Nilai Ke-%d : ",i+1);
                                scanf("%d", &A[i]);
                }

                /*Menampilkan nilai terbesar*/
                besar = A[0];
                for (i=1; i<max; i++)
                if (besar<A[i])
                                besar = A[i];

                printf("\n\nNilai Terbesar  = %d", besar);
}
Diposting oleh di 04.43 1 komentar
Langganan: Postingan (Atom)