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

Nie rozumiem, jak kiedy j = i, 2i, 3i ... ostatnia forpętla działa n razy. Chyba po prostu nie rozumiem, jak doszliśmy do tego wniosku na podstawie tego ifoświadczenia.

Edycja: Wiem, jak obliczyć złożoność dla wszystkich pętli, z wyjątkiem tego, dlaczego ostatnia pętla wykonuje czasy i w oparciu o operator mod ... Po prostu nie rozumiem, jak to jest. Zasadniczo, dlaczego j% nie mogę przejść do i * i zamiast ja?

Oznaczmy pętle A, B i 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++;
            }
        }
    }
}

• Pętla A iteruje O ( n ) razy.
• Pętla B iteracje O ( : i ² ) razy od iteracji . Dla każdej z tych iteracji:
  • j % i == 0 jest obliczany, co zajmuje czas O (1).
  • Na 1 / i tych iteracji pętla C iteruje j razy, wykonując pracę O (1) na iterację. Ponieważ j wynosi średnio O ( i ² ), i jest to wykonywane tylko dla iteracji 1 / i pętli B, średni koszt wynosi O ( i ²  /  i ) = O ( i ).

Mnożąc to wszystko razem, otrzymujemy O ( n  ×  i ²  × (1 +  i )) = O ( n  ×  i ³ ). Ponieważ i wynosi średnio O ( n ), jest to O ( n ⁴ ).

Problem polega na tym, że ifwarunek jest spełniony tylko 1 / i czasu:

Zasadniczo, dlaczego j% nie mogę przejść do i * i zamiast ja?

W rzeczywistości, jnie idź do j < i * i, nie tylko do j < i. Ale warunek j % i == 0jest spełniony tylko wtedy, gdy jjest wielokrotnością i.

Wielokrotności iw przedziale są i, 2*i, 3*i, ..., (i-1) * i. Są i - 1takie, więc i - 1czasy pętli C są osiągane pomimo i * i - 1czasów iteracji w pętli B.

• Pierwsza pętla zużywa niteracje.
• Druga pętla zużywa n*niteracje. Wyobraź sobie wtedy i=n, kiedy j=n*n.
• Trzecia pętla zużywa niteracje, ponieważ jest wykonywana tylko irazy, gdzie ijest ograniczona nw najgorszym przypadku.

Zatem 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 ograniczenie wykonania wewnętrznej pętli k było wystarczające, aby zmniejszyć rzeczywistą złożoność poniżej. O(n⁴).Napisałem więc:

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

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

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

To pokazuje, że faktyczna względna różnica między faktyczną n⁴a złożonością tego segmentu kodu jest czynnikiem asymptotycznym względem wartości wokół 0.124...(faktycznie 0,125). Chociaż nie daje nam to dokładnej wartości, możemy wywnioskować, co następuje:

Złożoność czasu jest n⁴/8 ~ f(n)tam, gdzie fjest twoja funkcja / metoda.

• Strona Wikipedii na temat notacji Big O stwierdza w tabelach „Rodzina notacji Bachmanna – Landaua”, że ~granica dwóch stron operandu jest równa. Lub:

  f jest równe g asymptotycznie

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

Użytkownik kaya3 zorientował się, co następuje:

Nawiasem mówiąc, stała asymptotyczna wynosi dokładnie 1/8 = 0,125; Oto dokładna formuła za pośrednictwem Wolfram Alpha .

Usuń ifi modulo bez zmiany złożoności

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 ifi modulo, możesz po prostu je refaktoryzować, jskacząc bezpośrednio z ido 2*ina 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 łatwiej obliczyć złożoność, możesz wprowadzić j2zmienną pośrednią , 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ć debugowania lub starej szkoły System.out.println, aby sprawdzić, czy i, j, ktryplet jest zawsze taki sam w każdej metodzie.

Forma zamknięta

Jak wspomnieli 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 skorzystasz z 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 ma takiej samej złożoności jak oryginalny kod, ale zwraca te same wartości.

Jeśli google pierwsze warunki, można zauważyć, że 0 0 0 2 11 35 85 175 322 546 870 1320 1925 2717 3731pojawiają się w „liczb Stirlinga pierwszego rodzaju: s (n + 2, n).” , z 0dodanymi dwoma s na początku. Oznacza to, że sumjest to liczba Stirlinga pierwszego rodzaju s(n, n-2) .

Rzućmy okiem na pierwsze dwie pętle.

Pierwszy jest prosty, zapętla się od 1 do n. Drugi jest bardziej interesujący. Zaczyna się od 1 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 i and j loopspołączone mają 1^2 + 2^2 + 3^2.
Istnieje wzór na sumę pierwszych n kwadratów n * (n+1) * (2n + 1) / 6, która jest z grubsza O(n^3).

Masz ostatnią, k loopktóra zapętla się od 0 do jwtedy i tylko wtedy j % i == 0. Ponieważ jtrwa od 1 do i^2, j % i == 0jest prawdziwe dla iczasów. Ponieważ i loopiteracja się kończy n, masz jeden dodatkowy O(n).

Więc masz O(n^3)z i and j loopsi inny O(n)z k loopw sumieO(n^4)