Olimpiade Sains Provinsi (OSP) 2010 - Komputer, Nomor 22

Question

Perhatikan potongan algoritma berikut.

for i := 1 to n do 
  for j := 1 to n do 
    XX(i,j);

Misalnya XX(i,j) dijalankan dengan harga berapapun bersifat konstan, dan potongan algoritma itu dengan harga n = 100, diperlukan waktu rata-rata 1 detik kira-kira berapa detik potongan algoritma ini dijalankan untuk nilai n = 2000?

Christian E. C. · Accepted Answer

(2000/100)^2 x 1 = 20^2 = 400 detik//

Sensei Puat · Answer

Lihat bahwa kompleksitas program tsb adalah O(N²), karena ada 2 for yang tujuan hitungnya sama, yaitu N, sehingga untuk penghitungan waktu yg diperlukan, akan berbanding lurus dengan kuadraf nilai N

Sehingga waktu yg diperlukan adalah 2000 x 1/100 = 20 hasilnya dikuadratkan, jadi 400

Kurang lebih caranya sama dgn komentar diatas

//CMIIW

Roy Tarigan · Answer

bisa ngk ya klok gni... Dik; n1= 100 n2=2000 t1=1 dit; t2...? n1^2/n2^2=t1/t2-- 100^2/2000=2*1/t2 -- 10000/4000000=1/t2 -- 4000000=10000t2 t2=4000000/10000 = 400

Olimpiade Sains Provinsi (OSP) 2010 - Komputer, Nomor 22

3 jawaban