Algorithmus, um einen Ausdruck zu begrenzen, um seinen Wert zu maximieren

8

Ich habe dies beim Nachschlagen von Problemen bei der dynamischen Programmierung gefunden. Sie erhalten einen nicht-bewertbaren Ausdruck der Form V0 O0 V1 O1 .... Vn-1

Wir müssen Klammern an Stellen setzen, die den Wert des gesamten Ausdrucks maximieren.

V sind die Operanden und O sind die Operatoren. In der ersten Version von Problemoperatoren können * und + und Operanden positiv sein. Die zweite Version des Problems ist völlig allgemein.

Für die erste Version habe ich eine DP-Lösung entwickelt.

Lösung - A [] = Operanden-Array B [] - Operatoren Array T (A [i, j]) - Maximalwert des Ausdrucks  T (A [0, n-1]) = max über alle i {(T (A [0, i]) OiT (A [i + 1, n-1]))}

Die Grenzfälle sind trivial (wenn i = j). Ich brauche Hilfe bei folgenden - Analysieren Sie die Laufzeit dieses Algorithmus. Und wenn es ein besseres gibt.

    
Nitin Garg 06.11.2011, 04:35
quelle

1 Antwort

4

Es ist einfacher, die Berechnung von A[i,j] -Elementen von kürzeren Bereichen zu längeren Bereichen zu analysieren. Der Algorithmus sieht so aus:

%Vor%

Da A[] mit einem konstanten Zeitzugriff (Array) implementiert werden kann, ist der Algorithmus O(n^3) .

    
Ante 06.11.2011, 10:16
quelle

Tags und Links

Django: Verwenden von Annotate, Count und Distinct in einem Queryset Hinzufügen eines Scheines zu 3 Seiten mit CSS