Dimostra la complessità per un algoritmo generico

Question

Dimostra la complessità per un algoritmo generico

#1 da (5 voti)

5

Sono nuovo alla teoria della complessità e sto cercando di dimostrare un fatto.

Quindi, consideriamo un algoritmo T che riceve all'input un numero intero

Questo algoritmo ha una complessità temporale per n = 1: θ (1) e per n > 1: 2T (n / 2) + θ (n).

Devo dimostrare che l'algoritmo T (n) ha complessità θ (n log (n)). Ho provato a dimostrarlo con l'induzione matematica ma niente sembra funzionare:

n = 1 -> θ(1)

n = 2 -> 2T(2/2)+θ(2) = 2T(1) + θ(2) = 2θ(1)+θ(2).

n = 3 -> 2T(3/2)+θ(3) = ??

È corretto questo approccio? C'è un modo migliore per capire questo?

complexity time

posta Madix 11.03.2016 - 19:54

fonte

1 risposta

Leggi altre domande sui tag complexity time

Qual è la teoria alla base dell'implementazione di due HashMaps con mirroring in grado di accettare operazioni di scrittura? Ho bisogno di un broker per mediare scritture in conflitto? Microservizi con lo stesso database

score 5 · Accepted Answer

Questa istanza specifica può essere facilmente risolta disegnando come viene calcolata la funzione ricorsiva T (n). Ogni chiamata a T (n) ha un costo di θ (n) più due volte il costo di metà della dimensione del problema.

 T(n) = ...

0:                 θ(n)
                  /   \
1:          θ(n/2)     θ(n/2)
            / \           / \
2:     θ(n/4) θ(n/4) θ(n/4) θ(n/4)
        / \       ⋰⋱  ⋰⋱  ⋰⋱
3: θ(n/16) θ(n/16) ⋯ ⋯  ⋯  ⋯  ⋯ ⋯
   ⋰⋱       ⋰⋱
  θ(1) θ(1)  ⋯  ⋯

Ogni livello ha due volte il numero di termini rispetto al livello precedente. L'intero albero è log ₂ n livelli profondi. Quindi qual è la somma di tutti i nodi in questo albero? Possiamo descriverlo come la somma

2⁰·θ(n/2⁰) + 2¹·θ(n/2¹) + 2²·θ(n/2²) + ⋯ + 2^{(log₂ n)}·θ(1)
= 2⁰·θ(n/2⁰) + 2¹·θ(n/2¹) + 2²·θ(n/2²) + ⋯ + n·θ(n/n)
= Σ_{i = 0 ... log₂n} 2ⁱ·θ(n/2ⁱ)
= Σ_{i = 0 ... log₂n} θ(n)
= log₂(n) · θ(n)
= θ(n · log n)

(Nota: questo presuppone che a · θ (b · n) = θ (a · b · n) sia ovvio, che tecnicamente dovrei mostrare in una dimostrazione rigorosa.)

Tuttavia, tali calcoli sono poco pratici da fare nel caso generale. Pertanto, di solito applicheremo il Teorema master che ci dà la complessità se il tempo di esecuzione ricorsivo della forma T (n) = a · T (n / b) + f (n) corrisponde a un modello specifico. Qui a = 2, b = 2, f (n) = θ (n).

Con il Teorema Master, il caso corrisponde a dove c = log _b a = 1 e f (n) = θ (n ^c · log ^k n) con k = 0. Questo ci dice che T (n) = θ (n ^c · log ^{k + 1} n) = θ (n · log n). Quindi entrambi i percorsi arrivano alla stessa soluzione, ma il Teorema Master è più generale, e anche più semplice perché dobbiamo solo abbinare la struttura della nostra funzione ricorsiva per il tempo di esecuzione contro tre pattern noti.

Il tuo approccio per induzione non è soddisfacente, perché non stai eseguendo alcuna fase di induzione . Di solito, mostriamo che la proprietà di induzione deve contenere n + 1 se è valida per n, quindi è corretta se vale anche per qualsiasi n noto (ad esempio n = 1). Questo è troppo scomodo da fare qui, quindi sarebbe meglio provare che una proprietà vale per 2n se vale per n. Lascerò questo come un esercizio per il lettore;) ma vorrei sottolineare che tale induzione sarebbe tecnicamente dimostrata solo per i poteri di 2 piuttosto che per tutti, e un ulteriore argomento sarebbe necessario per generalizzare questo.