Apakah kode berikut dianggap O(1) atau O(n)? Loop for memiliki kompleksitas konstan yang berjalan 10 kali tetapi saya tidak yakin apakah kondisi if akan dianggap O(n) atau O(1). untuk (i = 0; saya &...

2
rollo123 5 April 2021, 21:04

1 menjawab

Jawaban Terbaik

Kompleksitasnya akan menjadi O(1), karena terlepas dari seberapa banyak Anda meningkatkan input, kompleksitas algoritme tetap konstan. Yaitu, operasi yang dilakukan di dalam loop itu dianggap memiliki waktu yang konstan, maka O(1).

for (i = 0; i < 10; i++)
{
    if (arr [i] == 1001) 
    {
        return i;
    }
}

Di sisi lain jika loop Anda adalah:

for (i = 0; i < 10; i++)
{
    f(n)
}

Dan fungsi f(n) memiliki kompleksitas O(n) maka kompleksitas seluruh potongan kode akan menjadi O(n) karena 10 * N dapat diberi label sebagai O(n).

Untuk penjelasan yang lebih mendalam, lihat Apa itu penjelasan bahasa Inggris sederhana tentang notasi “Big O”?

1
dreamcrash 5 April 2021, 18:22