## PENERAPAN KOMPLEKSITAS WAKTU ALGORITMA PRIM UNTUK MENGHITUNG KEMAMPUAN KOMPUTER DALAM MELAKSANAKAN PERINTAH
Deny Wiria Nugraha
Jurusan Teknik Elektro, Fakultas Teknik, Universitas Tadulako Email : deny_wiria_nugraha@yahoo.co.id
Abstract -  The  purpose  of  this  study  is  to develop the software using both Delphi 7 and ArcView  GIS  3.3  programming  language which  is  able  to  apply  Prim's  algorithm  in obtaining  the  time  complexity  used  to calculate  the  cability  of  computer  in executing the command.  This study not only compares two pieces of software built  by the authors but also compares the cability of two computers that each have different specifications.
It  has  been  proven  that  the  software generated in this study can be utilized to get the  complexity  of  time  by  using  Prim’s algorithm  which  is  used  to  calculate  the ability  of  computer  in  executing  the command.  The  software  can  also  accurately display the  minimum  spanning  tree  as  a result of applying the Prim's algorithm.  The capability  of  computer  is  examined  in  terms of  the  accuracy  and  speed  in  executing  the commands.  The  examination  result  shows that  the  capability  of  the  first  computer specifications is higher than the capability of the  second  computer  specifications  in applying  the  Prim's  algorithm.  The  other result  found  in  this  study  shows  that  the computation  time  software  built  in  Delphi  7 is faster than the computation time software built  in  ArcView  GIS  3.3.  This  result indicates that in terms of applying the Prim's algorithm,  the  software  built  in  Delphi  7  is more  efficient  than  the  software  built  in ArcView GIS 3.3.
Keywords: Time Complexity, Prim’s Algorithm, The Ability of Computer

## I. PENDAHULUAN
Penggunaan komputer dalam berbagai  bidang  saat  ini  berkembang dengan pesatnya. Aplikasi-aplikasi
komputer  banyak  digunakan  di  berbagai bidang tersebut antara lain: bidang pendidikan  misalnya e-learning ;  bidang pemerintahan misalnya e-government ;
bidang  teknik  misalnya  aplikasi computer aided  design (CAD);  bidang  industri misalnya aplikasi computer aided manufacturing (CAM);  bidang  seni  dan grafik  misalnya  photoshop  dan  coreldraw; bidang bisnis misalnya e-commerce ; bidang kesehatan misalnya aplikasi ultra sonografi (USG)  dan  aplikasi computerized  axial tonography ;  dan  lain-lain.  Penggunaan komputer  memiliki  banyak  keuntungan antara lain: mengotomasi dan memudahkan pekerjaan-pekerjaan  yang  rutin  dan  berat secara fisik, memperkaya sumber informasi sehingga  interaksi  dan  kualitas  keputusan menjadi lebih baik, memiliki kecepatan dan ketelitian dalam mengerjakan suatu perintah,  memiliki  media  penyimpanan yang  ringkas  dan  berkapasitas  besar,  dan mampu  mengolah  data  dalam  jumlah  yang besar.
Semua  aplikasi  komputer  sangat menuntut kemampuan komputer yang baik. Kemampuan  komputer  yang  baik  adalah kecepatan  dan  ketepatan  komputer  dalam melaksanakan suatu perintah yang diberikan oleh pengguna komputer. Komputer  dapat  melakukan  suatu  operasi dasar, seperti misalnya perhitungan, penjumlahan  atau  pengurangan  dalam waktu yang sangat cepat. Untuk menghitung  kemampuan  komputer  yaitu kecepatan dan ketepatannya, maka diperlukan  suatu  algoritma  untuk  menguji kemampuan  komputer  tersebut.  Algoritma yang digunakan dalam penelitian ini adalah algoritma Prim. Algoritma ini menggunakan metode Greedy yang merupakan  salah  satu  metode  untuk merancang dan mendesain suatu algoritma. Metoda  ini  membangun  suatu  pohon merentang  minimum  dengan  memeriksa garis  demi  garis  untuk  memilih  garis dengan  bobot  kecil  dan  membuang  garis
dengan  bobot  besar,  sehingga  terbentuk suatu  pohon  merentang  minimum.  Metode ini  digunakan  untuk  mendapatkan  solusi yang optimal dari suatu permasalahan.
Tujuan  penelitian  ini  adalah  untuk membangun perangkat lunak dengan menggunakan bahasa pemrograman Delphi 7  dan  program  ArcView  GIS  3.3  yang mampu  mengaplikasikan  algoritma  Prim untuk mendapatkan kompleksitas waktunya guna diterapkan untuk menghitung kemampuan komputer dalam melaksanakan perintah.  Penelitian  ini  membandingkan dua  buah  perangkat  lunak  yang  dibangun penulis  dan  membandingkan  kemampuan dua unit komputer dengan spesifikasi yang berbeda.
Rumusan masalah dalam penelitian ini  berkaitan  dengan  bagaimana  caranya menghitung  kemampuan  komputer  dalam melaksanakan perintah yang diberikan oleh pengguna  komputer.  Hal  tersebut  memberi arti  bahwa  perlu  dibangun  suatu  perangkat lunak yang mampu mengaplikasikan algoritma  Prim  dengan  menggunakan bahasa pemrograman Delphi 7 dan program ArcView  GIS  3.3  untuk  mendapatkan kompleksitas  waktu  algoritma  Prim,  yang diuji  pada  dua  unit  komputer  dengan spesifikasi yang berbeda.

