``java 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++) { for(int k = 0; k < j; k++) { sum++; } } } }
Nie rozumiem jak w przypadku gdy j = i, 2i, 3i... ostatnia pętla `for` jest wykonywana n razy. Chyba po prostu nie rozumiem, jak doszliśmy do tego wniosku na podstawie instrukcji `if`.
Edit: Wiem jak obliczyć złożoność dla wszystkich pętli z wyjątkiem tego, dlaczego ostatnia pętla wykonuje się i razy na podstawie operatora mod... Po prostu nie widzę, jak to'jest i. Zasadniczo, dlaczego nie może'j % i przejść do i * i, a nie i?
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.
n
iteracji.n*n
iteracji. Wyobraźmy sobie przypadek, gdy i=n
, a następnie j=n*n
.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ą.
~
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)
.
if
and modulo without changing the complexityOto 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 i
do 2*i
do 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.
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 0
s dodanymi na początku. Oznacza to, że sum
to numer mieszadłowy pierwszego rodzaju s(n, n-2)
.