necessita di una spiegazione sull'ammortamento nell'algoritmo

Question

necessita di una spiegazione sull'ammortamento nell'algoritmo

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

1

Sono un'analisi dell'algoritmo di apprendimento e mi sono imbattuto in uno strumento di analisi per comprendere il tempo di esecuzione di un algoritmo con prestazioni molto variabili che viene definito come ammortamento.

Le virgolette automatiche

An array with upper bound of n elements, with a fixed bound N, on it size. Operation clear takes O(n) time, since we should dereference all the elements in the array in order to really empty it.

L'affermazione sopra è chiara e valida. Ora considera il contenuto successivo:

Now consider a series of n operations on an initially empty array. if we take the worst case viewpoint, the running time is O(n^2), since the worst case of a sigle clear operation in the series is O(n) and there may be as many as O(n) clear operations in the series.

Dalla dichiarazione precedente come è la complessità temporale O (n ^ 2)? Non ho capito la logica dietro. se vengono eseguite 'n' operazioni come è O (n ^ 2)? Per favore spiega cosa sta cercando di trasmettere l'autor ..

algorithm-analysis

posta Pradeep 18.11.2012 - 19:08

fonte

2 risposte

Leggi altre domande sui tag algorithm-analysis

Flusso di lavoro dell'applicazione Gestione errori MVC PHP, visualizzazione visualizzazione e autorizzazioni utente

score 2 · Answer 1

Nel tuo caso, n è la dimensione dell'array. E l'algoritmo funziona al massimo una volta sull'array. Ogni volta che viene eseguito, esegue un'operazione (o chiama un'altra funzione) che viene eseguita al massimo una volta sull'array. Quindi, se si assume che il peggiore costo di esecuzione dell'algoritmo clear () sia O (n) e che l'algoritmo esterno non comporti nulla di più costoso o proporzionale a quell'algoritmo, si eseguirà una funzione O (n) clear () n volte .

Ciò significa che il costo complessivo della funzione sarà n * O (n) o O (n ^ 2).

Una cosa importante da notare è che l'operazione non è un'operazione costante. Quando si dice che eseguire un'operazione n volte costa O (n), significa semplicemente che quell'operazione è un'operazione costante o O (1) - quella che non aumenta di costo con l'aumento delle dimensioni. La funzione clear () non si adatta a questa descrizione e quindi non si può dire che l'esecuzione della funzione clear () n volte sia un'operazione O (n).

Post script:

O (n ^ 2) significa che la complessità del tempo di esecuzione della funzione esaminata non supererà la crescita quadrata per valori sufficientemente grandi di n.

In parole più semplici, per valori grandi di n, O (n ^ 2) significa che il tempo di eseguire l'algoritmo esaminato su un input di dimensione n non aumenta di più di quattro volte quando n è raddoppiato. La parola chiave qui è grande perché per valori più piccoli di n, i fattori costanti (anche quando esistono come coefficienti) possono essere significativi. Teoricamente, valori elevati di n significano avvicinamento all'infinito.

score 0 · Answer 2

"Now consider a series of n operations on an initially empty array. if we take the worst case viewpoint, the running time is O(n^2), since the worst case of a single clear operation in the series is O(n) and there may be as many as O(n) clear operations in the series."

se esegui n operazioni su un array con n elementi (assumendo che ogni operazione sia di ordine 1), ottieni n X O (n) - > O (n ^ 2).

Esempio:

Dire n = 3, si desidera eseguire 3 cancellazioni sull'array. il primo processo chiaro richiede 3 operazioni il secondo processo chiaro richiede 3 operazioni. il terzo processo chiaro richiede 3 operazioni. totale = 3x3 = 9 = O (3 ^ 2).

La parte difficile che non riesco a giustificare è quella in corsivo!