## II. TINJAUAN PUSTAKA
A.  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  (Zakaria  dan Prijono, 2006:5).
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.
B.  Kompleksitas Waktu “Sebuah  algoritma  tidak  saja  harus menghasilkan  keluaran  yang  benar,  tetapi juga  harus  mangkus  (efisien)  (Munir, 2009:495)”.  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 jumlah waktu  dan  ruang  memori  yang  dibutuhkan untuk  menjalankan  algoritma  tersebut. Algoritma  yang  mangkus  adalah  algoritma yang meminimumkan kebutuhan waktu dan ruang.
Aplikasi  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 1 diperlihatkan kelompok algoritma berdasarkan kompleksitas waktu asimptotiknya.
Tabel 1. 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(n 2 ) Kuadratik O(n 3 ) Kubik O(2 n ) Eksponensial O(n!) Faktorial Berdasarkan  tabel  1  di  atas,  maka dapat digambarkan grafik kelompok algoritma  dengan  kompleksitas  waktu asimptotiknya  seperti  yang  terlihat  pada gambar 1..
Gambar 1 . Kelompok algoritma dengan kompleksitas waktu asimptotiknya (Mehta dan Sahni, 2005:24)
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.
C.   Algoritma Prim Graf G didefinisikan sebagai pasangan  himpunan  (V,  E),  ditulis  dengan notasi  G  =  (V,  E).  Dalam  hal  ini,  V merupakan  himpunan  tidak  kosong  dari simpul-simpul ( vertices atau node ) digambarkan dalam titik-titik, dan E adalah himpunan  sisi-sisi  ( edges atau arcs ) digambarkan dalam garis-garis yang menghubungkan  sepasang  simpul  (Munir, 2009:356). Sedangkan graf berbobot adalah graf yang setiap sisinya diberi sebuah harga. Bobot  pada  tiap  sisi  dapat  berbeda-beda bergantung  pada  masalah  yang  dimodelkan dengan graf.
Jika  G  adalah  graf  berbobot,  maka bobot  pohon  merentang  T  dari  G didefinisikan  sebagai  jumlah  bobot  semua sisi  di  T.  Pohon  merentang  yang  berbeda mempunyai  bobot  yang  berbeda  pula. Diantara  semua  pohon  merentang  dalam graf  G,  pohon  merentang  yang  berbobot minimum  dinamakan  pohon  merentang minimum.  Pohon  merentang  minimum mempunyai  terapan  yang  luas  dalam praktek (Munir, 2009:450).
Algoritma  Prim  dimulai  dari  simpul yang  berubah-ubah  di  setiap  tingkatnya, diperbolehkan  menambah  cabang  baru untuk  membuat  susunan  pohon  baru. Algoritma  ini  akan  tertahan  ketika  simpul yang  sedang  dieksplorasi  pada  graf  sudah sampai  pada  simpul  yang  dituju.  Strategi
yang  digunakan  adalah  strategi  Greedy dengan  menganggap  bahwa  pada  setiap langkah  dari  pohon  merentangnya  adalah augmented dan  dipilih  simpul  yang nilainya  paling  kecil  dari  semua  simpul yang ada (Purwanto, 2008:86).
Beberapa peneliti
yang menggunakan  metode  Greedy  diantaranya adalah, yang pertama Borůvka tahun 1926, selanjutnya  dengan  metoda  yang  sama, penelitiannya  ditinjau  ulang  oleh  Choquet tahun  1938,  Lukasziewicz,  Florek,  Perkal, Steinhaus  dan  Zubrzycki  tahun  1951. Algoritma  Borůvka  dimulai  dari  n  titik terasing dari graf (graf semula tanpa garis), kemudian  dari  masing-masing  titik  dipilih garis dengan bobot terkecil yang berhubungan  dengan  titik  tersebut.  Karena setiap  garis  mempunyai  dua  titik,  maka dimungkinkan ada garis yang diperiksa dua kali.
Peneliti  selanjutnya  adalah  Kruskal tahun  1956,  yang  menyusun  garis-garis dalam urutan tidak menurun ( non decreasing )  dari  bobotnya.  Langkah  awal adalah memilih garis dengan bobot terkecil diantara  semua  garis.  Selanjutnya  memilih garis  dengan  bobot  terkecil  berikutnya diantara  sisa  garis,  dengan  garis  tersebut menghubungkan  titik  di  dalam  pohon bagian  yang  sudah  dipilih  dengan  titik diluar pohon bagian.
Matematikawan Vojtěch Jarník tahun  1930  mengenalkan  suatu  metoda penentuan pohon merentang, yang selanjutnya  diteliti  kembali  oleh  Robert  C. Prim  tahun  1957  dan  Dijkstra  tahun  1959 sehingga  menghasilkan  suatu  algoritma yang dikenal dengan nama algoritma Prim.
Algoritma Prim menitikberatkan pada pemilihan bobot
minimum berdasarkan  simpul  yang  diambil.  Dan karena  tidak  perlu  mengurutkan  terlebih dahulu, algoritma Prim cocok untuk pohon dengan  jumlah  simpul  banyak.  Algoritma Prim  akan  selalu  berhasil  menemukan pohon  merentang  minimum  tetapi  pohon merentang  yang  dihasilkan  tidak  selalu unik.
Langkah-langkah  dalam  algoritma  Prim adalah sebagai berikut:
1. Buat sebuah pohon yang terdiri dari satu simpul  ( node ),  dipilih  secara  acak  dari graf.
2. Buat  sebuah  himpunan  yang  berisi semua cabang di graf.
3. Ulangi  sampai  semua  cabang  di  dalam himpunan  menghubungkan  dua  simpul di pohon:
a. Hapus  dari  himpunan  satu  cabang dengan bobot terkecil yang menghubungkan  satu  simpul  di pohon  dengan  satu  simpul  di  luar pohon.
b. Hubungkan  cabang  tersebut  ke pohon.
D.   Kemampuan Komputer Komputer  merupakan  suatu  alat elektronik yang mampu melakukan berbagai  tugas,  yaitu:  menerima  input, memproses input sesuai perintah, menyimpan perintah-perintah dan hasil dari pengolahan,  menyediakan  output  dalam bentuk  informasi,  memberikan  informasi, dan  bekerja  secara  otomatis  (Sudarmawan dan Ariyus, 2007:47).
Kemampuan  komputer  yang  paling menakjubkan
adalah
kecepatannya.
Komputer  dapat  melakukan  suatu  operasi dasar,  misalnya  perhitungan,  penambahan atau  pengurangan,  dalam  waktu  yang sangat  cepat,  yaitu  dalam  waktu mili second , mikro  second , nano  second atau piko  second .  Komputer  yang  cepat  dapat melakukan  operasi  dalam  waktu pico second . Komputer mainframe dapat mempunyai kecepatan sampai denga n lebih dari 1000 MIPS ( million instructions per second ). Komputer dengan kecepatan  1000  MIPS  dapat  mengolah sebanyak 1.000.000.000 (1 milyar) instruksi/perintah per detiknya. Kemampuan komputer lainnya yang menakjubkan  adalah  ketepatannya.  Kalau manusia lelah, maka mentalnya akan luluh, yang  akan  berakibat  kecenderungan  untuk melakukan kesalahan. Misalnya saja manusia disuruh untuk melakukan perhitungan sebanyak 100000 buah penambahan, yang akan diselesaikan dalam waktu  satu  hari  terus  menerus  tanpa berhenti,  maka  akan  dijamin  bahwa
manusia akan melakukan kesalahan. Sebaliknya, karena komputer tidak mempunyai  mental  dan  tidak  mengenal lelah, maka komputer tidak akan mengalami kesalahan (Purnama,  2012:32- 38).
Hasil  studi  literatur  yang  penulis lakukan, mengindikasikan bahwa
penelitian  tentang  kompleksitas  waktu pernah  dilakukan  oleh  beberapa  peneliti lainnya  yaitu  Indriati (2000)  yang  meneliti tentang  pohon  merentang  minimum  pada graf monge untuk
menentukan
kompleksitas  dan  waktu  tempuh  suatu algoritma. Penelitian tersebut hanya menggunakan  beberapa  titik/simpul  saja dan  hanya  menggunakan  program  yang sangat  sederhana.  Penelitian  Pop  dan Zelina (2004) menyajikan algoritma waktu eksponensial untuk graf tidak berarah yang memiliki  simpul-simpul n yaitu  algoritma heuristik berbasis Kruskal, algoritma heuristik  berbasis  Prim,  dan  algoritma heuristik  berbasis  pendekatan  global-lokal. Dilakukan  beberapa  macam  eksperimen waktu  komputasi  dengan  jumlah  simpul yang  bervariasi.  Pada  penelitian  yang penulis lakukan saat ini adalah membangun program  yang  sangat  lengkap  dengan menggunakan bahasa pemrograman Delphi 7  dan  program  ArcView  GIS  3.3,  yang diuji  pada  dua  unit  komputer  yang memiliki  spesifikasi  berbeda,  dan  menguji jumlah  titik/simpul  dan  jumlah  sisi  yang sangat banyak untuk menghasilkan kompleksitas  waktu  algoritma  Prim  secara akurat  yang  digunakan  untuk  menghitung kemampuan komputer
dalam melaksanakan perintah.

