Qual è la complessità O grande di questo algoritmo ricorsivo?

Question

Qual è la complessità O grande di questo algoritmo ricorsivo?

#1 da (3 voti)
#2 da (2 voti)
#3 da (0 voti)

1

Sto seguendo un corso di Algoritmi e Strutture Dati.

Oggi, il mio professore ha detto che la complessità del seguente algoritmo è 2^n .

Ho aspettato che la lezione finisse, mi sono avvicinato e gli ho detto che credevo davvero che fosse un algoritmo di O(n) , e ho fatto il calcolo per dimostrarlo, e volevo mostrarglielo, ma ha continuato a dirlo non era, senza darmi alcuna spiegazione convincente.

L'algoritmo è ricorsivo e la sua relazione di ricorrenza è:

       { 1         if n=1
T(n) = {
       { 2T(n/2)   otherwise

L'ho calcolato come O(n) , in questo modo:

Espandiamo T(n)

T(n) = 2 [2 * T(n/(2^2))]
     = 2^2 * T(n/(2^2))
     = 2^2 * [2 * T(n/(2^3))]
     = 2^3 * T(n/(2^3))
     = ...
     = 2^i * T(n/(2^i)).

Ci fermiamo quando il termine all'interno di T è 1, cioè:

n/(2^i) = 1 ==> n = 2^i ==> i = log n

Dopo la sostituzione, otteniamo

T(n) = 2^log n * T(1)
     = n * 1
     = O(n).

Poiché questo algoritmo è saltato fuori da una lezione su Merge Sort, ho notato come Merge Sort, che notoriamente è O(n log n) ha una complessità di 2T (n / 2) + theta (n) (ovviamente maggiore di 2T (n / 2)), e gli ho chiesto perché è così, che un algoritmo con una complessità più bassa, ottiene un maggiore-O maggiore. Perché, a questo punto, è controintuitivo per me. Ha risposto, parole per parole, "Se pensi che sia contro-intuitivo, hai problemi seri in matematica."

Le mie domande sono:

C'è qualche errore nella mia dimostrazione?
L'ultima situazione non sarebbe contro-intuitiva?

algorithms complexity big-o algorithm-analysis

posta doplumi 15.10.2015 - 22:07

fonte

3 risposte

Leggi altre domande sui tag algorithms complexity big-o algorithm-analysis

Test unitario: programmazione strutturata vs non strutturata [chiusa] Qualità del codice: qual è il valore dell'osservazione dei if?

score 3 · Answer 1

Prima di tutto, per analizzare la complessità di un algoritmo semplice e ricorsivo, la prima tappa sarebbe il Teorema principale , dove abbiniamo la tua espressione T(n) = 2·T(n/2) allo schema T(n) = a·T(n/b) + f(n) . Confrontando i coefficienti, possiamo vedere che a = 2, b = 2, f(n) = x per alcuni costanti x . Il Teorema di Master ci dà poi la complessità a seconda che certe relazioni tra i coefficienti reggano.

Qui, il caso si applica dove esiste un c tale che f(n) = O(n^c) e c < log_b a , con c = 0 ( f(n) = O(1) = O(n^0) e 0 < log_2 2 <=> 0 < 1 ). Pertanto, il Teorema Master ci dice che T(n) = Theta(n^(log_b a)) = Theta(n) , quindi anche T(n) = O(n) . In altre parole, hai ragione .

La tua prova è valida, ma per essere davvero convincente dovresti usare la prova per tecnica di induzione. Hai essenzialmente usato l'induzione ma non hai etichettato chiaramente ogni fase, il che rende un po 'difficile da seguire (e, l'hai fatto all'indietro - dovresti iniziare con il caso base T(1) , quindi mostrare che la proprietà vale per T(n+1) per qualsiasi n anziché iniziare con il caso generale e lavorare verso il caso base).

score 2 · Answer 2

"The algorithm is recursive, and it has this complexity: ..."

Dalla formulazione della tua domanda sembra che la funzione T(n) non sia l'algoritmo da analizzare ma la sua complessità. Nella tua dimostrazione mostri che, in effetti, la funzione T si comporta asintoticamente come una funzione esponenziale.

Quindi l'errore potrebbe essere che stai provando a dimostrare la cosa sbagliata. In altre parole:

Hai ragione che calcolare T richiede tempo lineare (forse anche meno, tempo logaritmico suppongo).
Il tuo professore ha ragione nel dire che la complessità dell'algoritmo originale, la cui complessità è espressa da T , è esponenziale.

score 0 · Answer 3

L'algoritmo avrà il tempo di esecuzione di O ((log n) ^ 2), perché ci saranno passi di log n che raddoppiano un numero di n bit. Il risultato è O (n). È facilmente dimostrato dall'induzione completa che T (n) ≤ n, assumendo che n / 2 significhi floor (n / 2).

Per quanto riguarda l'intuizione, se T (n) = O (2 ^ n) allora T (1000) dovrebbe essere intorno a 2 ^ 1000. Ma poi T (1000) = 2 * T (500) che dovrebbe essere intorno a 2 ^ 501 ... Leggera differenza.

Ovviamente n = O (2 ^ n) secondo la definizione di Big-O.

Potrei sospettare che forse la ricorsione non sia effettivamente pubblicata qui correttamente se ciò che il tuo professore dice è così off-line.