Tentukan Big-O

adniatisiti03

01-10-2019 14:34

Tentukan Big-O

ada yg bsabantu ga?
saya ragu karenaada perintah if di algoritma ini
   for i → 1 to n-1 do
           for j → n down to n-1 do
                if ( A [ j ] > A[ j-1 ] ) then
                       temp → A [ j ]
                       A [ j   ] → A [ j-1 ]
                       A [ j-1 ] → temp
                  end if
            end for
     end for
Tentukan Big-O-nya

nona212 memberi reputasi

629

Kutip

Balasan

Guest

Tulis komentar menarik atau mention replykgpt untuk ngobrol seru

Tampilkan semua post

eternu5

02-10-2019 13:26

Nambahin jawaban yang udah ada, terkait kompleksitas waktu, kasus apa yang mau dicari? Best? Average? Worst? Ketika dihadapkan dengan algoritma yang memiliki percabangan, membatasi kompleksitas waktu pada hanya satu jenis kasus akan sangat mempermudah penghitungan.

Yang membedakan kompleksitas waktu antara best-average-worst case ada di bagian if ( A[ j ] > A[ j-1 ] ) then. Dengan mengasumsikan setiap baris algoritma membutuhkan waktu eksekusi yang konstan, for-loop yang paling dalam memiliki waktu eksekusi:

- Worst case: 4c per perulangan. (1c dari baris if...then, dan 3c dari blok percabangan)
- Best case: 1c per perulangan.

Kompleksitas waktu if ini kemudian digunakan untuk mencari kompleksitas waktu keseluruhan algoritma, baik untuk worst case atau best case.

Spoiler for big o:

Terkait dengan big o notation, big o notation sebetulnya ya itu, notasi. Big o adalah alat ukur. Hubungan kompleksitas waktu dengan notasi big o mirip seperti waktu dengan detik, atau harga dengan rupiah.

Sehingga ketika ditanya "apa notasi big o nya?", barangkali perlu diklarifikasi lebih lanjut: apa yang ingin dicari? Karena pertanyaan tersebut mirip dengan misalnya ketika sedang belanja, kemudian u ditanya "berapa rupiah?" Apakah maksudnya total harga belanjaannya? Atau harga susu yang lagi u pegang?

adniatisiti03 memberi reputasi

Kutip

Balas

Tutup