Laufzeit mit Big Θ Notation

Question

def filter(f, lst):  
    if lst == []: return [] 
    if f(lst[0]): return [lst[0]] + filter(f, lst[1:]) 
    return filter(f, lst[1:]) 

def my_reverse(lst):  # Reverse the list 
    def reverse_helper(x,y): 
     if x == []: return y 
     return reverse_helper(x[1:], [x[0]] + y) 
    return reverse_helper(lst, []) 

def revfilter_alpha(f, lst): # Reverse and filter ... 
    return my_reverse(filter(f, lst)) 

def revfilter_beta(f, lst): # Reverse and filter ... 
    if lst == []: return [] 
    return revfilter_beta(f, lst[1:]) + ([lst[0]] if f(lst[0]) else []) 

Kann mir jemand erklären, wie man die Laufzeit in Big Θ Notation für diese bestimmen kann? Ich habe einiges gelesen, habe aber noch keine Ahnung, wo ich anfangen soll.

In filter, ich denke, es ist Θ (n^2), weil es jedes Element in der Liste der Größe n mit der Prädikatfunktion f mit n rekursiven Aufrufen so n * n überprüft.

revfilter_beta sieht sehr ähnlich aus, nur während der Filterung umgekehrt, also wäre das nicht auch Θ (n^2)?

revfilter_alpha filtert dann eine Umkehr, also wäre das nicht n^2 * n^2 = ∞ (n^4)?

Hat jemand irgendwelche Gedanken?

Answer 1

filter hat n rekursive Aufrufe, aber Sie tun auch eine Kopieroperation bei jeder Iteration, die n dauert, so dass Sie am Ende Θ (n^2) haben. Wenn Sie es "richtig" implementiert haben, sollte es Θ (n) sein.

Dasselbe gilt für my_reverse.

Dasselbe gilt für revfilter_beta.

revfilter_alpha macht genau eine filter und dann ein reverse, damit ist, Θ (n^2 + n^2) = Θ (n^2).

---

EDIT: Lassen Sie uns einen Blick in filter ein bisschen mehr.

Was Sie herausfinden möchten, ist, wie viele Operationen relativ zur Größe der Eingabe durchgeführt werden. O(n) bedeutet, dass im schlimmsten Fall in der Größenordnung von n Operationen durchgeführt werden. Ich sage "in der Größenordnung von", weil Sie zum Beispiel O(n/2) Operationen oder O(4n) tun können, aber der wichtigste Faktor ist n. Das heißt, wenn n wächst, wird der konstante Faktor immer weniger wichtig, so dass wir nur den nichtkonstanten Faktor betrachten (n in diesem Fall).

Also, wie viele Operationen führt filter auf einer Liste der Größe n?

Nehmen wir es von unten nach oben. Was ist, wenn n 0 ist - eine leere Liste? Dann wird nur eine leere Liste zurückgegeben. Sagen wir mal, das ist 1 Operation.

Was ist, wenn n 1 ist? Es wird geprüft, ob lst[0] enthalten sein sollte - diese Prüfung dauert so lange, bis f aufgerufen wird - und dann wird der Rest der Liste kopiert und ein rekursiver Aufruf dieser Kopie ausgeführt, was in diesem Fall eine leere Liste ist. so filter(1) dauert f + copy(0) + filter(0) Operationen, wobei copy(n) ist, wie lange es dauert, um eine Liste zu kopieren, und f ist, wie lange es dauert zu prüfen, ob ein Element enthalten sein sollte, vorausgesetzt, es dauert die gleiche Zeit für jedes Element.

Was ist mit filter(2)? Es wird 1 überprüfen, dann kopieren Sie den Rest der Liste und rufen Sie filter auf den Rest: f + copy(1) + filter(1).

Sie können das Muster bereits sehen.filter(n) dauert 1 + copy(n-1) + filter(n-1).

Jetzt copy(n) ist nur n - es dauert n Operationen, die Liste auf diese Weise zu schneiden. So können wir weiter vereinfachen: filter(n) = f + n-1 + filter(n-1).

Jetzt können Sie versuchen, erweitern gerade filter(n-1) ein paar Mal, um zu sehen, was passiert:

filter(n) = f + n-1 + filter(n-1) 
      = 1 + n-1 + (f + n-2 + filter(n-2)) 
      = f + n-1 + f + n-2 + filter(n-2) 
      = 2f + 2n-3 + filter(n-2) 
      = 2f + 2n-3 + (f + n-3 + filter(n-3)) 
      = 3f + 3n-6 + filter(n-3) 
      = 3f + 3n-6 + (f + n-4 + filter(n-4)) 
      = 4f + 4n-10 + filter(n-4) 
      = 5f + 5n-15 + filter(n-5) 
      ... 

Können wir für x Wiederholungen verallgemeinern? Die 1, 3, 6, 10, 15 ... Sequenz ist die Dreieckszahlen - das heißt, 1, 1+2, 1+2+3, 1+2+3+4 usw. Die Summe aller Zahlen 1-x ist x*(x-1)/2.

  = x*f + x*n - x*(x-1)/2 + filter(n-x) 

Nun, was ist x? Wie viele Wiederholungen werden wir haben? Nun, Sie können sehen, dass, wenn x = n, Sie keine Rekursion mehr haben - filter(n-n) = filter(0) = 1. So ist unsere Formel ist jetzt:

