int sum = 0;
for(int i = 1; i < n; i++) {
    for(int j = 1; j < i * i; j++) {
        if(j % i == 0) {
            for(int k = 0; k < j; k++) {
                sum++;
            }
        }
    }
}

Saya tidak mengerti bagaimana ketika j = i, 2i, 3i ... forloop terakhir berjalan n kali. Saya kira saya hanya tidak mengerti bagaimana kita sampai pada kesimpulan berdasarkan pada ifpernyataan itu.

Sunting: Saya tahu bagaimana menghitung kompleksitas untuk semua loop kecuali untuk mengapa loop terakhir mengeksekusi i kali berdasarkan operator mod ... Saya hanya tidak melihat bagaimana itu saya. Pada dasarnya, mengapa saya tidak bisa naik ke i * i daripada saya?

Mari beri label loop A, B dan C:

int sum = 0;
// loop A
for(int i = 1; i < n; i++) {
    // loop B
    for(int j = 1; j < i * i; j++) {
        if(j % i == 0) {
            // loop C
            for(int k = 0; k < j; k++) {
                sum++;
            }
        }
    }
}

• Loop A berulang O ( n ) kali.
• Lingkaran B iterates O ( i ² ) kali per iterasi A . Untuk setiap iterasi ini:
  • j % i == 0 dievaluasi, yang membutuhkan O (1) waktu.
  • Pada 1 / i iterasi ini, lingkaran C iterates j kali, melakukan O (1) kerja per iterasi. Karena j adalah rata-rata O ( i ² ), dan ini hanya dilakukan untuk iterasi I / i dari loop B, biaya rata-rata adalah O ( i ²  /  i ) = O ( i ).

Mengalikan semua ini bersama-sama, kita mendapatkan O ( n  ×  i ²  × (1 +  i )) = O ( n  ×  i ³ ). Karena saya adalah rata-rata O ( n ), ini adalah O ( n ⁴ ).

Bagian yang sulit dari ini adalah mengatakan bahwa ifkondisinya hanya benar 1 / i saat itu:

Pada dasarnya, mengapa saya tidak bisa naik ke i * i daripada saya?

Bahkan, jtidak naik ke atas j < i * i, bukan hanya sampai j < i. Tetapi kondisinya j % i == 0benar jika dan hanya jika jmerupakan kelipatan i.

Kelipatan dari idalam rentang yang i, 2*i, 3*i, ..., (i-1) * i. Ada i - 1ini, sehingga loop C tercapai i - 1kali meskipun loop B i * i - 1berulang kali.

• Loop pertama mengkonsumsi niterasi.
• Loop kedua mengkonsumsi n*niterasi. Bayangkan kasusnya kapan i=n, lalu j=n*n.
• Loop ketiga mengkonsumsi niterasi karena hanya dieksekusi iberkali-kali, di mana iterikat npada kasus terburuk.

Dengan demikian, kompleksitas kode adalah O (n × n × n × n).

Saya harap ini membantu Anda mengerti.

Semua jawaban lain benar, saya hanya ingin mengubah yang berikut. Saya ingin melihat, jika pengurangan eksekusi k-loop dalam cukup untuk mengurangi kompleksitas aktual di bawah ini O(n⁴).Jadi saya menulis yang berikut:

for (int n = 1; n < 363; ++n) {
    int sum = 0;
    for(int i = 1; i < n; ++i) {
        for(int j = 1; j < i * i; ++j) {
            if(j % i == 0) {
                for(int k = 0; k < j; ++k) {
                    sum++;
                }
            }
        }
    }

    long cubic = (long) Math.pow(n, 3);
    long hypCubic = (long) Math.pow(n, 4);
    double relative = (double) (sum / (double) hypCubic);
    System.out.println("n = " + n + ": iterations = " + sum +
            ", n³ = " + cubic + ", n⁴ = " + hypCubic + ", rel = " + relative);
}

Setelah melaksanakan ini, menjadi jelas, bahwa kerumitan itu sebenarnya n⁴. Baris terakhir dari output terlihat seperti ini:

n = 356: iterations = 1989000035, n³ = 45118016, n⁴ = 16062013696, rel = 0.12383254507467704
n = 357: iterations = 2011495675, n³ = 45499293, n⁴ = 16243247601, rel = 0.12383580700180696
n = 358: iterations = 2034181597, n³ = 45882712, n⁴ = 16426010896, rel = 0.12383905075183874
n = 359: iterations = 2057058871, n³ = 46268279, n⁴ = 16610312161, rel = 0.12384227647628734
n = 360: iterations = 2080128570, n³ = 46656000, n⁴ = 16796160000, rel = 0.12384548432498857
n = 361: iterations = 2103391770, n³ = 47045881, n⁴ = 16983563041, rel = 0.12384867444612208
n = 362: iterations = 2126849550, n³ = 47437928, n⁴ = 17172529936, rel = 0.1238518469862343

