Big-O-Notation für zwei einfache rekursive Funktionen

Verwenden wir Wiederholungsrelationen, um das zu lösen! Die Laufzeit der ersten Funktion kann rekursiv als

  

T (0) = 1

     

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

Das bedeutet, dass der Basisfall eine Zeiteinheit benötigt, um abgeschlossen zu werden, und andernfalls machen wir zwei rekursive Aufrufe an kleinere Instanzen des Problems und führen einige Setup- und Bereinigungsarbeiten durch. Wenn wir einige Begriffe in dieser Wiederholung ausdehnen, erhalten wir

• T (0) = 1
• T (1) = 2T (0) + 1 = 2 + 1 = 3
• T (2) = 2T (1) + 1 = 2 × 3 + 1 = 7
• T (3) = 2T (2) + 1 = 2 × 7 + 1 = 15

Diese Serien 1, 3, 7, 15, ... könnten Ihnen bekannt vorkommen, da es 2 ¹ - 1, 2 ² - 1, 2 ^{ist 3} - 1 usw. Allgemein können wir das beweisen

  

T (n) = 2 ^{n + 1} - 1

Wir können dies durch Induktion tun. Als unser Grundfall gilt T (0) = 1 = 2 <1> - 1, also gilt der Anspruch für n = 0. Nehmen wir nun an, dass für einige n gilt: T (n) = 2 ^{n +1} - 1. Dann haben wir das

  

T (n + 1) = 2T (n) + 1 = 2 (2n + 1 <- 1) + 1 = 2 ^{n + 2} - 2 + 1 = 2 ^{n + 2} - 1

Und wir sind fertig! Da diese Wiederholung zu 2 ^{n + 1} - 1 = 2 (2 ⁿ ) - 1 führt, haben wir die Laufzeit Θ (2 ⁿ ).

Die Laufzeit der zweiten Funktion kann rekursiv als

  

T (0) = 1

     

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

Einige Begriffe erweitern:

• T (0) = 1
• T (1) = T (0) + 1 = 1 + 1 = 2
• T (2) = T (1) + 1 = 2 + 1 = 3
• T (3) = T (2) + 1 = 3 + 1 = 4

Dies ergibt 1, 2, 3, 4, ..., also könnten wir das im allgemeinen raten.

  

T (n) = n + 1

Wir können das wieder induktiv beweisen. Wenn n = 0 ist, gilt als Grundfall T (0) = 1 = 0 + 1. Für den induktiven Schritt sei angenommen, dass für einige n gilt: T (n) = n + 1. Dann

  

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

Und wir sind fertig! Da die Laufzeit n + 1 ist, ist die Laufzeit Θ (n).

Hoffe, das hilft!

Suchen von Kosten mithilfe eines Rekursionsbaums (über ein visuelles Diagramm).

Wiederholungsrelation der Funktion cost (n)

Ähnlich können wir die zeitliche Komplexität der zweiten Funktion finden.