SichtsComplexity Rezidiv
L (n) = 0, wobei n = 1, L (n) = L (n/2) wobei n> 1 a) Finden L (25). b) Was die Komplexität von L. wird
Bitte diese beiden oben genannten Fragen zu beantworten und zu tun illustrieren Ihre Antworten
Es O(logn)
sein wird, wie es n durch 2 geteilt wird. Es läuft ca. logn Schritte vor dem Anhalten.
n->n/2->n/4->n/8..n/2^k...1
so k=log(n)
It will be O(k)~O(logn).
Es ist nicht für ungerade Zahl definiert.
Aber wenn wir Boden auf eine Reihe betrachten, dann wird es sein wie
L(25)=L(12)=L(6)=L(3)=L(1)=0...
Ich würde Ihnen empfehlen, zunächst die Frage zu wissen.
Was meinen Sie mit "die Komplexität von L"? Meinst du "Was ist die Komplexität von L als Funktion?" Oder meinst du "was ist die Zeit (oder Raum) Komplexität von L, wenn es im Code implementiert wäre (zum Beispiel:' def L (n): zurückgeben 0 wenn n == 1 sonst L (n // 2) ') Sind wir davon ausgegangen, '/' ist Abschneidung Division? –
L (n) = 0 für alle n –