Ecco una ripartizione degli scenari comuni e delle loro complessità di runtime:
1. Tempo costante (O (1))
* Quando il ciclo esegue un numero fisso e piccolo di volte indipendentemente dalla dimensione dell'input. Questo è raro, ma potrebbe accadere se la condizione di loop dipende da un valore costante e non è influenzata dall'input.
`` `Python
i =0
Mentre io <5:# loop esattamente 5 volte
Stampa (i)
i +=1
`` `
2. Tempo logaritmico (O (log n))
* Quando il ciclo riduce la dimensione del problema di un fattore costante in ogni iterazione. Un esempio classico è la ricerca binaria.
`` `Python
basso =0
alto =n - 1
mentre basso <=alto:# loop continua finché lo spazio di ricerca esiste
mid =(basso + alto) // 2
Se arr [mid]
elif arr [mid]> bersaglio:
alto =Mid - 1
altro:
Restituisci a metà # Target trovato!
`` `
Qui, la dimensione dello spazio di ricerca (da `basso` a` alto`) è approssimativamente dimezzata in ogni iterazione. Pertanto, il ciclo esegue circa `log2 (n)` volte.
3. Tempo lineare (O (n))
* Quando il ciclo itera attraverso ogni elemento di un input di dimensioni `n` una volta. Questo è molto comune.
`` `Python
i =0
mentre io
i +=1
`` `
In questo caso, il corpo del loop esegue `n` volte.
4. Tempo quadratico (O (n^2))
* Quando il ciclo itera `n` volte per ciascuno degli elementi` n` (loop spesso nidificati).
`` `Python
i =0
Mentre io
mentre j
J +=1
i +=1
`` `
Ciò comporta un ciclo `while` nidificato, in cui entrambi i loop iterano` n` volte. Il numero totale di iterazioni è `n * n =n^2`.
5. Altro tempo polinomiale (O (n^k))
* Generalizzazioni dell'esempio quadratico sopra. Ad esempio, tre loop nidificati che ogni iterazione di `n` volte comporterebbe una complessità di O (n^3).
6. Tempo esponenziale (o (2^n)) o peggio
* Il tempo di esecuzione del loop cresce esponenzialmente con la dimensione dell'input. Questo spesso indica un algoritmo mal progettato o un problema intrinsecamente molto difficile. Esempi potrebbero comportare il tentativo di tutte le possibili combinazioni di elementi.
Considerazioni chiave:
* Dimensione input (N): Cosa rappresenta `n`? La dimensione di un array, l'entità di un numero, ecc. Questo è fondamentale per esprimere la complessità in termini di input.
* CONDIZIONE Variabile Modifiche: In che modo le variabili che controllano la condizione di loop cambiano all'interno del ciclo? Aumenta di una quantità costante, diminuzione di un fattore, ecc.?
* Operazioni all'interno del loop: Il tempo di esecuzione delle operazioni * all'interno * Il ciclo conta. Se, ad esempio, hai un'operazione O (n) all'interno di un ciclo che esegue N volte, la complessità complessiva è O (n * n) =O (n^2).
Come determinare la complessità di runtime:
1. Identifica la dimensione dell'input (n): Qual è il parametro di dimensioni pertinente?
2. Determina il numero di iterazioni: Quante volte il loop esegue *in relazione a `n` *? Questa è la parte fondamentale.
3. Considera le operazioni all'interno del loop: Se il ciclo contiene operazioni complesse, la loro complessità di runtime deve essere presa in considerazione. La complessità complessiva diventa la complessità delle iterazioni del loop moltiplicato per la complessità dell'operazione più costosa all'interno del ciclo.
4. Esprimi la complessità: Usa Big O Notation (O (), ω (), θ ()) per rappresentare il limite superiore, il limite inferiore o il limite stretto del tempo di esecuzione. In genere, ci concentriamo su Big O (scenario peggiore).
Esempio:
`` `Python
def processo_array (arr):
n =len (arr)
i =0
Mentre io
mentre j
arr [i], arr [j] =arr [j], arr [i] # swap temporale costante
J +=1
i +=1
RITORNO ARR
`` `
Analisi:
* `n` è la lunghezza dell'array di input` arr`.
* Il ciclo esterno (`i`) corre` n` volte.
* Il ciclo interno (`j`) esegue circa` n - i` volte. Nel peggiore dei casi, quando `io sono 0, funziona` n` volte.
* L'operazione di scambio all'interno del ciclo interno è O (1).
Pertanto, i loop nidificati contribuiscono alla complessità di O (n^2). Lo swap è tempo costante e non influisce sul runtime complessivo di O (n^2). Questo algoritmo è simile al tipo di selezione.
In sintesi, per determinare la complessità di runtime di un ciclo `mentre ', analizza attentamente quante volte il ciclo esegue rispetto alla dimensione dell'input e considerare la complessità delle operazioni eseguite all'interno del ciclo.
Programmazione © www.354353.com