Percobaan Kompleksitas Waktu Algoritma Akar Kuadrat n

Percobaan Kompleksitas Waktu Algoritma Akar Kuadrat n

Posted by Clevo

Tuesday, September 17, 2019

Java Percobaan

Selamat malam, kali ini saya akan membagikan mengenai contoh real analisis algoritma dalam komputer. Untuk mengetahui kompleksitas dari algoritma dapat dilakukan dengan cara menghitung secara manual diatas kertas.

Untuk sekarang ini saya akan mencoba melakukan perhitungan dari kompleksitas akar n. Dengan mengambil waktu lama pemrosesannya kita dapat membandingkannya dengan teori yang kita gunakan.

Pertama kita harus menyiapkan program yang melakukan algoritma akar n. Berikut contoh program dari menghitung akar n

	private void akar(Double n){
	while(i < sqrt(n)) {
	t = 100;
	i++;
	}
	}

view raw akar_n.java hosted with ❤ by GitHub

Program lengkap dari percobaan menentukan kompleksitas algoritma ini saya menggunakan bahasa pemrograman java. Berikut program yang akan saya gunakan untuk menentukan waktu dari program dengan kompleksitas akar n.

	import static java.lang.Math.sqrt;
	public class Kompleksitas {
	public int t = 100, i = 0;
	public Kompleksitas(Double n) {
	long start = System.currentTimeMillis();
	akar(n);
	long end = System.currentTimeMillis();
	System.out.println("Kompleksitas akar n dari " + n + ": " + (end - start) + " ms");
	}
	private void akar(Double n){
	while(i < sqrt(n)) {
	t = 100;
	i++;
	}
	}
	public static void main(String[] args) {
	new Kompleksitas(10000000000000000.0); // 10.000.000 bilion
	new Kompleksitas(20000000000000000.0); // 20.000.000 bilion
	new Kompleksitas(30000000000000000.0); // 30.000.000 bilion
	new Kompleksitas(40000000000000000.0); // 40.000.000 bilion
	new Kompleksitas(50000000000000000.0); // 50.000.000 bilion
	new Kompleksitas(60000000000000000.0); // 60.000.000 bilion
	new Kompleksitas(70000000000000000.0); // 70.000.000 bilion
	new Kompleksitas(80000000000000000.0); // 80.000.000 bilion
	new Kompleksitas(90000000000000000.0); // 90.000.000 bilion
	new Kompleksitas(100000000000000000.0); // 100.000.000 bilion
	new Kompleksitas(200000000000000000.0); // 200.000.000 bilion
	new Kompleksitas(300000000000000000.0); // 300.000.000 bilion
	new Kompleksitas(400000000000000000.0); // 400.000.000 bilion
	new Kompleksitas(1000000000000000000.0); // 1.000.000.000 bilion
	new Kompleksitas(2000000000000000000.0); // 2.000.000.000 bilion
	new Kompleksitas(3000000000000000000.0); // 1.000.000.000 bilion
	}
	}

view raw kompleksitas_akar_n.java hosted with ❤ by GitHub

Cobalah untuk melakukan running di komputer yang saudara gunakan. Setelah saya run saya mendapatkan waktu pemrosesan seperti tabel dibawah ini:


Banyak data atau n adalah banyak dari n yang dicobakan dalam program. Time menggunakan format milisecond karena dalam percobaan 10^17 hasilnya kurang dari 1 detik. Dengan menggunakan milisecond juga membuat waktu lebih mendekati kenyataan.

Saya melakukan percobaan 3 kali. Dengan menggunakan rata-rata dari 3 kali percobaan diharapkan akan mendekati grafik akar n yang sesuai dengan teori kita.

Saya juga melakukan perbandingan dengan cara mengakar n bilangan banyak data kemudian membaginya dengan  akar n bilangan banyak data kemudian. Kemudian pada percobaan juga dilakukan perbandingan yang sama tetapi tidak menggunakan akar. Dengan melakukan hal tersebut jika selisih Teori dan praktek mendekati 1 maka teori kompleksitas yang kita lakukan benar.

          (akar (baris))/(akar (baris+1)) ~ (baris)/(baris + 1)

Keterangan: ~ artinya mendekati.

Dalam tabel dapat kita lihat selisih dari teori dan percobaan yang kita lakukan. Karena akar n hampir sama dengan percobaan maka program diatas memiliki kompleksitas akar n.

Lalu bagaimana grafiknya? Kita akan menggambar dari grafik dengan menggunakan teori terlebih dahulu.

Setelah mengetahui grafik dari akar n, Bagaimana dengan grafik percobaan yang kita lakukan.

Bentuk grafik sama, meskipun y axis dari grafik berbeda. Ini menandakan bahwa program yang kita buat diatas memiliki kompleksitas akar n.

Dengan melakukan percobaan semacam ini kita bisa mengira ira kompleksitas yang kita dapatkan. Apabila kita sulit untuk menentukan kompleksitas menggunakan teori. Contohnya apabila memiliki program yang belum tahu kompleksiitasnya, anda diminta untuk menentukannya. Namun program tersebut sangan sulit untuk ditentukan. Anda dapat mencoba membandingkan komplekistas dari n sampai eksponen n.

Namun cara seperti ini tidak disarankan karena kita melakukan cocokologi. Dengan membandingkan selisihnya.

Ditulis Clevo Pada September 17, 2019 Komentar