Laufzeit

[algo777]

Hallo,

ich soll mittels einer Laufzeit von O(n) das Maximum in einem Array bestimmen und bin dabei auf folgende Lösung gekommen:

		int max = 0;
		
		for (int i=0; i<input.length-1; i++)
		{
			if (input[i] > max)
				max = input[i];
		}

Hierbei werden also maximal n (Länge des Array) Vergleiche angestellt. Oder muss ich jede Zuweisung dazuaddieren/multiplizieren:

max = input[i]

auch als weiteren Schritt hinzuzählen? Kann mir jemand geeignete Websites empfehlen zur Komplexität und Laufzeit von Algorithmen?

Gruß

 

[turtle]

Komplexitätstheorie

 

[Marcinek]

Ja das ist korrekt.

Zwar müssten hier die einzelenen Vergleiche berücksichtigt werden, aber da sich bei der O-Notation um Mengen handelt, ist O(4n) = O(n) also O(4n) ist Teilmenge von O(n).

 

[algo777]

Darf ich fragen wie du auf O(4n) kommst?

 

[Firephoenix]

Für jedes Element wird im worst-case

1. i mit der Länge verglichen
2. i um 1 erhöht
3. max mit einem element verglichen
4. ein neuer wert an max zugewiesen

zählt man nur die Operationen kommt man auf 4 (intern sind es vermutlich eh mehr, die zuweisung dürfte in einem anderem rahmen liegen als das kleiner - ist aber dank O-Notation ja eh egal)
Gruß

 

[hüteüberhüte]

Ich komme auch auf n

Ifs (bedingte Anweisungen/Verzweigungen) zählen nicht, und es wird immer angenommen, dass sie true sind

Eine Zuweisung zählt als eine Operation

Die Schleife wir n-mal ausgeführt

Dann ergibt sich O(n*1)=O(n)

Btw. O(n*k) ist O(n), wenn k eine Konstante ist

[EDIT]Mit Zeile 1 O(n*1+1)=O(n)[/EDIT]

 

[hüteüberhüte]

Für jedes Element wird im worst-case

1. i mit der Länge verglichen
2. i um 1 erhöht
3. max mit einem element verglichen
4. ein neuer wert an max zugewiesen

zählt man nur die Operationen kommt man auf 4 (intern sind es vermutlich eh mehr, die zuweisung dürfte in einem anderem rahmen liegen als das kleiner - ist aber dank O-Notation ja eh egal)
Gruß

Das ist leider falsch. Nur Punkt 4 (die Zuweisung) zählt als eine Operation. Vergleiche zählt nicht, das Hochzählen der Zählervariable auch nicht

[EDIT]Prinzipiell kann Zeile 1 auch als eine Operation zählen[/EDIT]

 

[Marcinek]

Also meine 4 habe ich einfach so gewählt ohne Bezug zur Aufgabe.

Aber dennoch müssen hier ALLE Operationen gezählt werden.

Allein schon: Wieso soll "punkt 4" als Zuweisung zählen aber i++ nicht???

 

[Firephoenix]

Haut mich, das war ungenau

Trotzdem arbeitet der Algorythmus in O(n) denn Konstanten fliegen bei der Betrachtungsweise raus.

Gruß

 

[Marco13]

Man kann dabei zählen, was man will. Manchmal sind's nur die Multiplikationen, manchmal Vergleiche, manchmal Vertauschungen...

 

[hüteüberhüte]

Man kann dabei zählen, was man will. Manchmal sind's nur die Multiplikationen, manchmal Vergleiche, manchmal Vertauschungen...

Es kommt auf die Definition an

        int max = 0; // 1
        
        for (int i=0; i<input.length-1; i++) // 1+n+n
        {
            if (input[i] > max) // 1
                max = input[i]; // 1
        }

= 1+1+n+n+n(1+1) = 2+2n+2n = 2+4n = O(n) würde keiner rechnen. Wenn man es schon genau haben will, müsste man den Bytecode und was letztendlich vom Prozessor ausgeführt wird, angucken. Macht man aber net

Thema fertig?

 

[Marco13]

Es geht ja nur um die asymptotische Laufzeit, bzw. die asymptotische Anzahl der benötigten Vergleiche (in diesem Fall). Die ist für die Maximumssuche immer gleich, egal ob man eine Turingmaschine mit Brain**** oder eine JVM (Kellerautomat) mit Java Bytecode programmiert. Aber es stimmt, man kann da schnell ist philosophieren kommen