Complessità nei cicli nidificati

Question

Complessità nei cicli nidificati

#1 da (10 voti)
#2 da (7 voti)
#3 da (2 voti)
#4 da (0 voti)

2

Premessa:

In questo post creerò la confusione comune tra O(n) e Theta(n) come notazioni di complessità.
Scriverò pseudo-codice per parlare di algoritmi, usando qualsiasi notazione che trovo di mio gradimento.

Lo so, ancora un'altra domanda su cicli annidati e complessità.

Recentemente ho scritto un algoritmo annidato, che funzionerebbe come collo di bottiglia di un'applicazione più complessa. In qualche modo sembrava questo:

while(firstLoopRunning) {
    foreach(element in myArray) {
        doSomeAction(element);
    }
}

Il mio acuto occhio mi ha portato alla conclusione che, come doSomeAction è in O(1) , l'algoritmo doveva essere in O(n²) .

So comunque che i cicli annidati possono avere una complessità diversa. Ad esempio quanto segue è in O(n.log(n)) :

for(i in 0..n) // n is constant in this loop
    for(j in 0..i) // j goes up to i and not to a constant
        print(j);

Poi ho pensato, hey, so che myArray ha una lunghezza massima. In questo caso specifico, conosco in base alla progettazione che non ci saranno mai più di 8 elementi in myArray, quindi l'algoritmo potrebbe assomigliare a questo:

while(firstLoopRunning) {
    // Let's do this one in Java, myArray would actually be an ArrayList
    try {
        doSomeAction(myArray.get(0));
        doSomeAction(myArray.get(1));
        doSomeAction(myArray.get(2));
        doSomeAction(myArray.get(3));
        doSomeAction(myArray.get(4));
        doSomeAction(myArray.get(5));
        doSomeAction(myArray.get(6));
        doSomeAction(myArray.get(7));
    } catch(ArrayOutOfBoundsException ex) {
       // Just a lazy way for me to avoid checking if the index exists
    }
}

E voilà! Eccolo in O(n) !

Inoltre, so per certo che i compilatori di solito trasformano i loop falso come questo:

for(i in 0..8) // not really a loop
    someCall(i);

in una sequenza di chiamate.

Che mi ha portato a una prima conclusione:

A iteration over an array which length will have a known finite upper-bound is in O(1).

Penso di aver ragione su questo (aka: correggimi se sbaglio)

D'altro canto, stiamo lavorando con dati finiti e l'intero punto della teoria della complessità è di lavorare su dati teoricamente infiniti.

Quindi usiamo un altro esempio classico: stiamo iterando sui quadrati di una griglia (= ~ array bidimensionale), quindi chiaramente un algoritmo O(n²) . E se invece dovessimo mettere tutti i quadrati in una singola lista e cambiare questo:

// O(n²) algorithm over myGrid[][]
for(i in myGrid)
    for(j in myGrid[i])
        yieldAction(myGrid[i][j])

in questo

// O(n) algorithm over myFlatGrid[]
for(i in myFlatGrid)
    yieldAction(myFlatGrid[i mod rowLength][j])

Fondamentalmente la stessa cosa, ma diversa complessità, ma non è stato ancora ottenuto alcun ciclo. Premesso che la griglia può crescere in entrambe le dimensioni, quindi la variabile è davvero quadratica, ma in un certo senso può essere trattata in modo lineare (anche se non ne vale la pena).

Ma mi manca qualcosa. Che senso ha che se si distorcono i dati in una finestra, posso modificare la complessità di un algoritmo da un punto di vista teorico anche se viene eseguito esattamente lo stesso numero di operazioni?

loops algorithms complexity

posta Pierre Arlaud 02.01.2014 - 11:53

fonte

4 risposte

7

Sembra che tu non abbia una chiara comprensione di ciò che n è in O (n) , motivo per cui sei perplesso.

My keen-eye brought me to the conclusion that, as doSomeAction is in O(1), the algorithm had to be in O(n²).

Questo è vero solo se entrambi i loop sono in O (n) ma se i loop hanno complessità O (p) e O (q) allora il programma complessivo ha complessità O (pq) e così via. Nel tuo esempio, hai un ciclo esterno che si svolge n volte e innescando un ciclo di lunghezza p non maggiore di 8 , in modo che l'intero il ciclo ha una complessità limitata da O (8n) = O (n) .

Se la complessità del loop interno non è costante, devi fare un'approssimazione più precisa.

I know however that nested loops can have a different complexity. For instance the following is in O(n.log(n))

Non lo è. Ricorda che

1 + 2 + ... + n = n(n+1)/2 = O(n²)

in modo che la complessità del loop sia O (n²) e non O (n.log (n)).

risposta data 02.01.2014 - 12:42

fonte

2

Sì. Ma modificando i dati, stai anche modificando n . Nel tuo primo esempio, n è in realtà costante. Quindi ha senso che l'intero algoritmo è in realtà costante.

Nel tuo secondo esempio, mentre puoi trasformare l'algoritmo O(n^2) in O(n) algoritmo, la quantità di dati aumenta da n a n^2 , quindi alla fine la complessità totale rimane la stessa.

Come ha suggerito Simon, la notazione O non riguarda i valori assoluti di n , ma il modo in cui il tempo dell'algoritmo cambia in base al modo in cui si modifica n . Con l'algoritmo O(n) , il tempo aumenta linearmente, quindi se n aumenta 2x, il tempo aumenta 2x. Con O(n^2) , il tempo aumenta quadraticamente, quindi se n aumenta 2x il tempo aumenta 4x, ecc.

Il punto è cambiando i dati, il tasso di crescita di n può anche cambiare. Come nel tuo esempio con la griglia. Se aumenti la lunghezza del lato per 2, allora l'algoritmo richiederà 4 volte tanto a lungo, a prescindere da cosa. Perché in O(n^2) , n è la lunghezza del lato e in O(n) , il n è il numero di elementi totali che è uguale al quadrato del lato.

risposta data 02.01.2014 - 12:34

fonte

0

Quando prendi N e la tua griglia per ottenere la tua O (n ^ 2) dovresti invece parlare di una griglia con per esempio N colonne e N righe.

Ora vedrai che con un N di raddoppiamento, quell'unità di tessere quadruplica.

E non importa se lo metti in lista o cambi la notazione, il problema avrà sempre O (n ^ 2) complessità.

risposta data 02.01.2014 - 12:53

fonte

Leggi altre domande sui tag loops algorithms complexity

La creazione di funzioni di utilità veramente piccole è una cattiva idea? [duplicare] Il valore di un codice più semplice rispetto alle prestazioni dovrebbe restituire più valori?

score 10 · Accepted Answer

Sembra che tu pensi che la complessità di un algoritmo sia legata al numero di cicli annidati. Non è il caso. La seguente parte di codice è O (1):

for i in [1.. 10^15]:
    for j in [1.. 10^15]:
        for k in [1.. 10^15]:
            dosomethingO1()

La complessità è correlata al tasso di crescita del numero di operazioni. Srotolare il tuo loop non cambia questo. Quindi:

foreach(element in myArray) {
    doSomeAction(element);
}

Ha 0 (1) se il numero di elementi in myArray è limitato. La complessità sarà decisa dal numero di iterazioni nel ciclo while.

Informazioni sull'esempio della griglia: se n è il numero di celle e la griglia è rappresentata come una matrice nidificata, il loop su quegli array produce ancora la complessità O (n).