Was ist die Zeit, die Komplexität der Wiederholung, T(n) = 2T(n-1) + 4

Was ist die Zeit, die Komplexität der Wiederholung, T(n) = 2T(n-1) + 4 ?

Ich habe ernsthafte Probleme mit diesem.
Ich habe versucht:

T(n) = 2T(n-1)+4 = 2(2T(n-2)+4)+4 = 4T(n-2)+12= 4(2T(n-3)+4)+4 = 8T(n-3)+20 = 8(2T(n-4)+4)+4 =
16 T(n-4)+36 =...

T(n) = 2^kT(n-k) + (4+2^(k+1))

so wie es aussieht T(n) = 2^n + (4+2^(n+1)), aber es scheint nicht richtig... bitte um Hilfe 🙁

  • Sie sagen nicht uns, der Initialisierung. Ist es T(0) = 0 oder T(0) = 1 ? Oder Sie kümmern sich nicht und Sie wollen nur das O asymptotische ?
  • O(n) ist Polynom
InformationsquelleAutor CnR | 2014-03-30
  1. 4

    Ihre Berechnung falsch. Ich gehe davon aus, dass hier T(0)=0

    T(n) =                       2T(n-1)+  4 
     =   2(2T(n-2)+4)+  4 =  4T(n-2)+ 12
     =   4(2T(n-3)+4)+ 12 =  8T(n-3)+ 28 
     =   8(2T(n-4)+4)+ 28 = 16T(n-4)+ 60
     =  16(2T(n-5)+4)+ 60 = 32T(n-5)+124
     =  32(2T(n-6)+4)+124 = 64T(n-6)+252

    Dann jetzt: betrachte die Sequenz 

    0,4,12,28,60,124,252,508,1020,2044,...

    Ist es sehr verlockend, fügen Sie 4, um all diese zahlen:

    4,8,16,32,64,128,256,512,1024,2048,...

    Erkennen Sie es ? Also die Vermutung ist klar 

    T(n) = 2^(n+2) - 4

    Nun, man kann leicht beweisen, dass es mit Induktion.

    Übrigens, wenn T(0) ist nicht gleich 0 die Formel ist

    T(n) = 2^(n+2) - 4 + T(0)*2^n
    • +1. auch ich nehme an, du meinst 1024, nicht 1025 🙂
    • So wahr ! Behoben.
    • Finde immer die base-case für das Wiederauftreten der Probleme. Base Fall helfen wird, um daraus die ganze Formel. In diesem Fall base-Fall ist T(0)
    InformationsquelleAutor hivert
  2. 3

    Lösung der Wiederholung, Beziehung, fand ich dies:

    Was ist die Zeit, die Komplexität der Wiederholung, T(n) = 2T(n-1) + 4

    InformationsquelleAutor Mohamed Ennahdi El Idrissi
  3. 2
    T(n) = 2T(n-1) + 1

    Lassen n = log m dann bekommen wir T(log m)=2T(log m - log 2) + 1

    Übernehmen S(a) = 2S(a/2) + 1

    Anwenden Master-theorem erhalten wir:
    n^logb^a = n^log2^2 = n.

    n^log2^2-1 = 1 hier € = 1

    Vom ersten Fall erhalten wir: S(a) = O(a)

    daher T(n) = O(2^n)

    InformationsquelleAutor Lordferrous
Schreibe einen Kommentar