Finden der zeitlichen Komplexität eines Exponentialalgorithmus

Question

Problem: Finden Sie die beste Möglichkeit, eine Stange der Länge zu schneiden n Jeder Schnitt ist Integerlänge Nehmen Sie an, dass jede Länge i Stab hat einen Preis p (i) Gegeben: Stab der Länge n und eine Liste von Preisen p, die den Preis für jede mögliche ganze Zahl zwischen 0 und n angibt.

Finden Sie den besten Satz von Schnitten, um den Höchstpreis zu erhalten Kann eine beliebige Anzahl von Schnitten verwenden, von 0 bis n-1 Es gibt keine Kosten für einen Schnitt.

Nachstehend präsentiere ich einen naiven Algorithmus für dieses Problem.

CUT-ROD(p,n) 
if(n == 0) 
    return 0 
q = -infinity 
for i = 1 to n 
    q = max(q, p[i]+CUT-ROD(p,n-1)) 
return q 

Wie kann ich beweisen, dass dieser Algorithmus exponentiell ist? Schritt für Schritt. Ich kann sehen, dass es exponentiell ist. Ich kann es jedoch nicht beweisen.

Answer 1

Lassen Sie uns den Code in C++ für Klarheit übersetzen:

int prices[n]; 
int cut-rod(int n) { 
    if(n == 0) { 
    return 0; 
    } 
    q = -1; 
    res = cut-rod(n-1); 
    for(int i = 0; i < n; i++) { 
    q = max(q, prices[i] + res); 
    } 
    return q; 
} 

Anmerkung: Wir sind das Caching das Ergebnis of cut-rod(n-1) unnötig zu vermeiden, dass die Komplexität des Algorithmus zu erhöhen. Hier können wir sehen, dass cut-rod(n) ruft cut-rod(n-1), die cut-rod(n-2) und so weiter auf cut-rod(0) ruft. Für cut-rod(n) sehen wir, dass die Funktion über das Array n mal iteriert. Daher ist die Zeitkomplexität des Algorithmus gleich O(n + (n-1) + (n-2) + (n-3)...1) = O(n(n+1)/2), was ungefähr gleich O((n^2)/2) ist.

EDIT: Wenn wir den exakt gleichen Algorithmus wie der in der Frage verwenden, seine Zeitkomplexität O (n!), Da Schnitt Stange (n) nennen Schnitt Stange (n-1) n mal. Cut-Rod (n-1) ruft Cut-Rod (n-2) n-1 mal und so weiter. Daher ist die Zeitkomplexität gleich O (n * (n-1) * (n-2) ... 1) = O (n!).