|
| Minggu, 22 Juli 2007 |
| KOMPLEKSITAS WAKTU DAN RUANG |
Secara teoritis, model abstrak pengukuran waktu/ruang harus independent dari pertimbangan mesin dan compiler apapun. Model abstrak seperti itu dapat dipakai untuk membandingkan algoritma yang berbeda. Besaran yang dipakai untuk menerangkan model abstrak pengukuran waktu/ruang ini adalah kompleksitas algoritma.
Ada dua macam kompleksitas algoritma :
a) kompleksitas waktu
Kompleksitas waktu di ekspresikan sebagai jumlah tahapan komputasi yang dibutuhkan untuk menjalankan algoritma sebagai fungsi dari ukuran masukan n.
b) komplesitas ruang
kompleksitas ruang diekspresikan sebagai jumlah memori yang digunakan oleh struktur data yang terdapat di dalam algoritma sebagai fungsi dari ukuran masukan n.
Dengan menggunakan besaran kompleksitas waktu/ruang algoritma, kita dapat menentukan laju peningkatan waktu (ruang) yang diperlukan algoritma dengan meningkatnya ukuran masukan n.
TERMINOLOGI KOMPLEKSITAS WAKTU / RUANG
Terminologi yang diperlukan dalam membahas kompleksitas waktu dan kompleksitas ruang suatu algoritma adalah :
1. Ukuran besar masukan data untuk suatu algoritma, n.
Sebagai contoh, dalam algoritma pengurutan elemen-elemen larik, n adalah jumlah elemen larik, sedangkan dalam algoritma perkalian matriks n adalah ukuran matriks n x n. pada beberapa kasus, ukuran masukan lebih tepat menggunakan dua buah besaran, misalnya jika masukan algoritma adalah graf, maka ukuran masukan adalah jumlah simpul dan jumlah sisi.
2. Kompleksitas waktu, T(n), adalah jumlah operasi yang dilakukan untuk melaksanakan algoritma sebagai fungsi dari ukuran masukan n.
3. Kompleksitas ruang, S(n), adalah ruang memori yang dibutuhkan algoritma sebagai fungsi dari ukuran masukan n.
Pertimbangan lain mengapa hanya meninjau komplesitas waktu adalah tingkat kekritisan memori. Ukuran memori sekarang ini tidak lagi menjadi persoalan kritis, karena computer sekarang mempunyai ukuran memori yang besar dibandingkan dengan computer mainframe 25 tahun yang lalu. Bahkan, bila memori masih kurang, memori sekunder pun dapat dijadikan sebagai memori tambahan (memori semu, virtual memory). Tetapi, ini tidak berarti kita melupakan kompleksitas ruang, hanya saja kompleksitas waktu akan selalu menjadi isu utama dalam merancang suatu algoritma. |
posted by iKa gUnDuL @ 22.33  |
|
|
|
|
| About Me |
|
Name: iKa gUnDuL
Home: BeKaSe, JaBaR, Indonesia
About Me: makhluk halus("maksudnya lemah lembut geto") yang bernama lengkap raden ajeng dwi kartika sari harum mewangi sepanjang hari (Alah!) dilahirkan pada malam jumat kliwon di tengah sawah pas bulan purnama(mang gw tukul(turunan kuntilanak!) tanggal 19 SEPTEMBER 1987 (tlisannya ged2 biar dikasih kado! huahah ngarep!). ce' berbintang virgo ini merupakan anak ke 2 dari 4 bersaudara. yang hobbynya makan orang dan tidur di kuburan... kan gw poccy(panggilan si ina en revi jelek)
See my complete profile
|
| Previous Post |
|
| Archives |
|
| Links |
|
|
| Template by |
|
|
