La complessità del modulo nel ciclo annidato

Question

La complessità del modulo nel ciclo annidato

#1 da (2 voti)
#2 da (0 voti)

1

ho il seguente codice:

for ( int i = 1; i < n; i ++)
    for ( int j = 0; j < n*n; j ++)
        if (j % i == 0)
           for (int k = 0; k < j; k++)
               sum++;

In che modo if (j % i == 0) influisce sulla complessità complessiva? Mentre k sale a j, che è n*n , anche il terzo ciclo dovrebbe essere di complessità n*n = O (n ^ 2), giusto? Quindi sarebbe O(N)*(N^2)*(N^2)= O(n^5) ? Ma la soluzione data è O(n^4) , quindi dove sbaglio? Grazie!

Ho familiarità con i concetti di base di BigOh, ma non sto capendo questo caso specifico, come i miei calcoli per la somma dei cicli annidati (con il primo che ripete il secondo n volte e il secondo che ripete il terzo n ^ 2 volte e il terzo n ^ 2 riassumerebbe anche n ^ 5) differisce da quello che so che è (n ^ 4). Quindi deve essere qualcosa su if (j % i == 0) che riduce l'esponente di uno. Poiché j è in media più grande di me, ci dovrebbe essere una buona possibilità che il if (j % i == 0) sia soddisfatto. Ma perché diminuisce esattamente l'esponente della complessità complessiva di uno? Ho cercato su Google in SE, ma non ho trovato alcuna informazione su un modulo integrato in un ciclo annidato come questo. Grazie in anticipo.

complexity

posta Don_M 29.03.2016 - 18:32

fonte

2 risposte

Leggi altre domande sui tag complexity

Come memorizzare i dati di stato quando i dati sono correlati a un'altra entità? Va bene costruire artefatti specifici per l'ambiente?

score 2 · Answer 1

Dato un ciclo

for i from 0 to n exclusive:
  if i is divisible by a:
    f(i)

possiamo vedere che f(i) verrà eseguito n/a volte (per essere precisi: 1 + floor((n-1)/a) for n > 0 volte). Il tempo di esecuzione per questa sottoespressione sarebbe quindi T(n) = &Sum;_{i=0...(n-1)/a} F(a·i) . Nel tuo caso specifico, il mio a non è una costante e pertanto annullerà un n .

score 0 · Answer 2

Questa non è in realtà una risposta alla tua domanda esatta; più come un modo alternativo di andare alle cose. Se non hai bisogno di una risposta teoricamente corretta e vuoi solo sapere se il tuo codice funzionerà abbastanza bene per dimensioni di input più grandi, c'è un modo semplice per determinare empiricamente la risposta a domande del genere. Soprattutto se non riesci a capire i limiti teorici e hai già la struttura di base del codice in atto.

Aggiungi una variabile contatore al ciclo più interno. Fondamentalmente, ne hai già uno (somma). Esegui il tuo codice per alcune dimensioni diverse di n, ad esempio per n = 100, 1000, 1e4, 1e5, 1e6 ecc. E guarda come cresce il tuo contatore. Utilizzare passaggi a grana fine se il tempo di esecuzione per valori maggiori di n cresce proibitivo. È possibile rappresentare graficamente i dati risultanti utilizzando un foglio di calcolo e avere un'idea di quanto il grafico assomigli alle funzioni di complessità temporale standard.

Quando i loop e la logica di branching diventano più complicati, spesso è il modo più rapido per avere un'idea di come si comporterà effettivamente il codice. Se aggiungi due contatori, uno all'interno del ramo e uno all'esterno, puoi anche avere un'idea di quante volte il ramo non è stato preso.

Questo aiuta anche a convalidare le risposte arrivate ragionando sulla complessità del tempo in modo più formale.