Come risolvere O (N log N) e altro

1

Ho seguito l'esercizio:

An algorithm takes 0.5 ms for input size 100. How large a problem can be solved in 1 min if the running time is the following:

  1. linear
  2. O (N log N)

...

Quindi l'algoritmo può elaborare 100 elementi in 0,5 ms, quindi 100 * (2 * 1000 * 60) = 12 000 000 elementi elaborati per il tempo lineare.

Ora come risolvere 12 000 000 = O (N log N) per N? N = 2 ^ (12 000 000 / N)

E sono bloccato su come eliminare l'esponenziale N.

Anche l'esercizio continua:

  1. Order the following functions by growth rate, and indicate which, if any, grow at the same rate.:

N, square root of N, N^1.5, N^2 , N log N, N log log N, N log^2 N, N log (N^2), 2/N, 2N, 2N/2, 37,N^3, N^2 log N

Poiché non ho alcuna soluzione come riferimento qui è mio:

2/N < sqrt(N) < 37< N=2N/2 < 2N < N log log N < N log N < N log (N^2) < N log^2 (N) < N^1.5 < N^2 < N^2 log N

Sarebbe bello se qualcuno potesse guardarlo e correggermi dove potrei sbagliarmi.

    
posta Don_M 28.03.2016 - 16:39
fonte

1 risposta

1

Se la tua funzione è O (n ln n), puoi supporre che l'ora esatta sia c * n * ln n. Digita i numeri per n = 100 in un foglio di calcolo e ottieni c = 0,5 ms / 100 / l 100.

Inserisci una formula in un foglio di calcolo e inserisci i valori per n fino a quando non ottieni la soluzione.

Potresti farlo nella tua testa: se lineare potresti risolvere per n = 12 milioni. 12 milioni sono circa 100 ^ 3,5 quindi il logaritmo è circa 3,5 volte più grande, quindi dividi per 3,5 dando circa 3,5 milioni.

37 è compreso tra 2 / n e n / 2. Ln (n ^ 2) è solo 2 ln n. E ignori le costanti quando guardi gli ordini di crescita.

Per risolvere qualcosa come n ln n = 12000000 lo si cambia in n = 12000000 / ln n. Quindi inizi con n = 12000000, sostituisci n con 12000000 / ln n e ripeti alcune volte. Il trucco è scrivere n="qualcosa che si restringe". N = 2 ^ (12000000 / n) non funziona.

    
risposta data 28.03.2016 - 22:43
fonte

Leggi altre domande sui tag