Lösung von Wiederholungsbeziehungen "Chip & Conquer"

  • Ich hatte die Aufgabe, einige Wiederholungsbeziehungen zu lösen, und ich habe Probleme mit dem sogenannten "Chip & amp; Beziehungen erobern.

    Hier einige Beispielprobleme:

    $$ T (n) = T (n-5) + cn ^ 2 $$

    und

    $$ T (n) = T (n-2) + \ log {n } $$

    Ich sollte eine Antwort in der $ \ Theta $ -Notation geben. Wie gehe ich um und löse Beziehungen wie diese?

    26 June 2016
    Raphael
2 answers
  • Zur Vereinfachung nehmen wir an, dass $ 5 $ $ n $ und $ n / 2 = n-5k $ für eine ganze Zahl $ k & gt; 0 $ teilt.

    $$ \ begin {align *} T (n) & amp; = T (n-5) + cn ^ 2 \\ T (n) & amp; = cn ^ 2 + c ( n - 5) ^ 2 + c (n - 10) ^ 2 + c (n - 15) ^ 2 + ... + c5 ^ 2 + c0 ^ 2 \ c | n = c (n ^ 2 + (n - 5) ^ 2 + (n - 10) ^ 2 + (n - 15) ^ 2 + ... + 5 ^ 2 + 0 ^ 2) \\ & amp; \ ge c (n ^ 2 + (n - 5) ^ 2 + (n - 10) ^ 2 + (n / 2) ^ 2) \ gec (n / 2) (1/5) (n / 2) ^ 2) \ \ & lt; = & gt; = cn ^ 3/40 | = (c / 40) n ^ 3 \\ | | \ omega (n ^ 3) \ T (n) & amp; = cn ^ 2 + c (n - 5) ^ 2 + c (n - 10) ^ 2 + c (n - 15) ^ 2 + ... + c5 ^ 2 + c0 ^ 2 \\ | | & amp; \ le c (n / 5) n ^ 2 \ le cn ^ 3 \\ & amp; = O (n ^ 3) \\ \ end {align *} $$

    Wir schließen daraus, dass $ T (n) = \ Theta (n ^ 3) $ ist.


    Nehmen wir zur Vereinfachung an, dass $ n / 2 = n-2k $ für eine ganze Zahl $ k & gt; 1 $ ist.

    $$ \ begin {align *} T (n.) ) & amp; = T (n-2) + \ log n = \ log n + \ log (n - 2) + \ log (n - 4) + ... + \ log (4) \\ & amp; \ ge \ log n + \ log (n - 2) + \ log (n - 4) + ... + \ log (n / 2) \ ge (n / 2) log (n / 2) \\ & amp; = \ Omega (n \ log n) \\ T (n) & amp; = T (n-2) + \ log n = \ log n + \ log (n - 2) + \ log (n - 4) + ... + \ log (4) \\ & amp; \ le (n / 2) \ log n \\ & amp; = O (n \ log n) \\ \ end {align *} $$

    Wir schließen daraus, dass $ T (n) = \ Theta (n \ log n) $ ist.

    11 July 2012
    GillesTimeless
  • Erweitern Sie die Wiederholung und summieren Sie sie auf.

    Beispiel 1:

    $$ \ begin {align * } T (n) & amp; = T (n-5) + O (n ^ 2) | = T (n-10) + O (n ^ 2) = \ dots \\ & amp; = T (0) + \ {\ text {\ (n / 5 \) Begriffe, jeweils \ (O (n ^ 2) \)} \} \ end {align *} $$

    Nun sagen wir $ T (0) = c $. Dies wäre im Allgemeinen in der Frage gegeben.

    so würde sich dies zu $ ​​(n / 5) .O (n ^ 2) = O (n ^ 3) $

    Beispiel 2:

    $$ \ begin {align *} T (n) & amp; = T (n-2) ) + \ log n | | = T (n-4) + \ log (n-2) + \ log (n) = \ dots \\ & amp; = T (0) + \ log (n-2 ^ k) + \ dots + log (n) = c + \ log (n-2 ^ k) + \ dots + \ log (n-2) + \ log (n) \\ & amp; = c + n \ log (n) \ end {align *} $$

    11 July 2012
    GillesTimeless