filter(n) = n*f + n*n - n*(n-1)/2 + 1 

Was wir weiter vereinfachen:

filter(n) = n*f + n^2 - (n^2 - n)/2 + 1 
      = n*f + n^2 - n^2/2 + n/2 + 1 
      = n^2 - n^2/2 + f*n + n/2 + 1 
      = (1/2)n^2 + (f + 1/2)n + 1 

So gibt ya haben es - eine ziemlich detaillierte Analyse. Das wäre Θ((1/2)n^2 + (f + 1/2)n + 1) ... unter der Annahme, f ist unbedeutend (etwa f = 1), dass zu Θ((1/2)n^2 + (3/2)n + 1) bekommt.

Sie werden nun feststellen, ob copy(n) eine konstante Menge an Zeit statt eine Menge an Zeit linear nahmen (wenn copy(n) 1 statt n sind), dann würden Sie da nicht, dass n^2 Begriff bekommen.

Ich gebe zu, wenn ich anfangs Θ(n^2) gesagt habe, habe ich das nicht alles in meinem Kopf getan. Stattdessen dachte ich: ok, Sie haben n rekursive Schritte, und jeder Schritt dauert n Menge an Zeit wegen der copy. n*n = n^2, also Θ(n^2). Um das zu tun ein bisschen genauer, n bei jedem Schritt schrumpft, so dass Sie wirklich n + (n-1) + (n-2) + (n-3) + ... + 1 haben, die endet als die gleiche Figur wie oben: n*n - (1 + 2 + 3 + ... + n) = n*n - n*(n-1)/2 = (1/2)n^2 + (1/2)n, die die gleiche ist, wenn ich 0 statt f benutzt hatte, oben . Ebenso, wenn Sie n Schritte hatten, aber jeder Schritt dauerte 1 anstelle von n (wenn Sie die Liste nicht kopieren mussten), dann hätten Sie 1 + 1 + 1 + ... + 1, n mal, oder einfach n.

Aber das erfordert ein bisschen mehr Intuition, also dachte ich, ich würde Ihnen auch die Brute-Force-Methode zeigen, die Sie auf alles anwenden können.

Answer 2

Alle Ihre Funktionen sind O(N^2), weil sie O(N) Zeit pro rekursiv Schritt nehmen und es wird N Schritte auf einer Liste der Länge N sein.

Es gibt zwei teure (also O(N)) Operationen, die Sie in Ihren Funktionen ausführen. Das erste ist Schneiden (z. B. lst[1:]). Die zweite ist eine Listenverkettung (unter Verwendung des Operators +).

Diese beiden sind möglicherweise teurer, als Sie erwarten, vor allem weil Pythons Listen nicht wie Listendatentypen in anderen Sprachen sind. Unter der Haube sind das Arrays, keine verketteten Listen. Es ist möglich, die obigen Operationen auf verknüpften Listen in O (1) -Zeit durchzuführen (obwohl O(1) Schneiden destruktiv ist). In Lisp zum Beispiel wären die von Ihnen verwendeten Algorithmen O(N) und nicht O(N^2).

Rekursion ist in Python oft auch nicht optimal, weil es keine tail call elimination gibt. Pythons Standard-Rekursionsbegrenzung ist 1000 in neueren Versionen, so lange Listen brechen rein rekursive Lösungen, wenn Sie im Modul sys herumspielen, um das Limit zu erhöhen.

Es ist möglich, eine O(N) Version dieser Algorithmen auch in Python zu tun, aber Sie sollten die oben genannten teuren Listenoperationen so weit wie möglich vermeiden. Anstatt Rekursion, schlage ich vor, Generatoren zu verwenden, die ein sehr viel "pythonischer" Programmierstil sind.

Filtern mit einem Generator ist sehr einfach zu tun. Der eingebaute in filter Funktion tut es bereits, aber Sie können Ihre eigene in nur wenigen Zeilen schreiben:

def my_filter(f, iterable): 
    for e in iterable: 
     if f(e): 
      yield e 

Umkehrung der Ordnung der Dinge ist ein wenig komplizierter, da Sie entweder müssen in der Lage zufällig zu tun Zugriff auf die Quelle oder verwenden Sie O(N) zusätzlichen Speicherplatz (Ihr Algorithmus verwendet den Stapel für diesen Speicherplatz, obwohl Listen dem Sequenzprotokoll folgen und nach dem Zufallsprinzip zugegriffen werden kann). Der eingebaute in reversed Funktion funktioniert nur auf Sequenzen, aber hier ist eine Version, die auf jedem iterable (wie ein anderer Generator) arbeitet:

def my_reversed(iterable): 
    storage = list(iterable) # consumes all the input! 
    for i in range(len(storage)-1, -1, -1): 
     yield storage[i] 

Beachten Sie, dass im Gegensatz zu vielen Generatoren, dies sofort auf Verbraucht alle seine Eingabe vor Es fängt an, Leistung zu erbringen. Führe es nicht auf einem unendlichen Eingang!

Sie können diese in beliebiger Reihenfolge zusammensetzen, und my_reversed(filter(f, lst)) sollte filter(f, my_reversed(lst)) entsprechen (obwohl für die Letzteren, die eingebaute reversed Funktion wahrscheinlich besser ist).

Laufzeit für beide oben genannten Generatoren (und ihre Zusammensetzung in jeder Reihenfolge) wird O(N) sein.