de-vraag
  • Pytania
  • Tagi
  • Użytkownicy
Powiadomienia
Nagrody
Rejestracja
Po zarejestrowaniu się, będziesz otrzymywać powiadomienia o odpowiedziach i komentarzach do swoich pytań.
Zaloguj się
Brak tłumaczeń pasujących do Twojego wyszukiwania Jeśli masz już konto, zaloguj się, aby sprawdzić nowe powiadomienia.
Za dodane pytania, odpowiedzi i komentarze przewidziane są nagrody.
Więcej
Źródło
Edytuj
 user11452926
user11452926
Question

Dlaczego złożoność obliczeniowa jest O(n^4)?

``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?
33 2020-02-11T07:07:31+00:00 5
Angela Cojocari 17541
Edytowane pytanie 19. września 2021 в 7:33
 user11452926
user11452926
Edytowane pytanie 11. lutego 2020 в 7:43
Programowanie
java
big-o
Popular videos
Czym jest złożoność obliczeniowa?
Czym jest złożoność obliczeniowa?
2 lata temu
Złożoność obliczeniowa - Matura z informatyki w zakresie rozszerzonym
Złożoność obliczeniowa - Matura z informatyki w zakresie rozszerzonym
1 rok temu
Introduction to Big O Notation and Time Complexity (Data Structures &amp; Algorithms #7)
Introduction to Big O Notation and Time Complexity (Data Structures & Algorithms #7)
4 lata temu
Złożoność obliczeniowa - notacja duże O
Złożoność obliczeniowa - notacja duże O
6 miesięcy temu
Złożoność obliczeniowa cz.1
Złożoność obliczeniowa cz.1
4 lata temu
Złożoność obliczeniowa
Złożoność obliczeniowa
1 rok temu
Calculating Time Complexity | New Examples | GeeksforGeeks
Calculating Time Complexity | New Examples | GeeksforGeeks
2 lata temu
Złożoność obliczeniowa: złożoność stała O(1)
Złożoność obliczeniowa: złożoność stała O(1)
4 miesiące temu
Wykład 12, część 4: złożoność czasowa i pamięciowa
Wykład 12, część 4: złożoność czasowa i pamięciowa
1 rok temu
Permutacja losowa: metody generowania, dyskusja zalet i wad, złożoność obliczeniowa i pamięciowa
Permutacja losowa: metody generowania, dyskusja zalet i wad, złożoność obliczeniowa i pamięciowa
4 lata temu
Kurs C++ odc. 14: Sortowanie. Złożoność algorytmów
Kurs C++ odc. 14: Sortowanie. Złożoność algorytmów
8 lat temu
Analiza Algorytmów dla opornych #1
Analiza Algorytmów dla opornych #1
3 lata temu
Algorytmy - Quick sort - Sortowanie szybkie
Algorytmy - Quick sort - Sortowanie szybkie
5 lat temu
Ultrazimny świat: co, jak i dlaczego, Piotr Żuchowski
Ultrazimny świat: co, jak i dlaczego, Piotr Żuchowski
3 lata temu
Omówienie autorskiego zadania &quot;Duplikaty&quot; + złożoność + STL
Omówienie autorskiego zadania "Duplikaty" + złożoność + STL
1 rok temu
Optymalizacja – podstawy złożoności obliczeniowej. Klasy P i NP. Heurystyka, losowy i wyczerpujący.
Optymalizacja – podstawy złożoności obliczeniowej. Klasy P i NP. Heurystyka, losowy i wyczerpujący.
4 lata temu
Analiza algorytmów (cz. 01)
Analiza algorytmów (cz. 01)
2 lata temu
« Poprzedni
Następny »
 kaya3
kaya3
11. lutego 2020 в 7:27
2020-02-11T07:27:19+00:00
Więcej
Źródło
Edytuj
#42395296

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.
Angela Cojocari 17541
Edytowana odpowiedź 19. września 2021 в 7:33
39
0
Mohammed Deifallah
Mohammed Deifallah
11. lutego 2020 в 7:21
2020-02-11T07:21:50+00:00
Więcej
Źródło
Edytuj
#42395294
  • 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ć.

Angela Cojocari 17541
Edytowana odpowiedź 19. września 2021 в 7:33
11
0
 TreffnonX
TreffnonX
11. lutego 2020 в 7:54
2020-02-11T07:54:16+00:00
Więcej
Źródło
Edytuj
#42395297

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.


Angela Cojocari 17541
Edytowana odpowiedź 19. września 2021 в 7:33
3
0
Silviu Burcea
Silviu Burcea
11. lutego 2020 в 7:23
2020-02-11T07:23:59+00:00
Więcej
Źródło
Edytuj
#42395295

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).

Angela Cojocari 17541
Edytowana odpowiedź 19. września 2021 в 7:33
0
0
Eric Duminil
Eric Duminil
12. lutego 2020 в 12:21
2020-02-12T12:21:46+00:00
Więcej
Źródło
Edytuj
#42395298

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).

Angela Cojocari 17541
Edytowana odpowiedź 19. września 2021 в 7:33
Eric Duminil
Eric Duminil
Edytowana odpowiedź 12. lutego 2020 в 12:34
0
0
Dodaj pytanie
Kategorie
Wszystkie
Technologia
Kultura / Rekreacja
Życie / Sztuka
Nauka
Profesjonalny
Biznes
Użytkownicy
Wszystkie
Nowy
Popularny
1
365
Zarejestrowany 1 dzień temu
2
True Image
Zarejestrowany 1 dzień temu
3
archana agarwal
Zarejestrowany 3 dni temu
4
Maxim Zhilyaev
Zarejestrowany 6 dni temu
5
adambotsfford adambotsfford
Zarejestrowany 1 tydzień temu
DE
ES
FR
IT
JA
KO
NL
PL
PT
RU
ZH
© de-vraag 2022
Źródło
stackoverflow.com
na podstawie licencji cc by-sa 3.0 z przypisaniem