Apa ini menunjukkan, bahwa perbedaan relatif aktual antara aktual n⁴dan kompleksitas segmen kode ini adalah faktor asimtotik terhadap nilai sekitar 0.124...(sebenarnya 0,125). Meskipun tidak memberi kami nilai yang tepat, kami dapat menyimpulkan, berikut ini:

Kompleksitas waktu adalah di n⁴/8 ~ f(n)mana ffungsi / metode Anda.

• Halaman wikipedia pada notasi O Besar menyatakan dalam tabel 'Family of Bachmann-Landau notations' yang ~mendefinisikan batas kedua sisi operan adalah sama. Atau:

  f sama dengan g asimptotik

(Saya memilih 363 sebagai batas atas yang dikecualikan, karena n = 362nilai terakhir yang kami dapatkan hasilnya masuk akal. Setelah itu, kami melampaui ruang panjang dan nilai relatif menjadi negatif.)

Pengguna kaya3 menemukan yang berikut:

Omong kosong asimptotik persis 1/8 = 0,125, omong-omong; inilah rumus yang tepat melalui Wolfram Alpha .

Hapus ifdan modulo tanpa mengubah kompleksitas

Inilah metode aslinya:

public static long f(int n) {
    int sum = 0;
    for (int i = 1; i < n; i++) {
        for (int j = 1; j < i * i; j++) {
            if (j % i == 0) {
                for (int k = 0; k < j; k++) {
                    sum++;
                }
            }
        }
    }
    return sum;
}

Jika Anda bingung dengan ifdan Modulo, Anda hanya bisa refactor mereka pergi, dengan jmelompat langsung dari ike 2*ike 3*i...:

public static long f2(int n) {
    int sum = 0;
    for (int i = 1; i < n; i++) {
        for (int j = i; j < i * i; j = j + i) {
            for (int k = 0; k < j; k++) {
                sum++;
            }
        }
    }
    return sum;
}

Untuk membuatnya lebih mudah untuk menghitung kompleksitas, Anda dapat memperkenalkan j2variabel perantara , sehingga setiap variabel loop bertambah 1 pada setiap iterasi:

public static long f3(int n) {
    int sum = 0;
    for (int i = 1; i < n; i++) {
        for (int j2 = 1; j2 < i; j2++) {
            int j = j2 * i;
            for (int k = 0; k < j; k++) {
                sum++;
            }
        }
    }
    return sum;
}

Anda dapat menggunakan debugging atau old-school System.out.printlnuntuk memeriksa bahwa i, j, ktriplet selalu sama di setiap metode.

Ekspresi bentuk tertutup

Seperti yang disebutkan oleh orang lain, Anda dapat menggunakan fakta bahwa jumlah n bilangan bulat pertama sama dengan n * (n+1) / 2(lihat angka segitiga ). Jika Anda menggunakan penyederhanaan ini untuk setiap loop, Anda mendapatkan:

public static long f4(int n) {
    return (n - 1) * n * (n - 2) * (3 * n - 1) / 24;
}

Jelas bukan kompleksitas yang sama dengan kode asli tetapi mengembalikan nilai yang sama.

Jika Anda menggunakan istilah pertama di Google, Anda dapat melihat yang 0 0 0 2 11 35 85 175 322 546 870 1320 1925 2717 3731muncul di "Angka pengadukan dari jenis pertama: s (n + 2, n)." , dengan dua 0s ditambahkan di awal. Ini berarti itu sumadalah angka Stirling dari jenis pertama s(n, n-2) .

Mari kita lihat dua loop pertama.

Yang pertama sederhana, perulangan dari 1 ke n. Yang kedua lebih menarik. Mulai dari 1 hingga kuadrat. Mari kita lihat beberapa contoh:

e.g. n = 4    
i = 1  
j loops from 1 to 1^2  
i = 2  
j loops from 1 to 2^2  
i = 3  
j loops from 1 to 3^2  

Secara total, i and j loopsgabungan tersebut memiliki 1^2 + 2^2 + 3^2.
Ada rumus untuk jumlah n kotak pertama n * (n+1) * (2n + 1) / 6, yang kira-kira O(n^3).

Anda memiliki yang terakhir k loopdari 0 hingga jjika dan hanya jika j % i == 0. Sejak jberalih dari 1 ke i^2, j % i == 0benar untuk ikali. Sejak i loopiterates berakhir n, Anda memiliki satu ekstra O(n).

Jadi, Anda memiliki O(n^3)dari i and j loopsdan yang lain O(n)dari k loopuntuk totalO(n^4)