Facile: Risolvi T (n) = T (n-1) + n per Metodo di iterazione

Qualcuno può aiutarmi con questo?Facile: Risolvi T (n) = T (n-1) + n per Metodo di iterazione

Utilizzare il metodo di iterazione per risolverlo. T (n) = T (n-1) + n

La spiegazione dei passaggi sarebbe molto apprezzata.

2012-12-02 blackvitriol

State richiesto di utilizzare un linguaggio di programmazione specifico o stai chiedendo di pseudo codice? –

codice pseudo..e grazie per la risposta immediata! : D – blackvitriol

Leggere questo: http://meta.stackexchange.com/questions/10811/how-to-ask-and-answer-homework-questions –

T(n) = T(n-1) + n 

T(n-1) =T(n-2) + n-1 

T(n-2) = T(n-3) + n-2

ecc è possibile sostituire il valore di T (n-1) e T (n- 2) in T (n) per avere un'idea generale del modello.

T(n) = T(n-2) + n-1 + n 


T(n) = T(n-3) + n-2 + n-1 + n 

T(n) = T(n-k) +kn - k(k-1)/2

Per caso base:

n - k =1 so we can get T(1)

k = n - 1 sostituto al precedente

T(n) = T(1) + (n-1)n - (n-1)(n-2)/2

Che si può vedere è di ordine n^2

fonte

2012-12-02 22:47:00 Fyre

Espandilo!

T(n) = T(n-1) + n = T(n-2) + (n-1) + n = T(n-3) + (n-2) + (n-1) + n

e così via, fino

T(n) = 1 + 2 + ... + n = n(n+1)/2 [= O(n^2)]

purché T(1) = 1

fonte

2012-12-02 22:43:11 Haile

+1 Pseudocode, shmeudocode ... È matematica: pura e semplice! – dasblinkenlight

Sei sicuro che questo è O (n²)? –

@ralu per essere più precisi, è Theta (n²), dal momento che n² delimita dall'alto e dal basso. – Haile

In pseudo codice che utilizza l'iterazione:

function T(n) { 
    int result = 0; 

    for (i in 1 ... n) { 
     result = result + i; 
    } 

    return result; 
}

fonte

2012-12-02 22:47:09

come ringrazio tutti per le risposte istantanee? : D – blackvitriol

haha, puoi votarli e dare loro un 'grazie: D' –

volevo ringraziarti ma dice che ho bisogno di 15 rep. grazie: D – blackvitriol

-2

metodo facile:

T (n) = T (n - 1) + (n)-----------(1) 
//now submit T(n-1)=t(n) 

T(n-1)=T((n-1)-1)+((n-1)) 
T(n-1)=T(n-2)+n-1---------------(2) 

now submit (2) in (1) you will get 
i.e T(n)=[T(n-2)+n-1]+(n) 
T(n)=T(n-2)+2n-1 //simplified--------------(3) 

now, T(n-2)=t(n) 
T(n-2)=T((n-2)-2)+[2(n-2)-1] 
    T(n-2)=T(n-4)+2n-5---------------(4) 
    now submit (4) in (2) you will get 
    i.e T(n)=[T(n-4)+2n-5]+(2n-1) 
    T(n)=T(n-4)+4n-6 //simplified 
    ............ 
T(n)=T(n-k)+kn-6 
    **Based on General form T(n)=T(n-k)+k, ** 
    now, assume n-k=1 we know T(1)=1 
      k=n-1 

    T(n)=T(n-(n-1))+(n-1)n-6 
    T(n)=T(1)+n^2-n-10 
    According to the complexity 6 is constant 

     So , Finally O(n^2)

fonte

2016-12-01 14:11:27

Per favore non risorgere domande di bassa qualità obsolete. – YSC

Mi è stata data una semplice procedura per ottenere la risposta .. lo so troppo a lungo ma non resuscitare @ YSC –

l'hai davvero ucciso:/ "Sappiamo T (1) = 0"? per avere k = n-1 devi avere T (1) = 1 quindi n-k = 1 => k = n-1 – Sanosay

Un'altra soluzione più facile

T(n) = T(n-1) + n 
    = T(n-2) + n-1 + n 
    = T(n-3) + n-2 + n-1 + n 
    // we can now generalize to k 
    = T(n-k) + n-k-1 + n-k-2 + ... + n-1 + n 
    // since n-k = 1 so k = n-1 and T(1) = 1 
    = 1 + 2 + ... + n 
    = n(n-1)/2 
    = n^2/2 - n/2 
    // we take the dominating term which is n^2*1/2 therefor 1/2 = big O 
    = big O(n^2)

fonte

2017-10-22 19:50:26

Facile: Risolvi T (n) = T (n-1) + n per Metodo di iterazione

risposta

Problemi correlati