Janus
09.08.2005, 15:25
Hallo...ich hätte da ein paar Fragen.
1.) Was bedeutet der Begriff polynomiale Zeit? Ich weiß was ein Polynom ist aber was ist eine polynomiale Zeit? Ist sie endlich?
2.)
Wir haben im Skript einen Algorithmus konzipiert der mir allerdings nciht ganz klar ist:
geg.: Folge a aus n ganzen Zahlen
ges.. größte Summe aus aufeinander folgenden Zahlen
z.b.: 4,-3,4,-6,4......n = 5
//sum = Summe aller Elemente von 1 bis i
//low = bisheriges Minimum von sum
max = 0, sum = 0; low = 0
for(i = 1...n){
sum = sum + a[i]
if(sum < low) {low = sum}
if(sum-low>max){max=sum-low} //hier liegt meines Erachtens der //Fehler...statt - gehört ein + gesetzt
}
O(n)
Wenn ich jetzt das Beispiel von oben auf den Algorithmus anwende kommt 6 heraus statt 5....Hab ich mich vertan oder stimmt der Algorithmus wirklich nicht?
mfg,
Janus
1.) Was bedeutet der Begriff polynomiale Zeit? Ich weiß was ein Polynom ist aber was ist eine polynomiale Zeit? Ist sie endlich?
2.)
Wir haben im Skript einen Algorithmus konzipiert der mir allerdings nciht ganz klar ist:
geg.: Folge a aus n ganzen Zahlen
ges.. größte Summe aus aufeinander folgenden Zahlen
z.b.: 4,-3,4,-6,4......n = 5
//sum = Summe aller Elemente von 1 bis i
//low = bisheriges Minimum von sum
max = 0, sum = 0; low = 0
for(i = 1...n){
sum = sum + a[i]
if(sum < low) {low = sum}
if(sum-low>max){max=sum-low} //hier liegt meines Erachtens der //Fehler...statt - gehört ein + gesetzt
}
O(n)
Wenn ich jetzt das Beispiel von oben auf den Algorithmus anwende kommt 6 heraus statt 5....Hab ich mich vertan oder stimmt der Algorithmus wirklich nicht?
mfg,
Janus