Calcolo della complessità del tempo

Question

Attualmente sto lavorando ad alcune domande d'esame e sono rimasto bloccato a questo punto. Mi viene dato che un algoritmo Quicksort ha una complessità temporale di O(nlog(n)). Per una particolare dimensione di input, il tempo per ordinare l'elenco è di 4 minuti. La domanda continua a chiedere quanto tempo ci vorrà per ordinare una lista del doppio delle dimensioni, sullo stesso sistema.

Ho già escluso che il tempo non sia 8 minuti (il doppio della dimensione dell'ingresso = il doppio della durata, il ragionamento molto molto sbagliato).

Alcuni di lavoro che ho fatto:

Lavorando A

• 4 = nlog(n)
• 4 = log(n^n)
• 16 = n^n
• mi sono praticamente bloccato a questo punto.

lavoro B

• X = 2nlog(2n) >> 2n dal doppio ingresso
• X = 2n(1 + log(n))
• X = 2n + 2nlog(n) >> nlog(n) era 4 minuti
• X = 2n + 2(4) = 2n + 8
• ancora una volta rimasto bloccato a questo punto.

Answer 1

Penso che la prima cosa da notare su questo problema è che, dato che ci sono voluti 4 minuti per ordinare i numeri, n deve essere abbastanza grande. Ad esempio, ho appena usato quicksort per ordinare un miliardo di numeri sul mio computer, e ci sono voluti solo meno di 3 minuti. Quindi, n è probabilmente circa 1 miliardo (da dare o prendere un ordine di grandezza).

Dato che n è enorme, è probabile ragionevole approssimare questo runtime come c*n*lg(n) per qualche costante c, dal momento che i termini di ordine inferiore di espansione di esecuzione non dovrebbe essere troppo rilevanti per tale un grande n. Se raddoppiamo n, otteniamo la seguente moltiplicatore di runtime rispetto al runtime originale:

[Runtime(2n)]/[Runtime(n)] 
[c * (2n) * lg(2n)]/[c * n * lg(n)] 
2 * lg(2n)/lg(n) 
2 * log_n(2n) 
2 * (1 + log_n(2)) 

Qui, lg() è il logaritmo in una base arbitraria e log_n() è il logaritmo in base n.

Innanzitutto, poiché abbiamo assunto n è grande, un possibile modo di procedere sarebbe quello di approssimare log_n(2) come 0, quindi il moltiplicatore runtime sarebbe approssimato come 2 e il runtime totale sarebbe approssimata come 8 minuti.

In alternativa, dal momento che probabilmente conosciamo n entro un ordine di grandezza, un'altra possibilità sarebbe quella di approssimare il moltiplicatore per un valore probabile di n:

• Se n = 100 milioni, allora avremmo approssimare il moltiplicatore come 2.075 e il tempo di esecuzione totale come 8.30 minuti.
• Se n = 1 miliardo, quindi approssimiamo il moltiplicatore come 2,067 e il tempo di esecuzione totale come 8,27 minuti.
• Se n = 10 miliardi, quindi approssimiamo il moltiplicatore come 2.060 e il tempo di esecuzione totale come 8.24 minuti.

Nota che enormi cambiamenti nella nostra approssimazione di n producono cambiamenti piuttosto piccoli nell'approssimazione del runtime totale.

Vale la pena notare che, mentre questo è bello sulla carta, in pratica le considerazioni architettoniche possono far sì che i runtime della vita reale siano molto diversi da quelli che abbiamo calcolato qui. Ad esempio, se l'algoritmo induce un sacco di paging dopo aver raddoppiato la dimensione dei dati, il tempo di esecuzione potrebbe essere molto, molto più alto dei ~ 8 minuti che abbiamo approssimato qui.

Answer 2

Non è possibile calcolare il tempo assoluto, senza conoscere il valore di n.
Prendi questo attraverso alcuni valori empirici.
Si supponga 'k' è il tempo impiegato per una sola operazione

If, n = 2, k.n.log(n) = 4 => k.2.1 = 4 => k = 2 
    if n is doubled, k.2n.log(2n) = 2.4.2 => 16 minutes 

If, n = 4, k.n.log(n) = 4 => k.4.2 = 4 => k = 1/2 
    if n is doubled, k.2n.log(2n) = 1/2.8.3 => 12 minutes 

If, n = 64, k.n.log(n) = 4 => k.64.6 = 4 => k = 1/96 
    if n is doubled, k.2n.log(2n) = 1/96.128.7 => 9.33 minutes 

Così al crescere di n, il tempo impiegato si avvicina al doppio del tempo (8 minuti)

Answer 3

Le informazioni fornite sono incompleto.

Dimostrazione:

Diamo la complessità algoritmica essere O(nlogn). Questo significa il tempo impiegato, t = c*nlogn.

Pertanto, abbiamo le seguenti equazioni:

• 4 = c*n*logn
• t = c*(n2)*log(n2), dove t è la risposta necessaria
• n2 = 2*n2

Numero di variabili = 4 (n, n2, t, c)
Numero di equazioni uniche = 3
Poiché abbiamo bisogno di 4 equazioni per 4 variabili, le informazioni fornite sono incomplete.

Answer 4

Mi piace il ragionamento di @ Amitoj, ma lo generalizzerei.

Let n0 = il numero di elementi che si traduce in un tempo di esecuzione di 4 minuti e n1 = 2 * n0. Poi abbiamo

c = 4 mins/(n0 * log n0) 

Stiamo cercando di trovare

t = c * n1 * log n1 
    = 4 mins/(n0 * log n0) * n1 * log n1 
    = 4 mins * (n1/n0) * (log n1/log n0) 

n1/n0 è sempre = 2.

Come n0 => l'infinito, il limite di log n1/log n0 va a 1.

Quindi sì, dato che n0 diventa più grande, il limite di t è 4 mins * 2 = 8 mins.

Answer 5

Tutte le risposte, ad eccezione di Anmol Singh Jaggi, sono errate.

Prima di tutto è facile vedere che questa informazione non è sufficiente per ottenere una risposta. Ed ecco perché:

Tutto quello che devi fare è risolvere un'equazione. Se la complessità temporale del vostro algoritmo è O (n log n), quindi la prima equazione che hai è:

dove n nella dimensione della vostra lista. Se vogliono di trovare quanto tempo ci vorrà per terminare l'algoritmo per dimensioni due volte più grande, si tratta fondamentalmente vogliono trovare x:

Quindi, in pratica è necessario risolvere un sistema di 2 equazioni con 3 sconosciuti. Questo ha o 0 risposte (non nel nostro caso) o una quantità infinita di risposte.

---

Ora si devono fare ipotesi del vostro c1. Se c1 = 1, quindi

Sostituendo n per la seconda equazione si ottiene: x = 13.5. Quindi 13 e mezzo minuto.

---

Ma ancora una volta, questa risposta abbiamo ottenuto sul presupposto che c1 è uguale a 1, se avete un altro fattore costante, si otterrà un'altra risposta.

Answer 6

Questo suona come una domanda d'esame assolutamente terribile, probabilmente scritta da qualcuno che non ha una profonda comprensione di cosa sia realmente la notazione Big-O. C'è molto di sbagliato in questo - molte delle quali sono già state affrontate in altre risposte.

Il problema più grande è che la notazione Big-O non offre alcuna relazione diretta con il tempo reale. Invia una quantità enorme di informazioni che sarebbero necessarie per rispondere alla domanda vera e propria che viene posta.

Le altre risposte qui hanno evidenziato che la domanda non fornisce alcuna indicazione sul numero di elementi presenti nel set originale di input, solo che nel secondo set sono presenti il ​​doppio e che l'informazione è fondamentale dare una risposta Ma ci sono un paio di cose che non hanno menzionato ...

In primo luogo, Big-O ignora i costi generali dell'algoritmo. Potrebbe essere il caso in cui l'algoritmo utilizzato in realtà impieghi 3,5 minuti per l'impostazione, indipendentemente dal numero di ingressi ricevuti, e che per il set di input originale il tempo di elaborazione effettivo sia solo di circa 30 secondi. Ciò influenzerà seriamente il calcolo del tempo impiegato per qualsiasi numero arbitrario di input.

Ma come tale omissione, Big-O lo fa ancora di più.

Partenza questa citazione da Wikipedia:

Nell'uso tipico, la definizione formale di notazione O non viene utilizzato direttamente; piuttosto, la notazione O per una funzione f è derivata dalle seguenti regole di semplificazione:

• Se f (x) è la somma di diversi termini, quello con il tasso di crescita è mantenuta, e tutti gli altri omesso.
• Se f (x) è un prodotto di più fattori, tutte le costanti (termini nel prodotto che non dipendono da x) vengono omesse.

Ciò significa che il calcolo tempo può includere più termini che potrebbero andare scartate. Cosa succede se l'algoritmo richiede il tempo c * (n + n * log(n)) per completare, senza sovraccarico? Nella notazione Big-O è ancora O(nlogn).

L'unica risposta che è realmente possibile alla domanda d'esame è "un po 'più di 4 minuti". Non possiamo sapere nulla di più senza molte più informazioni. In particolare:

• Qual è il sovraccarico?
• Qual è il costo per operazione?
• Di quanti articoli stiamo parlando?
• Quali altri termini sono stati eletti?