Ho problemi a fornire la complessità del tempo giusto nella notazione O per il seguente ciclo:
k := 0
for i := 0 to N
for j := k to M
// something
k = k + 1
Dove N = M. Senza il valore iniziale modificato di j del valore interno questo sarebbe ovviamente O (N * M), ma con il tempo di esecuzione decrescente del ciclo interno in ogni fase del ciclo esterno sono abbastanza confuso. Come può essere affrontato?
Quando M >= N , diminuendo di uno, il ciclo interno esegue (2*M+N)/2 sulla media, quindi la complessità complessiva rimane O(M*N) . Quando N > M , il ciclo esterno esegue M volte e quindi diventa un'operazione vuota per le% iterazioni% co_de rimanenti, perché una volta N-M raggiunge k , il ciclo interno viene eseguito a zero volte. Quindi il risultato complessivo è M
Il tempo di esecuzione ridotto non è sufficiente per modificare la complessità del tempo: il ciclo interno viene eseguito ancora in O (M).
Voglio provare.
Il 'qualcosa' sarebbe fatto N * M se non ci fosse 'k'.
Quanti "qualcosa" non sarebbero stati eseguiti a causa di k?
Prima iterazione, non ci sarà rimosso 'qualcosa'. Seconda iterazione, ce ne sarà una rimossa. Terzo, due. Quindi, il numero di "qualcosa" che non sarebbe stato eseguito a causa di k è uguale alla somma da 1 a M
Sum da 1 a M è uguale a M * (M + 1) * (1/2). Quindi:
O ((M * N) -M (M + 1) * 1/2)
in realtà è O (N * (N + 1) / 2) ... perché ??
sembra proprio questo ...
1
1 2
1 2 3
1 2 3 4
sommario di gauss .. e poiché la notazione asintotica ignora il valore costante, allora sarà O (N * N) ... =)
Leggi altre domande sui tag theory computer-science