## III. METODE PENELITIAN
A. Bahan Penelitian
Data yang merupakan bahan penelitian ini dikumpulkan melalui beberapa metode sebagai berikut:
1. Studi literatur, yaitu penelusuran
literatur  mengenai  dasar  pengetahuan tentang  hal-hal  yang  berkaitan  dengan penelitian  ini.  Metode  ini  dilakukan dengan cara mencari buku-buku, artikel- artikel, dan jurnal-jurnal ilmiah
mengenai algoritma, kompleksitas waktu,  algoritma  Prim,  dan  perangkat keras serta perangkat lunak komputer.
2. Pengumpulan data dari lokasi penelitian berupa  data  spesifikasi  komputer  yang terdiri  dari  data  perangkat  keras  dan data perangkat lunaknya serta pengumpulan  data  model  graf  berbobot yang  akan  digunakan  oleh  perangkat lunak  yang  dibangun  dalam  penelitian ini.
B.   Alat Penelitian
Dalam  penelitian  ini  menggunakan spesifikasi perangkat keras komputer sebagai berikut:
1.  Komputer spesifikasi 1 yaitu menggunakan  prosesor  Intel  Core  2
CPU T5500 1,66GHz, memori 2,49 GB
RAM, hard disk 320 GB.
2.  Komputer spesifikasi 2 yaitu menggunakan prosesor Intel Atom CPU N270  1,60  GHz,  memori  1,48  GB
RAM, hard disk 160 GB.
Spesifikasi perangkat lunak komputer  menggunakan  sistem  operasi Microsoft  Windows  XP,  Borland  Delphi versi 7 dan ArcView GIS versi 3.3.
C.   Jenis Penelitian
Penelitian  ini  merupakan  penelitian kualitatif  dalam  bidang  teknik  elektro khususnya  bidang  rekayasa  perangkat lunak  dan  algoritma  komputer  yang  sesuai dengan  bidang  ilmu  penulis.  Penelitian  ini dilakukan  dengan  cara  membangun  suatu perangkat lunak (program) dengan menggunakan bahasa pemrograman Delphi 7  dan  program  ArcView  GIS  3.3  untuk mengaplikasikan algoritma Prim dan mendapatkan kompleksitas waktunya, yang digunakan  untuk  menghitung  kemampuan dua  unit  komputer  dengan  spesifikasi berbeda dalam melaksanakan perintah yang diberikan oleh pengguna komputer.
D.  Lokasi Penelitian
Lokasi  penelitian  ini  adalah  pada Laboratorium  Komputer  Jurusan  Teknik
Elektro Fakultas Teknik Universitas Tadulako, Palu, Sulawesi Tengah.
F.  Tahapan Penelitian Penelitian  ini  dilakukan  dengan melalui tahapan-tahapan sebagai berikut:
1. Melakukan pengamatan dan pengumpulan  data  mengenai  spesifikasi komputer dan model graf berbobot yang akan digunakan. 2. Instalasi perangkat lunak yang dibutuhkan. 3. Membangun  perangkat  lunak  dengan menggunakan bahasa pemrograman
Delphi 7 dan program ArcView GIS 3.3
untuk mengaplikasikan algoritma Prim.
4. Merancang  dan  memasukkan  model graf  berbobot  ke  dalam  program  yang telah dibangun.
5. Melakukan pengetesan/pengujian dengan menggunakan dua unit komputer  yang  memiliki  spesifikasi yang berbeda untuk mendapatkan kompleksitas waktu algoritma Prim. 6. Menghitung kemampuan komputer dalam melaksanakan perintah. 7. Menarik kesimpulan
dari hasil pengetesan/pengujian.

