Zeit Komplexität der Textausrichtung mit dynamischer Programmierung

Question

Ich habe an einem dynamic programming problem involving the justification of text gearbeitet. Ich glaube, dass ich eine funktionierende Lösung gefunden habe, aber ich bin verwirrt bezüglich der Laufzeit dieses Algorithmus.

Die Forschung I bisher getan hat für dieses Problem, wie O (N^2) mitN als die Länge des Textes dynamische Programmierlösungen beschrieben, das gerechtfertigt wird. Für mich fühlt sich das falsch an: Ich kann sehen, dass O (N) -Aufrufe gemacht werden müssen, da es N Suffixe gibt, die überprüft werden sollen, aber wir werden nie überlegen, den Newline (oder "Split_point") über die maximale Linie hinaus zu setzen Länge L. Daher gibt es für jeden gegebenen Text höchstens L Positionen zum Platzieren des Splitpunkts (dies setzt den schlimmsten Fall voraus: dass jedes Wort genau ein Zeichen lang ist). Wird dieser Algorithmus wegen dieser Erkenntnis nicht genauer als O (LN) beschrieben?

@memoize 
def justify(text, line_length): 

    # If the text is less than the line length, do not split 
    if len(' '.join(text)) < line_length: 
     return [], math.pow(line_length - len(' '.join(text)), 3) 

    best_cost, best_splits = sys.maxsize, [] 

    # Iterate over text and consider putting split between each word 
    for split_point in range(1, len(text)): 
     length = len(' '.join(text[:split_point])) 

     # This split exceeded maximum line length: all future split points unacceptable 
     if length > line_length: 
      break 

     # Recursively compute the best split points of text after this point 
     future_splits, future_cost = justify(text[split_point:], line_length) 
     cost = math.pow(line_length - length, 3) + future_cost 

     if cost < best_cost: 
      best_cost = cost 
      best_splits = [split_point] + [split_point + n for n in future_splits] 

    return best_splits, best_cost 

Vielen Dank im Voraus für Ihre Hilfe, Ethan

Answer 1

Zu allererst Ihre Implementierung weit, weit von der theoretischen Effizienz, die Sie wollen sein wird. Sie stellen eine Zeichenfolge der Länge N in Ihrem Aufruf fest, was bedeutet, dass die Suche nach einer zwischengespeicherten Kopie Ihrer Daten möglicherweise O(N) ist. Starten Sie jetzt mehrere zwischengespeicherte Anrufe, und Sie haben Ihr Komplexitätsbudget aufgebraucht.

Dies ist fixierbar, indem Sie den Text außerhalb des Funktionsaufrufs verschieben und nur den Index der Startposition und die Länge L übergeben. Sie machen auch einen Join innerhalb Ihrer Schleife, die eine O(L) Operation ist. Mit etwas Sorgfalt können Sie stattdessen eine O(1) Operation machen.

Mit diesem Schritt würden Sie O(N*L) Operationen tun. Aus genau den Gründen, die Sie dachten.