Ich möchte die Zeit Komplexität in Big O des folgenden Codes finden:Zeitkomplexität eines rekursiven Reverse-String
ReverseString(S,x,y)
if x < y
swap(S,x,y)
return ReverseString(S,x+1,y-1)
Die Gleichung ich erhielt, war
T(1) = 1
T(n) = 3 + T(n+1)+ T(n-1)
Wenn ich Recht habe, wie Würde ich das Problem lösen?
Wenn ich nicht richtig bin, was ist die richtige Gleichung.
Angenommen, dass x und y Zeiger auf Ende der Zeichenfolge sind, dann ist Ihre Gleichung falsch. Dies ist eine einfache, einfache Rekursion, aber du hast angenommen, dass es doppelt ist. Außerdem gibt es das ernsthafte Problem, T (n) von T (n + 1) abhängig zu machen; Sie wollen wirklich nicht gehen bis in Indizes ohne eine garantierte, begrenzte begrenzte Abnahme.
Denken Sie so: Jede Iteration nähert sich x und y um jeweils ein Zeichen an jedem Ende. Ihre einzelne Rekursion durchläuft die Hälften der Zeichenfolge. Ich würde die Beziehung als
T(n) = 3 + T(n-1)
setzen, wobei n die halbe Länge der Zeichenfolge ist (abgeschnitten wenn ungerade).
Ich bin nicht sicher, was Ihr T (n) ist - Komplexität für eine Zeichenfolge der Länge n? Warum sollte T (n) von der Komplexität eines längeren Strings abhängen? Der Sinn dieser Methode ist, dass x bei 0 beginnt und zur Mitte hin zunimmt und y am Ende beginnt und zur Mitte hin abnimmt. Naiv, diese Methode führt die Saite einmal durch, wobei sie die Hälfte der Länge der (aufgerundeten) Iterationen verwendet, also sollte die Reihenfolge von n sein, nicht wahr? – Rup
T (n) ist die Standardaufgabennotation für Wiederholungsrelationen. – Prune