## IV. HASIL DAN PEMBAHASAN
Penelitian  ini  menghasilkan  dua perangkat  lunak  (program)  yaitu  program yang dibangun dengan
bahasa pemrograman  Delphi  7  dan  program  yang dibangun dengan ArcView GIS 3.3 dengan bantuan pemrograman script avenue . Bahasa pemrograman Delphi yang termasuk dalam salah satu bahasa pemrograman  visual  adalah  generasi  lanjut pemrograman  Pascal  (Malik,  2006:1). Delphi  telah  memanfaatkan  suatu  teknik pemrograman yang disebut Rapid Aplication  Develpment (RAD)  yang  telah membuat  pemrograman  menjadi  lebih mudah.  Delphi  merupakan  suatu  bahasa pemrograman  yang  telah  memanfaatkan metode  pemrograman Object  Oriented Programming (OOP).  Dengan  dukungan OOP, Delphi mempunyai kemampuan yang sangat  handal.  Hal  inilah  yang  menjadi daya  tarik  bagi  kebanyakan  orang  untuk menggunakan Delphi sebagai bahasa pemrograman  dewasa  ini.  Sedangkan ArcView  merupakan  salah  satu  perangkat
lunak  sistem  informasi  geografis  dan pemetaan  yang  telah  dikembangkan  ESRI ( Environmental Systems Research Institute ).  Dengan  ArcView,  pengguna dapat  memiliki  kemampuan-kemampuan untuk melakukan visualisasi, meng-
explore ,  menjawab query ,  dan  sebagainya (Prahasta, 2009:1).
Maksud  penggunaan  kedua  program tersebut  dalam  penelitian  ini  adalah  untuk mendapatkan hasil penerapan kompleksitas waktu  algoritma  Prim  untuk  menghitung kemampuan komputer dalam melaksanakan perintah  secara  akurat.  Pengujian  sistem pada  penelitian  ini  dilakukan  dengan parameter  pengujian  berupa  variasi  jumlah titik/simpul,  variasi  jumlah  sisi,  variasi model  graf  yang  memiliki  bobot  berupa panjang  garis  yang  menghubungkan  antara titik-titik, dan diuji pada dua unit komputer yang memiliki spesifikasi berbeda.
Penggunaan variasi jumlah titik/simpul, variasi jumlah sisi, dan variasi model  graf  berbobot,  serta  diuji  pada  dua unit  komputer  yang  memiliki  spesifikasi berbeda  adalah  untuk  mendapatkan  hasil pengujian yang lengkap berupa
kompleksitas  waktu  algoritma  Prim  dalam mencari  pohon  merentang  minimum  dan jumlah  total  jalur  minimum  graf  berbobot, di  mana  data  kompleksitas  waktu  yang telah  didapatkan tersebut, digunakan  untuk menghitung  kemampuan  komputer  dalam melaksanakan suatu perintah.
Tabel 2 . Hasil pengujian kompleksitas waktu algoritma Prim menggunakan komputer spesifikasi 1
Tabel 3 . Hasil pengujian kompleksitas waktu algoritma Prim menggunakan komputer spesifikasi 2 Program-program yang
dibangun/dihasilkan  pada  penelitian  ini
terbukti mampu mengaplikasikan algoritma Prim  dan  mendapatkan  waktu  komputasi (kompleksitas  waktu)  yang  digunakan untuk  menghitung  kemampuan  komputer dalam  melaksanakan  perintah.  Program- program  tersebut  juga  mampu  secara  tepat menampilkan  pohon  merentang  minimum, yang merupakan hasil dari mengaplikasikan algoritma Prim. Hasil dari program-program tersebut dalam mengaplikasikan  algoritma  Prim  dapat dilihat pada tabel di bawah ini. Tabel 4 . Hasil dari program dalam mengaplikasikan algoritma Prim No. Model Graf Berbobot Hasil Pohon Merentang Minimum Dengan Menggunakan
Algoritma Prim 1. n = 5, m = 8
2. n = 10, m = 20
3. n = 20, m = 49
4. n = 30, m = 80
5. n = 40, m = 104
6. n = 50, m = 130
7. n = 60, m =163
8. n = 70, m = 192
9. n = 80, m = 228

