chiarimenti sull'analisi ammortizzata

Naviga le tue risposte
0

Stavo esaminando un articolo qui

Nella sezione denominata Metodo aggregato, l'autore dice

Then summing over the entire sequence, all the 1's sum to O(n), and all the di also sum to O(n). That is,

e poi dà questo 

Σ1≤i≤n ci   ≤   n + Σ0≤j≤m 2j−1

Posso capire come sommare 1 per ottenere n, Ma non sono molto chiaro come il secondo termine diventi Σ0≤j≤m 2j−1 e quindi O (n)

Ci scusiamo per la formattazione .. Non sono sicuro di come stampare le notazioni matematiche qui. Vedrai per favore l'articolo originale?

    
posta damon 21.06.2013 - 08:02
fonte

1 risposta

1

I can understand how summing 1's to get n , But I am not very clear how the second term becomes Σ0≤j≤m 2j−1 and thereby O(n)

Questo è il modo in cui le prestazioni dell'algoritmo (il big-oh ) sono stimate. Mostra solo come si comporta l'algoritmo per un numero elevato di iterazioni.

Se fai molte iterazioni di un algoritmo, che ha O (1), allora vengono sommate, e questo è ciò che dice il tuo articolo.

Forse puoi vedere la tua somma come (f (n) -algoritmo grande-o valore) 

bigo=0;
for ( int i = 0; i < n; ++ i )
   bigo+=f(n);

che si traduce per O (1) in:     bigo = 0;     for (int i = 0; i < n; ++ i)        bigo + = 1;

Se il tuo f (n) sarebbe O (n), allora dovresti fare n * n il ciclo di iterazione, e quindi sarebbe f (n): 

bigo=0;
for ( int i = 0; i < n; ++ i )
  for ( int j = 0; j < n; ++ j )
     bigo+=1;

HTH

    
risposta data 21.06.2013 - 08:32
fonte

Leggi altre domande sui tag

Come si può scrivere CoffeeScript in CoffeeScript? [duplicare] Condividi più classi come una dll o una lib con più progetti