Mi è stato permesso di semplificare i termini durante il calcolo di Big O?

Question

Mi è stato permesso di semplificare i termini durante il calcolo di Big O?

Naviga le tue risposte

#1 da (7 voti)

1

Voglio calcolare il runtime della seguente funzione

T (n) = (1 + 2 + 3 + 4 + 5 + ... + n) / n

All'inizio questo non mi è sembrato difficile perché può essere risolto facilmente trasformando la formula

T (n) = (n (n-1) / 2) / n = (n ^ 2-n) / n = n-1 che porta in O (n).

Pensando a questa funzione ho faticato. Non sono sicuro di poter ridurre n, perché non conosco il codice dietro quella funzione.

Ad esempio potrebbe essere qualcosa di simile

method foo()
{
          methodWhichTakesNCubeAmountOfTime(); //Build sum, O(n^2)
          methodWhichTakesNAmountOfTimeAndCantBeSimplified(); //O(n)
}

Per questo metodo otterrei n cubi come runtime.

O(n^2) + O(n) = O(n^2)

So che questo metodo non copre il termine originale ma spero che tu capisca cosa intendo: Il diviso per n potrebbe essere una funzione completamente diversa (che ha accidentalmente una complessità di n) e quindi non posso ridurre il altri n con esso.

Quindi sono confuso. Sono autorizzato a trasformare i termini normalmente durante il calcolo del Big O o alcune regole matematiche non si applicano qui?

Grazie.

algorithms complexity computer-science big-o

posta BudBrot 20.01.2018 - 14:48

fonte

1 risposta

Leggi altre domande sui tag algorithms complexity computer-science big-o

È accettabile per un'entità di dominio implementare un'interfaccia? Best practice per la compatibilità con le versioni precedenti del database

score 7 · Accepted Answer

Non solo puoi, è in una definizione molto precisa di O.

La complessità O non è così semplice come la maggior parte dei programmatori laici lo capisce.

Semplicemente detto, l'O è definito asintoticamente. Ciò significa che stai cercando di capire come si comporterebbe l'algoritmo se n si avvicina all'infinito. E nella maggior parte dei casi, un termine domina il calcolo. Il tuo esempio di

O(n^2) + O(n) = O(n^2)

è una buona rappresentazione di questo. Mentre per il piccolo n , il O(n) influenza il tempo, per n che si avvicina all'infinito, O(n) diventa trascurabile rispetto a O(n^2) . Quindi va bene ignorarlo.

Questo è anche il motivo per cui vedi Big-O spesso con un solo termine. Perché se questo termine è in equazione della complessità, lo dominerebbe come n si avvicina all'infinito.

Anche una nota. Mentre Big-O è un buon modo per misurare le prestazioni di un algoritmo, è più uno strumento matematico teorico, che un modo pratico per valutare gli algoritmi.

Ad esempio, potresti avere due algoritmi. Uno O(n^2) e il secondo O(1000*n) . La prima sarebbe chiaramente più veloce per n minore di 1000. Ma poiché le costanti vengono eliminate perché la complessità sia "corretta", la seconda dovrebbe essere scritta realmente come O(n) .