## A.   Hasil  Pengujian  Kompleksitas  Waktu
Algoritma Prim
Algoritma  Prim  menentukan  suatu pohon  merentang  minimum  di  dalam  graf yang  terhubung  dan  berbobot  dengan  n titik/simpul (jumlah data masukan).
Selanjutnya  akan  diuji  kompleksitas  waktu dari  algoritma  Prim  dengan  tujuan  untuk mengetahui efisiensi dari algoritma tersebut.  Efisiensi  algoritma  diukur  dari berapa  jumlah  waktu  yang  dibutuhkan untuk  menjalankan  algoritma  tersebut. Algoritma  yang  efisien  yaitu  algoritma yang meminimumkan kebutuhan waktu.
Keakuratan waktu eksekusi algoritma  dapat  diperoleh  dengan  tidak menghitung kebutuhan waktu untuk menampilkan  antarmuka  program,  operasi masukan/keluaran (baca, tulis), dan sebagainya. Jadi, benar-benar yang dihitung  adalah  kebutuhan  waktu  untuk bagian  algoritma  yang  inti  saja  (Munir,
2009:498). Berdasarkan  hasil  yang  diperoleh dari
program-program yang
dibangun/dihasilkan  pada  penelitian  ini untuk  mendapatkan  pohon  merentang minimum  dengan  menggunakan  algoritma Prim  seperti  yang  terlihat  pada  tabel  4  di atas  dan  berdasarkan  langkah-langkah dalam  algoritma  Prim  seperti  yang  telah dijelaskan sebelumnya pada tinjauan pustaka,  maka  kompleksitas  dari  algoritma Prim dapat dibuktikan sebagai berikut:
1. Langkah  1  (inisialisasi)  dari  algoritma Prim  memerlukan  waktu  paling  banyak n  operasi.  Sehingga  kompleksitas  dari langkah ini adalah O(n).
2. Langkah  2,  adalah  langkah  iterasi, memerlukan  paling  banyak  n-1  kali pengujian (sebab satu titik/simpul sembarang telah dipilih pada langkah 2), sehingga  kompleksitas  langkah  ini adalah O(n).
3. Langkah 3 dijalankan tepat n kali. Setiap  kali  menjalankan  langkah  3, menentukan  garis/sisi  dengan  bobot
terkecil dari himpunan titik-titik/simpul- simpul  yang  belum  terhubung  (F)  ke himpunan  titik-titik/simpul-simpul  yang sudah  saling  terhubung  (T),  dengan paling  banyak  n  kali  operasi.  Sehingga langkah  3  ini  memiki  kompleksitas O(n). Setelah  titik/simpul  pada  himpunan  T terbaru ditandai,
perlu untuk memperbaharui  daftar  titik/simpul  pada himpunan  F.  Untuk  tiap  titik/simpul pada himpunan F,
diadakan perbandingan  antara  bobot  dari  sisi terkecil dari titik/simpul pada himpunan F  ke  titik/simpul  pada  himpunan  T,
untuk  menentukan  sisi  dengan  bobot terkecil yang menghubungkan sembarang  titik/simpul  pada  himpunan F  ke  sembarang  titik/simpul  pada himpunan  T.  Proses  pembaharuan tersebut dalam O(n) operasi.
Karena  tidak  ada  satupun  bagian  dari langkah  3  ini  yang  memerlukan  lebih dari  O(n)  operasi,  maka  kompleksitas langkah  3  adalah  O(n),  perlu  diingat bahwa O(n) + O(n) = O(n).
Karena  langkah  3  dilaksanakan  n  kali, maka operasi yang dilakukan adalah:
(n)(O(n)) = O(n 2 ) …………………(1)
Sehingga  kompleksitas  dari  semua langkah  iterasi  (langkah  2  dan  langkah  3) adalah
O(n) + O(n 2 ) = O(n 2 + n) = O(n 2 ) .......(2)
Dari menghitung kompleksitas masing-masing  langkah  di  atas,  diperoleh kompleksitas algoritma Prim adalah: kompleksitas  langkah  1  +  kompleksitas langkah  semua  iterasi  (langkah  2  dan langkah 3) adalah:
f(n) = O(n) + O(n 2 ) = O(n 2 + n) = O(n 2 ) .....................(3)
Sehingga dapat disimpulkan bahwa kompleksitas waktu algoritma Prim bersifat kuadratik.
B.   Hasil  Penerapan  Kompleksitas  Waktu Algoritma  Prim  Untuk  Menghitung Kemampuan Komputer Dalam Melaksanakan Perintah Hasil  penerapan  kompleksitas  waktu algoritma Prim untuk menghitung kemampuan  komputer  spesifikasi  1  dalam melaksanakan  perintah  dapat  dijelaskan sebagai berikut:
1. Diketahui kompleksitas waktu algoritma Prim adalah O(n 2 ).
2. Dari  tabel  hasil  pengujian  (tabel  2) diketahui  bahwa  waktu  komputasi program  yang  dibangun  dengan  Delphi 7  untuk  jumlah  titik/simpul  (n)  =  40 adalah  sebesar  0,282  detik.  Maka  dapat dihitung  kemampuan  komputer  dengan program  yang  dibangun  dengan  Delphi 7  dalam  menjalankan  algoritma  Prim untuk  n  =  40,  mampu  melaksanakan perintah  (langkah)  per  detik  yaitu sebanyak:
= n 2 /waktu komputasi
= 40 2 /0,282 = 1600/0,282
= 5673,76 langkah/detik.
3. Dari  tabel  hasil  pengujian  (tabel  2) diketahui  bahwa  waktu  komputasi program yang dibangun dengan ArcView GIS 3.3 untuk jumlah titik/simpul (n) = 40 adalah sebesar 130 detik. Maka dapat dihitung kemampuan komputer dengan program yang dibangun  dengan  ArcView  GIS  3.3 dalam  menjalankan  algoritma  Prim untuk  n  =  40,  mampu  melaksanakan perintah  (langkah)  per  detik  yaitu sebanyak:
= n 2 /waktu komputasi
= 40 2 /130 = 1600/130
= 12,31 langkah/detik.
4. Dari  tabel  hasil  pengujian  (tabel  2) diketahui  bahwa  waktu  komputasi program  yang  dibangun  dengan  Delphi
7  untuk  jumlah  titik/simpul  (n)  =  40 adalah  sebesar  0,282  detik.  Maka  dapat dihitung kemampuan komputer menjalankan  program  untuk  n  =  40 dengan kecepatan sebesar:
= waktu komputasi/n 2 = 0,282/40 2 = 0,282/1600 = 1,7625 x 10 -4 detik.
5. Dari  tabel  hasil  pengujian  (tabel  2) diketahui  bahwa  waktu  komputasi program yang dibangun dengan
ArcView GIS 3.3 untuk jumlah titik/simpul (n) = 40 adalah sebesar 130 detik. Maka dapat dihitung kemampuan komputer menjalankan program untuk n = 40 dengan kecepatan sebesar: = waktu komputasi/n 2
= 130/40 2 = 130/1600
= 8,125 x 10 -2 detik .
Hasil  penerapan  kompleksitas  waktu algoritma Prim untuk menghitung kemampuan  komputer  spesifikasi  2  dalam melaksanakan  perintah  dapat  dijelaskan sebagai berikut:
1. Diketahui kompleksitas waktu algoritma Prim adalah O(n 2 ).
2. Dari  tabel  hasil  pengujian  (tabel  3) diketahui  bahwa  waktu  komputasi program  yang  dibangun  dengan  Delphi
7  untuk  jumlah  titik/simpul  (n)  =  40 adalah  sebesar  0,329  detik.  Maka  dapat dihitung  kemampuan  komputer  dengan program  yang  dibangun  dengan  Delphi 7  dalam  menjalankan  algoritma  Prim untuk  n  =  40,  mampu  melaksanakan perintah  (langkah)  per  detik  yaitu sebanyak:
= n 2 /waktu komputasi
= 40 2 /0,329 = 1600/0,329
= 4863,22 langkah/detik.
3. Dari  tabel  hasil  pengujian  (tabel  3) diketahui  bahwa  waktu  komputasi program yang dibangun dengan ArcView GIS 3.3 untuk jumlah
titik/simpul (n) = 40 adalah sebesar 411 detik. Maka dapat dihitung kemampuan komputer dengan program yang dibangun  dengan  ArcView  GIS  3.3 dalam  menjalankan  algoritma  Prim untuk  n  =  40,  mampu  melaksanakan
perintah  (langkah)  per  detik  yaitu sebanyak:
= n 2 /waktu komputasi = 40 2 /411 = 1600/411 = 3,89 langkah/detik. 4. Dari  tabel  hasil  pengujian  (tabel  3) diketahui  bahwa  waktu  komputasi program  yang  dibangun  dengan  Delphi 7  untuk  jumlah  titik/simpul  (n)  =  40 adalah  sebesar  0,329  detik.  Maka  dapat dihitung kemampuan komputer menjalankan  program  untuk  n  =  40 dengan kecepatan sebesar:
= waktu komputasi/n 2 = 0,329/40 2 = 0,329/1600 = 2,05625 x 10 -4 detik.
5. Dari  tabel  hasil  pengujian  (tabel  3) diketahui  bahwa  waktu  komputasi program yang dibangun dengan ArcView GIS 3.3 untuk jumlah titik/simpul (n) = 40 adalah sebesar 411 detik. Maka dapat dihitung kemampuan komputer menjalankan program untuk n = 40 dengan kecepatan sebesar: = waktu komputasi/n 2 = 411/40 2 = 411/1600 = 2,56875 x 10 -1 detik.

