Aiuto con la complessità della notazione Big-O [duplicato]

1

Come faccio a trovare la complessità della notazione O per quanto segue?

 int sum = 0;
 for (int i = 1; i <= n*2; i++ )
   sum++;

Ho letto la guida su Big - O e altri post su Big -O complessità, ma sono ancora perso.

    
posta ixbo45 22.11.2016 - 01:32
fonte

1 risposta

1

Ho appena imparato la notazione di Big O in questo semestre, ma dalla mia comprensione la notazione di O guarda alla complessità di un algoritmo. In questo caso il ciclo viene eseguito 2 volte, quindi eseguirai sum ++ 2n volte, quindi sarebbe O (2n).

La notazione di Big O analizza lo scenario peggiore con input molto grandi in modo da poter eliminare la costante 2, poiché a n molto molto grandi o input il 2 non ha un grande impatto sulla complessità, quindi Big O sarebbe O (n).

Probabilmente potresti cercare esempi di O (n), O (logn), O (2 ^ n), O (n ^ 2) in modo da poter vedere quali algoritmi con queste complessità assomigliano.

    
risposta data 22.11.2016 - 02:21
fonte

Leggi altre domande sui tag