Il mio ragionamento per determinare il Big-O di questo algoritmo è corretto?

0

Prendi il seguente algoritmo con due sezioni separate e le sezioni non si influenzano a vicenda (la funzione non è ricorsiva).

void algorithm(int x)
{
   // This section of the algorithm has linear growth... O(x)

   // This section of the algorithm has x * logarithmic growth... O(xlogx)
}

Per determinare la notazione Big O dell'algoritmo, ho fatto quanto segue:

Tempo di esecuzione dell'algoritmo approssimativamente = xlogx + x

Il termine più grande è xlogx, quindi l'algoritmo è Big O = O (xlogx).

È corretto? O devo inserire più informazioni dalle due sezioni dell'algoritmo. Ad esempio, la prima sezione esegue effettivamente operazioni 10x, ma nei miei calcoli uso solo la notazione O (x).

    
posta Inertial Ignorance 22.04.2018 - 22:07
fonte

1 risposta

2

O (x) + O (xlog (x)) = O (xlog (x)) perché O (xlog (x)) è il termine dominante / superset di O (x).

Algoritmi: come sommare O (n) e O (nlog (n)) insieme?

Vedi le risposte di Justin Cave e di davidk01.

    
risposta data 23.04.2018 - 00:07
fonte

Leggi altre domande sui tag