Dies ist eine Frage aus einer der alten Prüfungen zu Algorithmen und Datenstruktur, auf die ich kürzlich gestoßen bin. Es fällt mir schwer, die Lösung zu verstehen. Ich muss big-O, big-ϴ und big-Ω Grenzen einer Funktion finden:

void recursion(int n) {
 int i;
 if (n == 0) {
 return;
 }
 for (i = 0; i < n; i++) {
 recursion(i);
 }
}

Die Lösung ist 2^n für alle drei und ich kann nicht verstehen warum. Ich habe versucht, Dinge aufzuschreiben, und ich kann der Lösung nicht einmal nahe kommen. Ich würde mich freuen, wenn jemand erklären würde, woher das 2^n von hier kommt.

1
randomuser 18 Apr. 2018 im 00:57

3 Antworten

Beste Antwort

Schauen wir uns eine einfachere Rekursion an, die als O (2 ^ n) bekannt ist.

void fib(int n) {
    if (n < 3) {
        return 1;
    } else {
        return fib(n - 1) + fib(n - 2);
    }
}

Hier können Sie sehen, dass für den nicht trivialen Fall von n> 2 dies zu 2 ^ (n-2) Aufrufen für sich selbst führt. Zum Beispiel, wenn n = 5:

n = 5
    n = 4
        n = 3
            n = 2
            n = 1
        n = 2
    n = 3
        n = 2
        n = 1

Es gibt 8 (2 ^ 3) rekursive Aufrufe, da jeder Aufruf mit n> 2 zwei weitere rekursive Aufrufe erzeugt, sodass fib (n + 1) doppelt so viele rekursive Aufrufe hat wie fib (n).

Also für Ihr Beispiel:

n = 3
    n = 2
        n = 1
            n = 0
        n = 0
    n = 1
        n = 0
    n = 0

Wir erhalten also 7 rekursive Aufrufe, wenn n = 3 ist

Für n = 4

n = 4
    n = 3
        n = 2
            n = 1
                n = 0
            n = 0
        n = 1
            n = 0
        n = 0
    n = 2
        n = 1
            n = 0
        n = 0
    n = 1
        n = 0
    n = 0

Hier haben wir 15 Anrufe. Wenn Sie sich den Ausführungsbaum oben ansehen, sehen Sie, dass Rekursion (4) im Grunde Rekursion (3) + Rekursion (3) + 1 ist

n = 4
    n = 3          // + 1
        n = 2                //
            n = 1            //
                n = 0        // recursion(3)
            n = 0            //
        n = 1                //
            n = 0            //
        n = 0                //
    n = 2           //
        n = 1       //
            n = 0   // recursion(3)
        n = 0       //
    n = 1           //
        n = 0       //
    n = 0           //

Im Allgemeinen hat die Rekursion (n + 1) einen rekursiveren Aufruf als die 2 * Rekursion (n) .... was sich im Grunde für jede +1 bis n verdoppelt .... was O (2 ^ n) ist.

2
Stephen Docy 18 Apr. 2018 im 03:25

Bezeichnen wir die Gesamtlaufzeit als f(n). Aufgrund der Schleife in der Funktion ist f(n) tatsächlich eine Summe von f(i) für i zwischen 0 und n-1. Das ist eine Summe von n Elementen. Versuchen wir, den Ausdruck zu vereinfachen. Ein Standardtrick in solchen Situationen besteht darin, eine komplementäre Gleichung zu finden. Mal sehen, was der Wert von f(n-1) ist. Ähnlich wie im vorherigen Fall ist es eine Summe von f(i) für i zwischen 0 und n-2. Jetzt haben wir also zwei Gleichungen:

f(n)=f(1)+...+f(n-1)
f(n-1)=f(1)+...+f(n-2)

Subtrahieren wir die Sekunde von der ersten:

f(n)-f(n-1)=f(n-1)
--> f(n)=2f(n-1)

Dies ist nun eine homogene lineare Wiederholungsbeziehung mit konstanten Koeffizienten. Die Lösung ist sofort verfügbar (siehe den Link für weitere Details):

f (n) = f (1) * 2 n = 2 n

2
SomeWittyUsername 17 Apr. 2018 im 22:34
r(n)   = r(n-1)+r(n-2)+...+r(0) // n calls.
r(n-1) = r(n-2)+r(n-3)+...+r(0) // n-1 calls.
r(n-2) = r(n-3)+r(n-4)+...+r(0) // n-2 calls.
.
.
.
r(1)   = r(0)                   // 1 call.
r(0)   = return;                // 0 call.

So,

r(n)   = r(n-1)+r(n-2)+...+r(0)         // n calls.
       = 2 * (r(n-2)+...+r(0))          // 2 * (n - 1) calls.
       = 2 * ( 2 * (r(n-3)+...+r(0)) )  // 2 * 2 * (n - 2) calls.
.
.
.

Daraus folgt =>

2^(n-1) * (n - (n-1))

Und das wäre

2^n calls...
1
user7340499user7340499 18 Apr. 2018 im 06:54