Analisi algoritmi per complessità temporale

Question

Sto analizzando un algoritmo e voglio solo sapere se sono sulla strada giusta.

Per questo algoritmo, sto solo contando le moltiplicazioni sulla linea che hanno *** in esse.

Ecco l'algoritmo:

1. Così sto iniziando dal più linea interna, posso vedere ci sono 2 le operazioni di là (i due moltiplicazioni).
2. Ora sto guardando i 2 loop più interni, quindi posso dire che il p=p*20*z viene eseguito esattamente (j) + (j-1)+(j-2)+(j-3)...1 volte. Questo è uguale a j(j+1)/2.
3. Quindi, in totale, poiché ci sono due moltiplicazioni, succede 2 * (j(j+1)/2).
4. Quindi, infine, il ciclo "i" avviene esattamente n volte, quindi, in totale, è n(2 * (n(n+1)/2)).

Questo è il mio processo di pensiero dietro questo. Ho ragione? Grazie.

Answer 1

Il tuo processo di pensiero è corretto. È necessario sostituire il termine j con un n (n è il più grande valore che j può assumere), ma probabilmente è un refuso.

Inoltre, è possibile semplificare ulteriormente da dove ti trovi:

n(2*(n(n+1)/2)) 
2*n*(n^2+n)/2 
n^3+n^2 

=> O(n^3) 

L'ultimo passo è perché il termine n cubetti crescerà ad un tasso molto più grande del n quadrato termine possiamo dire che dominerà il runtime per grande n. Solo un altro punto che vorrei menzionare è che dovresti forse considerare il negozio come un'operazione e le due moltiplicazioni, anche se ovviamente questo non cambierà il runtime big-o semplificato.

Answer 2

di calcolo in questo particolare esempio potrebbe essere semplificata se si può scoprire che tutti e tre i cicli ha la stessa condizione di uscita up to n:

1. i <= n
2. j <= n
3. k <= j

Fondamentalmente il terzo ciclo eseguirà anche le iterazioni n perché j <= n così k <= n, questo significa che la complessità sarebbe n * n * n = O(n^3)

Answer 3

In questo modo è possibile ottenere l'ordine di crescita del vostro algoritmo metodicamente: