MATRIX MULTIPLICATION
ALGORHTM
WAHYU SRI MULYANI
(17/418671/PPA/05455)
Computer
Science Post Graduate Program
Department of Computer Science and Electronics
Faculty of Mathematics and Natural Sciences
Department of Computer Science and Electronics
Faculty of Mathematics and Natural Sciences
Universitas
Gadjah Mada
2017
A. LATAR
BELAKANG
Sebuah
matriks sangat sering digunakan dalam komputasi ilmiah. Pengolahan citra
digital adalah salah satu contok penggunaan matriks yang adal di dalamnya.
Matriks yang terdapat memiliki ordo yang besar, sehingga untuk pemrosesan
dibutuhkan waktu yang sebanding. Operasi yang sering dijumpai adalah perkalian
matriks.
Perkalian
matriks dengan ordo yang besar memiliki kompleksitas yang tersendiri. Hal
tersebut akan berdampak terhadap waktu tempuh algoritma. Latar belakang di atas
menjadi dasar penulis untuk melakukan percobaan terhadap teori kompleksitas
waktu pada perkalian matriks.
B. TUJUAN
Tujuan
dari percobaan ini adalah mengetahui kompleksitas waktu dalam perkalian matriks
dan kebenaran dari teori yang telah diberikan.
C. RUMUSAN
MASALAH
Rumusan
masalah dari percobaan ini adalah bagaimana kompleksitas waktu dari perkalian
matriks dengan ordo 200, 400, 800 dan 1600.
D. LANDASAN
TEORI
Kompleksitas waktu adalah
sebuah fungsi f(n) yang diberikan untuk menyatakan waktu tempuh dan kebutuhan
storage dengan ukuran n input data.
F(n) merupakan “big oh”
dari G(n) dengan notasi F(n) = O(G(n)) jika dan hanya jika tedapat dua
konstanta bulat positif C dan no sedemikian hingga |F(n)| £ C |G(n)| untuk setiap n > no.
F(n) merupakan “omega” dari
G(n) dengan notasi F(n) = Ω (G(n)) jika dan hanya jika terdapat dua buah
konstanta positif C dan m sedemikian hingga |F(n)| ³
C |G(n)| untuk setiap n ³ m.
F(n) merupakan “theta” dari
G(n) dengan notasi F(n) = Ó¨ (G(n)) jika dan hanya jika terdapat dua buah
konstanta positif C1, C2 dan m sedemikian hingga.
C1 £
|F(n)| £ C2 |G(n)|
untuk setiap n ³ m.
Teorema 1:
Jika F(n) adalah fungsi polinomial dalam n dengan derajat
m, yang ditulis dengan:
F(n)
= am Nm + am-1 Nm-1 +
… + a1 N + a0
Maka ‘Big Oh’ dari F(n) adalah Nm yang
dinotasikan:
F(n) = O(Nm)
Keadaan kompleksitas waktu
·
Worst case (nilai maksimum dari nilai F(n) utk semua input yg mungkin.
Keadaan yang terburuk dr suatu algoritma)
·
Average case (keadaan dr waktu tempuh yg ekivalen dgn nilai ekspektasi
dari F(n) utk setiap input data yang mungkin. Nilai ekspektasi didefinisikan
sbg:
E= n1 p1 + n2 p2 +
….. + nk pk
n = nilai nilai yang muncul
p = probabilitas dr setiap
n yg muncul
·
Best case (suatu keadaan yang merupakan nilai minimum dari F(n) untuk
setiap input yang mungkin. Ini keadaan yang terbaik dari suatu algoritma. Sehingga
waktu tempuhnya minimal.
Hal
yang mempengarungi waktu tempuh antara lain :
-
Banyaknya langkah
-
Besar dan jenis inputan
-
Jenis operasi
-
Computer dan kompilator
Gambar
berikut adalah grafik perbandingan masing-masing kompleksitas waktu algoritam.
Beberapa jenis
kelas efisiensi umum yang dijumpai dalam Big-O, yaitu:
|
Fungsi Big-O
|
Nama
|
|
O(1)O(1)
|
Konstan
|
|
O(logn)O(logn)
|
Logaritmik
|
|
O(n)O(n)
|
Linear
|
|
O(nlogn)O(nlogn)
|
n log n
|
|
O(n2)O(n2)
|
Kuadratik
|
|
O(nm)O(nm)
|
Polinomiale
|
|
O(n!)O(n!)
|
Faktorial
|
E. ANALISIS
HASIL PERCOBAAN
1.
Percobaan
1 (Seluruh Matriks di tampilkan)
Percobaan pertama dilakukan dengan
menampilkan matrik input, yaitu matriks A dan matriks B. Setelah itu matriks di
kalikan dan dihasilkan matriks C yang selanjutnya matriks hasil tersebut di
tampilkan ke layer. Berikut adalah grafik yang terjadi pada percobaan pertama.
|
Ukuran Matriks
|
Waktu Tempuh Percobaan 1
|
|
200
|
31621
|
|
400
|
86841
|
|
800
|
322773
|
|
1600
|
1.37E+11
|
Terlihat di grafik, pada data 1600 terjadi
kenaikan yang cukup tinggi dan menjadikan perhitungan waktu error. Sehingga
jika dilihat pada grafik kompleksitas waktu algoritma, notasi big-O yang
terjadi adalah O(n2). Oleh Karena itu percobaan pertama dapat
disimpulkan sesuai dengan teori kompleksitas waktu.
2.
Percobaan
2 (Hasil ditampilkan)
Percobaan kedua dilakukan dengan
tidak menampilkan matriks inputan akan tetapi menampilkan matriks hasil
perkalian. Berikut adalah hasil dari run program tersebut.
200 data
400 data
800 data
1600 data
Gambar grafik di atas adalah hasil dari
percobaan 2 yaitu dengan menampilkan matriks hasil perkalian. Seperti halnya
percobaan pertama, grafik terlihat seperti pada grafik kompleksitas waktu
algoritma dengan notasi big-O yang terjadi adalah O(n2). Oleh karena
itu percobaan pertama dapat disimpulkan sesuai dengan teori kompleksitas waktu.
3.
Percobaan
3 (tidak menampilkan data matriks)
200 data
400 data
800 data
16.000 data
Percobaan ke 3 dilakukan tanpa
melakukan print matriks inputan dan matriks hasil perkalian. Sehingga dilakukan
perhitungan waktu perkalian matriks secara bersih. Grafik di atas merupakan
hasil waktu yang diperoleh dari running coding yang sudah dibuat. Jika di
lakukan perbandingan dengan grafik kompleksitas waktu, maka grafik yang terjadi
di atas memiliki notasi O(n2).
4.
Percobaan
4
200 data
400
data
800
data
1600
data
2400
data
Percobaan ke 4 dilakukan dengan
penambahan data 2400. Terjadi kenaikan grafik yang signifikan dari angka 10.000
menjadi 27.000. Seperti terlihat pada grafik, pola yang dibentuk masih sama
seperti percobaan sebelumnya.
Dari ke empat percobaan yang telah dilakukan dengan
beberapa perilaku yang diberikan, mendapatkan hasil notasi O(n2).
Sehingga dapat disimpulkan untuk operasi perkalian matriks kompleksitas waktu
yang dibutuhkan adalah O(n2).
|
#include
<stdio.h>
#include
<conio.h>
#include
<stdlib.h>
#include
<time.h>
#include
<iostream>
#include
<fstream>
#include
<cstdlib>
#include
<ctime>
using
namespace std;
int
main()
{
double **A,**B,**C, t1;
int i,j,k,koloma,barisa,n,barisb,kolomb;
srand((unsigned)time(NULL));
printf("<< Program Perkalian
Matriks >>\n\n");
printf("Baris matriks A :
");scanf("%i",&barisa);
printf("Kolom matriks A :
");scanf("%i",&koloma);
printf("Baris matriks B :
");scanf("%i",&barisb);
printf("Kolom matriks B :
");scanf("%i",&kolomb);
printf("Range angka random :
0-");scanf("%i",&n);
if (koloma!=barisb)
{
printf("Lebar matriks A tidak
sama dengan Panjang Matriks B\n");
exit(EXIT_SUCCESS);
}
else
{
//alokasi memori untuk matriks A
A=(double**)
malloc(barisa*sizeof(double*));
for(i=0;i<barisa;i++)
A[i]=(double*)malloc(koloma*sizeof(double));
//alokuasi memori untuk matriks B
B=(double**) malloc(barisb*sizeof(double*));
for(i=0;i<barisb;i++)
B[i]=(double*)malloc(kolomb*sizeof(double));
//alokasi memori untuk matriks C
C=(double**)
malloc(barisa*sizeof(double*));
for(i=0;i<barisa;i++)
C[i]=(double*)malloc(kolomb*sizeof(double));
//Menampilkan
input random matriks A
// printf("\nMatriks A:
\n");
for (i=0;i<barisa;i++)
{
for (j=0;j<koloma;j++)
{
A[i][j]= (rand()%n);
/*
printf("%.0lf",A[i][j]);
if (j == (koloma-1))
printf("\n");
else
printf(" ");
*/
}
}
//menampilkan input random matriks
B
// printf("\nMatriks B:
\n");
for (i=0;i<barisb;i++)
{
for (j=0;j<kolomb;j++)
{
B[i][j]=(rand()%n);
/*
printf("%.0lf",B[i][j]);
if (j == (kolomb-1))
printf("\n");
else
printf(" ");
*/
}
}
//menampilkan hasil perkalian
matriks
// printf("\n\nPerkalian
Matriks (A.B):\n");
for (i=0;i<barisa;i++)
{
for (j=0;j<kolomb;j++)
{
C[i][j] = 0;
for (k=0;k<koloma;k++)
{
C[i][j] += A[i][k]
* B[k][j];
}
/*
printf("%.0lf",
C[i][j]);
if (j == (kolomb-1))
printf("\n");
else
printf(" ");
*/
}
}
//disalokasi memori A,B,C
for(i=0;i<barisa;i++)
free(A[i]);
for(i=0;i<barisb;i++)
free(B[i]);
for(i=0;i<barisa;i++)
free(C[i]);
free(A);
free(B);
free(C);
t1 = clock();
cout << "WAKTU = "
<< t1<< " msec\n";
}
getch();
}
|
Komentar
Posting Komentar