Oznaczmy pętle A, B i C:

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

- Pętla A iteruje O(*n*) razy.
- Pętla B iteruje O(*i*<sup>2</sup>) razy **na każdą iterację A**. Dla każdej z tych iteracji:
    - `j % i == 0` jest oceniane, co zajmuje O(1) czasu.
    - Na 1/*i* z tych iteracji, pętla C iteruje *j* razy, wykonując O(1) pracy na iterację. Ponieważ *j* wynosi średnio O(*i*<sup>2</sup>), a jest to wykonywane tylko dla 1/*i* iteracji pętli B, średni koszt wynosi O(*i*<sup>2</sup> / *i*) = O(*i*).

Mnożąc to wszystko razem, otrzymujemy O(*n* × *i*<sup>2</sup> × (1 + *i*)) = O(*n* × *i*<sup>3</sup>). Ponieważ *i* jest średnio O(*n*), to jest O(*n*<sup>4</sup>).

---

Najtrudniejszą częścią tego jest stwierdzenie, że warunek `if` jest prawdziwy tylko 1/*i* czasu:

> Zasadniczo, dlaczego nie może' j % i przejść do i * i, a nie do i?

W rzeczywistości, `j` idzie do `j < i * i`, nie tylko do `j < i`. Ale warunek `j % i == 0` jest prawdziwy wtedy i tylko wtedy, gdy `j` jest wielokrotnością `i`.

Wielokrotnościami `i` w tym zakresie są `i`, `2*i`, `3*i`, ..., `(i-1) * i`. Jest ich `i - 1`, więc pętla C jest osiągana `i - 1` razy, mimo że pętla B iteruje `i * i - 1` razy.

• Pierwsza pętla zużywa n iteracji.
• Druga pętla zużywa n*n iteracji. Wyobraźmy sobie przypadek, gdy i=n, a następnie j=n*n.
• Trzecia pętla zużywa n iteracji, ponieważ jest wykonywana tylko i razy, gdzie i jest ograniczone do n w najgorszym przypadku.

Tak więc złożoność kodu wynosi O(n×n×n×n).

Mam nadzieję, że to pomoże ci zrozumieć.

Wszystkie pozostałe odpowiedzi są poprawne, chcę tylko zmienić następujące. Chciałem zobaczyć, czy redukcja egzekucji wewnętrznej pętli k jest wystarczająca, aby zmniejszyć rzeczywistą złożoność poniżej O(n⁴). Więc napisałem co następuje:

dla (int n = 1; n < 363; ++n) {
    suma wewnętrzna = 0;
    dla(int i = 1; i < n; ++i) {
        dla(int j = 1; j < i * i; ++j) {\i0}
            if(j % i == 0) {\i1}
                dla(int k = 0; k < j; ++k) {
                    suma++;
                }
            }
        }
    }

    long cubic = (długi) Math.pow(n, 3);
    long hypCubic = (długi) Math.pow(n, 4);
    double relative = (podwójny) (suma / (podwójny) hypCubic);
    System.out.println("n = " + n + ": iteracje = " + suma +
            ", n³ = " + sześcienny + ", n⁴ = " + hypCubic + ", rel = " + względny);
}

Po wykonaniu tego, staje się oczywiste, że złożoność jest w rzeczywistości n⁴. Ostatnie linie wyjścia wyglądają tak:

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

Pokazuje to, że rzeczywista względna różnica pomiędzy rzeczywistą n⁴ a złożonością tego segmentu kodu jest czynnikiem asymptotycznym do wartości około 0,124... (właściwie 0,125). Chociaż nie daje nam to dokładnej wartości, możemy wydedukować, co następuje:

Złożoność czasowa jest n⁴/8 ~ f(n) gdzie f jest twoją funkcją/metodą.

• Wikipedia-page w notacji Big O stwierdza w tabelach 'Rodziny notacji Bachmann-Landau', że ~ określa granicę dwóch stron operandu jest równa. Albo:

  f jest równe g asymptotycznie

(Wybrałem 363 jako wyłączoną górną granicę, ponieważ n = 362 jest ostatnią wartością, dla której otrzymujemy sensowny wynik. Następnie przekraczamy przestrzeń długą, a wartość względna staje się ujemna).

Użytkownik kaya3 doszedł do następujących wniosków:

Stała asymptotyczna wynosi dokładnie 1/8 = 0.125, przy okazji; oto dokładna formuła za pośrednictwem Wolframa Alfa.

Przyjrzyjmy się dwóm pierwszym pętlom.

Pierwsza z nich jest prosta, zapętla się od 1 do n. Druga jest bardziej interesująca. Przechodzi od 1 do i podniesionego do kwadratu. Zobaczmy kilka przykładów:

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  

W sumie pętle i i j razem wzięte mają 1^2 + 2^2 + 3^2.
Istnieje wzór na sumę pierwszych n kwadratów, n * (n+1) * (2n + 1) / 6, który jest w przybliżeniu O(n^3).

Masz ostatnią k pętlę, która pętli od 0 do j wtedy i tylko wtedy, gdy j % i == 0. Ponieważ j idzie od 1 do i^2, j % i == 0 jest prawdziwe dla i razy. Ponieważ i loop iteruje nad n, masz jedno dodatkowe O(n).

Więc masz O(n^3) z pętli i oraz j i kolejne O(n) z pętli k dla sumy O(n^4).

Remove `if and modulo without changing the complexity

Oto oryginalna metoda:

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;
}

Jeśli jesteś zdezorientowany przez if i modulo, możesz je po prostu przerobić, z j skokiem bezpośrednio z ido 2*ido 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;
}

Aby jeszcze bardziej ułatwić obliczanie złożoności, można wprowadzić zmienną pośrednią j2, tak aby każda zmienna pętli była zwiększana o 1 przy każdej iteracji:

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;
}

Możesz użyć debuggowania lub old-school System.out.println w celu sprawdzenia, czy i, j, k triplet jest zawsze taki sam w każdej metodzie.

Wyrażenie formy zamkniętej

Jak wspominali inni, możesz użyć faktu, że suma pierwszych n liczb całkowitych jest równa n * (n+1) / 2 (patrz liczby trójkątne). Jeśli użyjesz tego uproszczenia dla każdej pętli, otrzymasz :

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

Oczywiście nie jest to *nie taka sama złożoność jak oryginalny kod, ale zwraca te same wartości.

Jeśli googlujesz pierwsze terminy, możesz zauważyć, że 0 0 0 2 11 35 85 175 322 546 870 1320 1925 2717 3731 pojawiają się w "Stirling numbers of the first kind: s(n+2, n).", z dwoma 0s dodanymi na początku. Oznacza to, że sum to numer mieszadłowy pierwszego rodzaju s(n, n-2).