Perché la complessità computazionale è O(n^4)?

Question

Altro

Fonte Versione non AMP Modifica

Perché la complessità computazionale è O(n^4)?

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



Non capisco come quando j = i, 2i, 3i... l'ultimo ciclo `for` viene eseguito n volte. Credo di non capire come siamo arrivati a questa conclusione basandoci sulla dichiarazione `if`.

Edit: So come calcolare la complessità per tutti i cicli, tranne che per il motivo per cui l'ultimo ciclo esegue i volte in base all'operatore mod... Non vedo proprio come sia i. In pratica, perché j % i non può arrivare a i * i piuttosto che i?

Angela Cojocari

17541

Domanda modificata 19º settembre 2021 в 7:33

user11452926

Domanda modificata 11º febbraio 2020 в 7:43

Programmazione

java big-o

11º febbraio 2020 в 7:07

11 visualizzazioni

Commenti sulla domanda (10)

kaya3 · Answer 1 · 2020-02-11T07:27:19+00:00

Etichettiamo i cicli A, B e C:

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



- Il loop A itera O(*n*) volte.
- Il loop B itera O(*i*2) volte **per iterazione di A**. Per ognuna di queste iterazioni:
    - `j % i == 0` viene valutato, il che richiede O(1) tempo.
    - Su 1/*i* di queste iterazioni, il ciclo C itera *j* volte, facendo O(1) lavoro per iterazione. Poiché *j* è O(*i*2) in media, e questo viene fatto solo per 1/*i* iterazioni del ciclo B, il costo medio è O(*i*2 / *i*) = O(*i*).

Moltiplicando tutto questo insieme, otteniamo O(*n* × *i*2 × (1 + *i*)) = O(*n* × *i*3). Poiché *i* è in media O(*n*), questo è O(*n*4).

---

La parte difficile di questo è dire che la condizione `if` è vera solo 1/*i* delle volte:

> Fondamentalmente, perché j % i non può'andare fino a i * i piuttosto che i?

In effetti, `j` va fino a `j < i * i`, non solo fino a `j < i`. Ma la condizione `j % i == 0` è vera se e solo se `j` è un multiplo di `i`.

I multipli di `i` nell'intervallo sono `i`, `2*i`, `3*i`, ..., `(i-1) * i`. Ci sono `i - 1` di questi, quindi il ciclo C viene raggiunto `i - 1` volte nonostante il ciclo B iteri `i * i - 1` volte.

Mohammed Deifallah · Answer 2 · 2020-02-11T07:21:50+00:00

Mohammed Deifallah

Fonte Versione non AMP Modifica

Il primo ciclo consuma n iterazioni.
Il secondo ciclo consuma n*n iterazioni. Immaginate il caso in cui i=n, quindi j=n*n.
Il terzo ciclo consuma n iterazioni perché viene eseguito solo i volte, dove i è limitato a n nel caso peggiore.

Quindi, la complessità del codice è O(n×n×n×n).

Spero che questo vi aiuti a capire.

Angela Cojocari

17541

Risposta modificata 19º settembre 2021 в 7:33

11

0

Commentari (0)

TreffnonX · Answer 3 · 2020-02-11T07:54:16+00:00

Tutte le altre risposte sono corrette, voglio solo modificare quanto segue. Volevo vedere se la riduzione delle esecuzioni del k-loop interno era sufficiente a ridurre l'effettiva complessità al di sotto della "O" (n⁴).` Così ho scritto quanto segue:


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

    lungo cubico = (lungo) Math.pow(n, 3);
    lungo ipCubico = (lungo) Math.pow(n, 4);
    doppio parente = (doppio) (somma / (doppio) ipCubico);
    System.out.println("n = " + n + ": iterazioni = " + somma +
            ", n³ = " + cubico + ", n⁴ = " + ipCubico + ", rel = " + relativo);
}
```

Dopo averlo eseguito, diventa ovvio, che la complessità è in realtà `n⁴`. Le ultime linee di output hanno questo aspetto:

``` 
n = 356: iterazioni = 1989000035, n³ = 45118016, n⁴ = 16062013696, rel = 0,12383254507467704
n = 357: iterazioni = 2011495675, n³ = 45499293, n⁴ = 16243247601, rel = 0,12383580700180696
n = 358: iterazioni = 2034181597, n³ = 45882712, n⁴ = 16426010896, rel = 0,12383905075183874
n = 359: iterazioni = 2057058871, n³ = 46268279, n⁴ = 16610312161, rel = 0,12384227647628734
n = 360: iterazioni = 2080128570, n³ = 46656000, n⁴ = 16796160000, rel = 0,1238454848432498857
n = 361: iterazioni = 2103391770, n³ = 47045881, n⁴ = 16983563041, rel = 0,12384867444612208
n = 362: iterazioni = 2126849550, n³ = 47437928, n⁴ = 17172529936, rel = 0,1238518469862343
``` 

Ciò dimostra che l'effettiva differenza relativa tra l'attuale `n⁴` e la complessità di questo segmento di codice è un fattore asintotico verso un valore intorno a `0,124...` ` (in realtà 0,125). Anche se non ci dà il valore esatto, possiamo dedurre quanto segue:

La complessità temporale è `n⁴/8 ~ f(n)` dove `f` è la vostra funzione/metodo.

* La pagina wikipedia sulla notazione Big O afferma nelle tabelle della "Famiglia delle notazioni di Bachmann-Landau" che il `~`` definisce il limite dei due lati dell'operando è uguale. Oppure:
> f è uguale a g asintoticamente 

(Ho scelto 363 come limite superiore escluso, perché `n = 362` è l'ultimo valore per il quale otteniamo un risultato ragionevole. Dopo di che, superiamo il lungo spazio e il valore relativo diventa negativo).

L'utente kaya3 ha capito quanto segue:
> La costante asintotica è esattamente 1/8 = 0.125, tra l'altro; [ecco la formula esatta tramite Wolfram Alpha][1].

  [1]: https://www.wolframalpha.com/input/?i=sum+for+i+%3D+1+to+n-1+of+i+*+i+*+%28i-1%29+%2F+2
***  ***

Silviu Burcea · Answer 4 · 2020-02-11T07:23:59+00:00

Diamo un'occhiata ai primi due cicli.

Il primo è semplice, va da 1 a n. Il secondo è più interessante. Va da 1 a i al quadrato. Vediamo alcuni esempi:

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

In totale, i i e j loop combinati hanno 1^2 + 2^2 + 3^2.
C'è una formula per la somma dei primi n quadrati, n * (n+1) * (2n + 1) / 6, che è circa O(n^3).

Hai un ultimo k loop che va da 0 a j se e solo se j % i == 0. Poiché j va da 1 a i^2, j % i == 0 è vero per i volte. Poiché il i loop itera su n, hai un O(n) in più.

Quindi avete O(n^3)da i e j loop e un altro O(n) dal k loop per un totale di O(n^4)

Eric Duminil · Answer 5 · 2020-02-12T12:21:46+00:00

Rimuovere "se" e modulo senza modificare la complessità

Ecco il metodo originale:

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

Se siete confusi dal "se" e dal modulo, potete semplicemente rifattorizzarli via, con il "j" che salta direttamente da "i" a "2i" a "3i" ... :

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

Per rendere ancora più facile il calcolo della complessità, è possibile introdurre una variabile intermedia j2, in modo che ogni variabile del loop venga incrementata di 1 ad ogni iterazione:

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

È possibile utilizzare il debug o la vecchia scuola System.out.println per verificare che i, j, k tripletta sia sempre la stessa in ogni metodo.

Espressione in forma chiusa

Come detto da altri, si può usare il fatto che la somma dei primi n interi è uguale a n * (n+1) / 2 (vedi numeri triangolari). Se si utilizza questa semplificazione per ogni ciclo, si ottiene :

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

Ovviamente non è non la stessa complessità del codice originale ma restituisce gli stessi valori.

Se cercate su Google i primi termini, potete notare che 0 0 0 0 2 11 35 85 175 322 546 870 1320 1925 2717 3731 appaiono in "numeri di Stirling del primo tipo: s(n+2, n)", con due 0s aggiunti all'inizio. Significa che sum è il numero di Stirling del primo tipo s(n, n-2).