Big-O untuk loop bersarang

Saya membaca posting ini di Big-O
Dikatakan bahwa kode berikut adalah O (n ^ 2):

bool ContainsDuplicates(String[] strings)
{
    for(int i = 0; i < strings.Length; i++)
    {
        for(int j = 0; j < strings.Length; j++)
        {
            if(i == j) // Don't compare with self
            {
                continue;
            }

            if(strings[i] == strings[j])
            {
                return true;
            }
        }
    }
    return false;
}

Tapi saya tidak bisa mengerti kenapa.
Lingkaran dalam melakukan sesuatu yang konstan.
Jadi ini adalah penjumlahan dari 1 .... N dari sebuah konstanta. yaitu angka konstan O (1).
Lingkaran luar adalah penjumlahan dari O (1).
Jadi saya akan membayangkan itu adalah n * O (1).

Saya pikir saya salah paham sesuatu di sini.
Saya tidak berpikir bahwa semua loop bersarang berarti O (n ^ 2), kan?

Kesalahan Anda adalah dengan lingkaran dalam. Ia melakukan sesuatu yang konstan n kali, jadi itu adalah O ( n ). Loop luar melakukan loop dalam n kali, jadi itu adalah O ( n × n ), atau O ( n ²  ).

Secara umum, jika jumlah iterasi yang dibuat loop tergantung pada ukuran input, itu adalah O ( n ). Dan jika k loop tersebut bersarang, itu adalah O ( n ^k  ).

Jika panjang string adalah n, tes jika i == jakan dieksekusi n ^ 2 kali. Urutan suatu algoritma adalah urutan bagian mana pun yang memiliki urutan tertinggi. Karena 'i' dibandingkan dengan 'j' n ^ 2 kali, urutan algoritma tidak mungkin kurang dari O(n^2).

Untuk 'n' yang sangat besar, menggandakan 'n' akan empat kali lipat waktu berjalan.

Anda salah mengartikan arti operasi konstan.

Operasi konstan adalah operasi yang selalu dijalankan dalam jumlah waktu yang tetap tanpa bergantung pada input yang diterimanya.

i == j adalah operasi konstan karena mengeksekusi pernyataan ini dalam jumlah waktu yang tetap. Katakanlah dibutuhkan 1 unit waktu.

Tetapi operasi konstan ini dilakukan (tidak ada nilai i) * (tidak ada nilai j) kali. Katakanlah saya dan j dijalankan masing-masing 10 kali. Kemudian dengan perhitungan dibutuhkan 100 unit waktu untuk menyelesaikan i == j ketika dalam loop bersarang. Jadi itu akan bervariasi karena nilai i dan j bervariasi.

Kita dapat yakin bahwa i == j akan dilakukan dalam 1 unit waktu tetapi kita tidak tahu berapa kali i == j akan dilakukan.

Jika dilakukan n kali maka akan membutuhkan n unit waktu. Loop luar mengeksekusi loop dalam sebanyak n kali. Jadi pada dasarnya operasi i == j dilakukan n ^ 2 kali.

Semua loop bersarang berarti O (n ^ (tidak ada loop bersarang)). Di sini O berarti batas atas yang berarti kode akan dieksekusi kurang dari atau sama dengan nilai O (). Ini adalah jaminan bahwa itu tidak akan lebih lama dari itu tetapi bisa memakan waktu lebih sedikit tidak lebih besar.

Loop bersarang menjalankan O ( i ₁ * i ₂ * ... * i _n ), di mana n adalah jumlah loop bersarang dan i _x adalah jumlah iterasi dalam loop x . (Atau, dengan kata lain, itu adalah produk dari jumlah iterasi di masing-masing loop.)

Sepasang loop Anda mengulangi array yang sama dua kali, yang secara kebetulan adalah O (n * n) atau O (n ² ).

Apa yang terjadi di dalam loop paling dalam diperlakukan sebagai konstan karena itu akan terjadi setiap saat. Notasi O-besar tidak benar-benar mengukur kinerja kode linier, ini lebih tentang membuat perbandingan relatif tentang bagaimana algoritma iteratif berperilaku ketika diberi n item input untuk ditangani. Operasi tertentu yang tidak benar-benar melakukan iterasi (seperti push atau pop pada stack) menjadi seperti O (1) karena mereka menangani satu elemen data.