Big-O per ciclo annidato

Naviga le tue risposte
8

Sto leggendo questo post su Big-O
Dice che il seguente codice è O (n ^ 2): 

bool ContainsDuplicates(String[] strings)
{
    for(int i = 0; i < strings.Length; i++)
    {
        for(int j = 0; j < strings.Length; j++)
        {
            if(i == j) // Don't compare with self
            {
                continue;
            }

            if(strings[i] == strings[j])
            {
                return true;
            }
        }
    }
    return false;
}

Ma non riesco a capire perché.
Il ciclo interno fa qualcosa di costante.
Quindi è la somma di 1 ... N di una costante. cioè numero costante O (1).
Il ciclo esterno è la somma su O (1).
Quindi immagino che sia n * O (1).

Penso di aver frainteso qualcosa qui.
Non penso che tutti i cicli annidati significano O (n ^ 2), giusto?

    
posta user10326 25.09.2011 - 23:20
fonte

4 risposte

18

Il tuo errore è con il ciclo interno. Fa qualcosa di costante n volte, quindi è O ( n ). Il ciclo esterno esegue il ciclo interno n volte, quindi è O ( n × n ) o < em> O ( n 2 ).

In generale, se il numero di iterazioni effettuate da un loop dipende dalla dimensione dell'input, è O ( n ). E se k tali loop sono nidificati, è O ( n k ).

    
risposta data 25.09.2011 - 23:26
fonte
4

Se la lunghezza della stringa è n , il test se i == j verrà eseguito n ^ 2 volte. L'ordine di un algoritmo è l'ordine di qualsiasi parte di esso ha l'ordine più alto. Poiché 'i' viene confrontato con 'j' n ^ 2 volte, l'ordine dell'algoritmo non può essere inferiore a O(n^2) .

Per un 'n' molto grande, il raddoppio 'n' quadruplicherà il tempo di esecuzione.

    
risposta data 25.09.2011 - 23:25
fonte
2

Stai interpretando erroneamente cosa significhi un'operazione costante.

Un'operazione costante è un'operazione che viene eseguita sempre in un intervallo di tempo fisso indipendente dall'input che riceve.

i == j è un'operazione costante perché esegue questa istruzione in un intervallo di tempo prestabilito. Diciamo che ci vuole 1 unità di tempo.

Ma questa operazione costante viene eseguita (nessun valore di i) * (nessun valore di j) volte. Diciamo che i e j sono eseguiti 10 volte ciascuno. Quindi, per calcolo, occorrono 100 unità di tempo per il completamento di i == j in un ciclo annidato. Quindi varierà quando i valori di i e j variano.

Possiamo essere sicuri che i == j sarà fatto in 1 unità di tempo, ma non possiamo sapere quante volte verrà eseguito = = j.

Se viene eseguito n volte, saranno necessarie n unità di tempo. Il ciclo esterno esegue il ciclo interno n volte. Quindi in sostanza i == j operazioni sono fatte n ^ 2 volte.

Tutti i cicli annidati significano O (n ^ (no di cicli annidati)). Qui O indica il limite superiore che significa che il codice verrà eseguito in un valore inferiore o uguale al valore di O (). Questa è la garanzia che non ci vorrà più tempo, ma può richiedere meno tempo non più grande.

    
risposta data 26.09.2011 - 14:22
fonte
0

I cicli nidificati eseguono O ( i 1 * i 2 * ... * i n ), dove n è il numero di cicli nidificati e i x è il numero di iterazioni nel ciclo x . (Oppure, per dirla in un altro modo, è il prodotto del numero di iterazioni in ciascuno dei loop.)

La tua coppia di loop itera sullo stesso array due volte, che per coincidenza è O (n * n) o O (n 2 ).

Quello che succede all'interno del ciclo più interno viene trattato come costante perché succederà ogni volta. La notazione Big-O non si riferisce alla misurazione del rendimento del codice lineare, ma piuttosto al confronto relativo di come gli algoritmi iterativi si comportano quando vengono forniti elementi di input n da trattare. Alcune operazioni che non eseguono alcuna iterazione (come push o pop su una pila) vengono sottoposte a dinging come O (1) perché gestiscono un elemento dei dati.

    
risposta data 25.09.2011 - 23:52
fonte

Leggi altre domande sui tag

Come si pronuncia l'operatore '...' [chiuso] Ci sono state dispute quando il software identifica i sessi con un booleano? [chiuso]