## V. KESIMPULAN DAN SARAN

## A.  Kesimpulan
Setelah dilakukan serangkaian pengujian dan perhitungan dalam penelitian ini, maka dapat diambil kesimpulan sebagai berikut:
1. Program-program yang dibangun/dihasilkan  pada  penelitian  ini dengan menggunakan
bahasa pemrograman  Delphi  7  dan  program ArcView  GIS  3.3,  terbukti  mampu mengaplikasikan  algoritma  Prim  dan mendapatkan  kompleksitas  waktunya yang  digunakan  untuk  menghitung kemampuan komputer dalam melaksanakan perintah. Program- program  tersebut  juga  mampu  secara tepat  menampilkan  pohon  merentang minimum,    yang  merupakan  hasil  dari mengaplikasikannya  algoritma  Prim. Kemampuan  komputer  yang  diteliti
dalam  penelitian  ini  adalah  ketepatan dan  kecepatan  dalam  melaksanakan perintah.
2. Hasil  pengujian  membuktikan  bahwa waktu komputasi program yang dibangun  dengan  Delphi  7  lebih  cepat dibandingkan  dengan  waktu  komputasi program yang dibangun dengan ArcView GIS 3.3. Hal ini mengindikasikan  bahwa  program  yang dibangun  dengan  Delphi  7  lebih  efisien daripada program yang dibangun dengan  ArcView  GIS  3.3  dalam mengaplikasikan algoritma Prim.
3. Dari  hasil  perhitungan,  terbukti  dengan jelas  bahwa  kemampuan  komputer spesifikasi  1  lebih  tinggi  daripada kemampuan  komputer  spesifikasi  2 dalam  mengaplikasikan  algoritma  Prim. Hal  ini  terbukti  pada  saat  komputer spesifikasi 1 menjalankan program yang dibangun dengan Delphi 7 untuk jumlah titik/simpul (n) = 40, mampu melaksanakan  perintah  sebesar  5673,76
langkah/detik, sedangkan komputer spesifikasi
2 hanya mampu
melaksanakan  perintah  sebesar  4863,22 langkah/detik.  Pada  saat  menjalankan program yang dibangun dengan ArcView GIS 3.3 untuk jumlah titik/simpul (n) = 40, komputer spesifikasi  1  mampu  melaksanakan perintah  sebesar  12,31  langkah/detik, sedangkan komputer spesifikasi 2 hanya mampu  melaksanakan  perintah  sebesar 3,89 langkah/detik.
4. Dari  hasil  perhitungan,  terbukti  juga dengan jelas bahwa kecepatan komputer spesifikasi  1  lebih  tinggi  daripada kecepatan komputer spesifikasi 2 dalam mengaplikasikan  algoritma  Prim.  Hal ini terbukti pada saat komputer spesifikasi 1 menjalankan program yang dibangun dengan Delphi 7 untuk jumlah titik/simpul (n) = 40, mampu menjalankan program dengan kecepatan sebesar  1,7625  x  10 -4 detik,  sedangkan komputer  spesifikasi  2  hanya  mampu menjalankan program dengan kecepatan sebesar  2,05625  x  10 -4 detik.  Pada  saat menjalankan  program  yang  dibangun dengan  ArcView  GIS  3.3  untuk  jumlah
titik/simpul (n) = 40, komputer spesifikasi  1 mampu menjalankan program  dengan  kecepatan  sebesar
8,125 x 10 -2 detik, sedangkan komputer spesifikasi 2 hanya mampu menjalankan program  dengan  kecepatan  sebesar 2,56875 x 10 -1 detik.
B.   Saran
Saran  yang  dapat  diberikan  dalam penelitian ini adalah sebagai berikut:
1. Pengujian  kemampuan  komputer  dalam melaksanakan perintah dapat menggunakan algoritma-algoritma lainnya  seperti  algoritma  Borůvka, algoritma Kruskal, algoritma Sollin, dan lain-lain. 2. Pengujian  kemampuan  komputer  dalam melaksanakan  perintah,  juga  dapat menggunakan komputer dengan spesifikasi  lainnya  untuk  mendapatkan keakuratan  dan  keanekaragaman  hasil pengujian mengenai kemampuan komputer.

## DAFTAR PUSTAKA
Indriati, D. 2000. Minimum Spanning Tree Pada  Graf  Monge, Tesis  Program Studi Matematika , Universitas Gadjah Mada, Yogyakarta.
Malik,  J.  J.  2006. Kumpulan  Latihan Pemrograman Delphi , Andi, 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.
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, diakses: 19 Maret 2010.
Prahasta,  E.  2009. Sistem  Informasi Geografis: Tutorial ArcView ,
Informatika, Bandung.
Purnama,  H.  2012.  Pengantar  Teknologi
Informasi,
http://www.scribd.com/doc/8191909
9/4/Kemampuan-Komputer ,  diakses:
24 Agustus 2012.
Purwanto,  E.  B.  2008. Perancangan  dan Analisis  Algoritma ,  Edisi  1,  Graha Ilmu, Yogyakarta.
Sudarmawan,  Ariyus,  D.  2007. Interaksi
Manusia dan Komputer , Andi, Yogyakarta
Zakaria,  T.  M.,  Prijono,  A.  2006. Konsep Dan  Implementasi  Struktur  Data , Informatika, Bandung.