Rekursion und Big O

Question

Ich habe gearbeitet, durch eine letzte Hausaufgabe Informatik beteiligt Rekursion und Big-O-Notation. Ich glaube, dass ich das verstehe recht gut (sicherlich nicht perfekt, aber!) Aber es ist eine Frage insbesondere, dass mir die meisten Probleme gibt. Das Seltsame ist, dass es von der Suche, es ist die einfachste eines auf den Hausaufgaben aussieht.

Geben Sie die beste Wachstumsrate der Big-Oh-Notation für die Lösung der folgenden Wiederholung mit?

T (1) = 2

T (n) = 2T (n - 1) + 1 für n> 1

Und die Möglichkeiten sind:

• O (n log n)
• O (n ^ 2)
• O (2 ^ n)
• O (n ^ n)

Ich verstehe, dass große O arbeitet als obere Grenze, die meiste Menge von Berechnungen zu beschreiben, oder die höchste Laufzeit, das Programm oder dauert der Prozess. Ich fühle mich wie diese besondere Rekursion sollte O (n) sein, da allenfalls nur die Rekursion für jeden Wert von n einmal auftritt. Da n nicht verfügbar ist, ist es entweder besser als das, O (n log n), oder schlimmer noch, die anderen drei Optionen zu sein.

Also, meine Frage ist: Warum nicht das O (n)

Answer 1

Es gibt ein paar verschiedene Möglichkeiten Rezidive zu lösen: Substitution, Wiederholung Baum und Master-Theorem. Master-Satz wird in dem Fall nicht, weil es nicht die Master-Theorem Form paßt.

Sie könnten die beiden anderen Methoden verwenden, aber der einfachste Weg für dieses Problem ist es iterativ zu lösen.

T (n) = 2T (n-1) + 1 | T (n) = 4T (n-2) + 2 + 1 | T (n) = 8T (n-3) + 4 + 2 + 1 | T (n) = ...

Sehen Sie das Muster?

T (n) = 2 ^n-1 ⋅T (1) + 2 ^n-2 + 2 ^n-3 +. .. + 1 | T (n) = 2 ^n-1 ⋅2 + 2 ^n-2 + 2 ^n-3 + ... + 1
T (n) = 2 ⁿ + 2 ^n-2 + 2 ^n-3 + ... + 1

Daher ist die engste gebunden ist Θ (2 ⁿ ).

Answer 2

Ich glaube, Sie die Frage ein wenig falsch verstanden haben. Es macht Dich nicht fragen, wie lange es dauern würde, um die Wiederholung zu lösen. Es ist zu fragen, was das Big-O (die asymptotische Grenze) der Lösung selbst ist.

Was Sie tun müssen, ist mit einer Lösung in geschlossener Form zu kommen, i. e. die nicht-rekursive Formel für T (n), und dann bestimmen, was die großen O-diesen Ausdruck ist.

Answer 3

Die Frage für die Big-Oh-Notation bittet um die Lösung der Wiederholung, die Wiederholung nicht die Kosten für die Berechnung.

Um es anders auszudrücken: die Wiederholung erzeugt:

  1 -> 2
  2 -> 5
  3 -> 11
  4 -> 23
  5 -> 47

Was big-Oh-Notation beschreibt am besten die Sequenz 2, 5, 11, 23, 47, ...

Die richtige Art und Weise zu lösen, ist die Wiederholung Gleichungen zu lösen.

Answer 4

Ich denke, das exponentielle sein wird. Jeder Schritt auf n macht den Wert doppelt so groß sein.

T(2) = 2 * T(1) = 4
T(3) = 2 * T(2) = 2 * 4
...

T (x) würde die Laufzeit des folgenden Programms (zum Beispiel):

def fn(x):
 if (x == 1):
  return    # a constant time
 # do the calculation for n - 1 twice
 fn(x - 1)
 fn(x - 1)

Answer 5

  

Ich denke, das exponentielle sein wird. Jeder Schritt auf n bringt doppelt so viel Berechnung.

Nein, es funktioniert nicht. Ganz im Gegenteil:

Beachten Sie, dass für n Iterationen, uns Zeit zum Laufen bringen R . Dann gilt für n + 1 Iterationen wir werden genau das bekommen, R + 1.

Damit ist die Wachstumsrate konstant und die Gesamtlaufzeit ist in der Tat O ( n ).

Aber ich denke, Dima Annahme über die Frage richtig ist, obwohl seine Lösung zu kompliziert ist:

  

Was Sie tun müssen, ist mit einer Lösung in geschlossener Form zu kommen, i. e. die nicht-rekursive Formel für T (n), und dann bestimmen, was die großen O-diesen Ausdruck ist.

Es ist ausreichend, um die relative Größe von T ( n ) und T ( n + 1) zu prüfen, Iterationen und die relative Wachstumsrate bestimmen. Die Menge offensichtlich verdoppelt, die direkt das asymptotische Wachstum gibt.

Answer 6

Zunächst einmal alle vier Antworten sind schlechter als O (n) ... O (n * log n) ist komplexer als einfache alte O (n). Was ist größer: 8 oder 8 * 3, 16 oder 16 * 4, etc ...

Auf die eigentliche Frage. Die allgemeine Lösung kann offensichtlich in konstanter Zeit gelöst werden, wenn Sie nicht Rekursion tun

(T (n) = 2 ^ (n - 1) + 2 ^ (n) - 1)., So das ist nicht das, was sie fragen

Und wie Sie sehen können, wenn wir den rekursiven Code schreiben:

int T( int N )
{
    if (N == 1) return 2;
    return( 2*T(N-1) + 1);
}

Es ist offensichtlich O (n).

So scheint es eine schlecht formulierte Frage zu sein, und sie werden Ihnen wahrscheinlich das Wachstum der Funktion selbst, nicht die Komplexität des Codes zu fragen. Das sind 2 ^ n. Gehen Sie jetzt tun, den Rest Ihres Hausaufgaben ... und studieren auf O (n * log n)

Answer 7

Das Berechnen einer Lösung geschlossener Form der Rekursion ist einfach. Durch die Inspektion, erraten Sie, dass die Lösung

T(n) = 3*2^(n-1) - 1

Dann beweisen Sie durch Induktion, dass dies in der Tat ist eine Lösung. Basisfall:

T(1) = 3*2^0 - 1 = 3 - 1 = 2. OK.

Induktion:

Suppose T(n) = 3*2^(n-1) - 1. Then
T(n+1) = 2*T(n) + 1 = 3*2^n - 2 + 1 = 3*2^((n+1)-1) - 1. OK.

, wo die erste Gleichheit von der Wiederholung Definition stammt, und die zweite Hypothese von der induktiven. QED.

3 * 2 ^ (n-1) -. 1 ist deutlich Theta (2 ^ n), also die richtige Antwort ist die dritte

Um die Leute, die O beantwortet (n): Ich konnte nicht mehr mit Dima zustimmen. Das Problem hat nicht fragt die engste obere Schranke an die Rechenkomplexität eines Algorithmus T (n) zu berechnen (die jetzt O wäre (1), da seine geschlossene Form bereitgestellt worden ist). Das Problem stellt für die engste obere Schranke auf T (n) selbst , und das ist die exponentielle eins.