• Wir präsentieren Dir heute ein Stellenangebot für einen Java Entwickler - m/w/d in Augsburg, München, Stuttgart oder Bamberg. Hier geht es zur Jobanzeige

Laufzeitberechnung - dringende Hilfe!

N

NoSkills

Neues Mitglied
Hallo,

wie berechnet man eigentlich die Laufzeit von Algirthmen?
Ich meine gut, ich weiß irgendwas mit O(n) und so weiter, aber kann man das selbst nicht auch ausrechnen?
Welche Methoden gibt es dafür?
 
mihe7

mihe7

Top Contributor
Grundsätzlich sucht man Schranken für die Anzahl an im Algorithmus durchgeführten Elementarschritten. Wenn Du auf sehr niedriger Ebene und formal arbeiten willst, dann stellst Du eine Schrittzahlfunktion auf und beschreibt deren Wachstum mit Hilfe der Landau-Symbole (O-Notation).

Beispiel zur Bestimmung des letzten Vorkommens eines Zeichens in einem char-Array:
Java:
public int lastIndexOf(char[] txt, char c) {
    int pos = txt.length - 1;
    while (pos >= 0) {
        if (txt[pos] == c) {
            break;
        }
        pos--;
    }
    return pos;
}

Frage: wie ist die Laufzeit im schlechtesen Fall (worst case) in Abhängigkeit der Textlänge n?

Formal müsstest Du jetzt eine Schrittzahlfunktion SZ(n) aufstellen (und ggf. Korrektheit beweisen). In Zeile 2 wird die initiale Position gesetzt, macht einen Schritt. In Zeile 3 folgt ein Vergleich als weiterer Schritt, Zeile 4 ein weiterer Vergleich und damit weiterer Schritt, dann geht es weiter mit Zeile 7 (worst case), dann zurück zu 3 usw.

Bei jeder Iteration der Schleife werden also drei Schritte ausgeführt, die Schleife wird n-mal durchlaufen. Wenn die Schleife terminiert, erfolgt nochmal ein Vergleich in Zeile 3. In Zeile 9 noch ein Schritt für die Rückgabe (sofern man die zählen will), macht insgesamt SZ(n) = 1 + 3n + 1 + 1 = 3 + 3n. Die Schrittzahlfunktion wächst nicht wesentlich schneller als n, somit liegt die Laufzeit in O(n). Formal heißt das, dass positive Konstanten C und x0 existieren, so dass für alle x > x0 gilt: |SZ(x)| = |3+3x| = 3+3x ≤ Cx. Das ist z. B. für x0=2 und C=4 der Fall.

Etwas mehr an der Praxis orientiert: Zeile 1 ist konstant: O(1), Schleife in den Zeilen 3 bis 8 läuft über alle n Zeichen, in der Schleife gibt es nur konstante Laufzeiten, also liegt die Laufzeit der Schleife in O(n). Beim return passiert nix aufregendes, also O(1), macht O(1) + O(n) + O(1) = O(n).

Dann würde mir noch die Reduktion einfallen. Damit kann z. B. die untere Schranke eines Algorithmus angegeben werden, indem man ein Problem mit bekannter unterer Schranke auf das betrachtete reduziert. Damit können nicht nur einzelne Algorithmen sondern komplette Probleme behandelt werden.
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
D OOP Hilfe zu Übung Laufzeitberechnung in Big O Java Basics - Anfänger-Themen 2
K Laufzeitberechnung Java Basics - Anfänger-Themen 5
A Laufzeitberechnung von Algorithmus Java Basics - Anfänger-Themen 4
B BITTE!! Ich brauche dringende Hilfe bei einer Aufgabe Java Basics - Anfänger-Themen 17
T Datentypen brauche dringende hilfe!dezi in Asci umwandeln! Java Basics - Anfänger-Themen 4
A Dringende Bitte um Erklärungen zum besseren Verständnis Java Basics - Anfänger-Themen 4
N Brauche dringende Hilfe Java Aplett läuft nicht! Java Basics - Anfänger-Themen 3
C eine dringende bitte an alle java-programmierer Java Basics - Anfänger-Themen 4
G dringende frage zu klassen und methoden ( klassendiagramm) Java Basics - Anfänger-Themen 19
G Dringende Frage bzgl. meines Codes Java Basics - Anfänger-Themen 30
Leo0909 Ich brauche Hilfe bei dieser Aufgabe Java Basics - Anfänger-Themen 2
D Hilfe beim Erzeugen eines Arrays NullPointerException wird ausgelöst Java Basics - Anfänger-Themen 11
J Doppelt verkette Liste ich bitte um Hilfe Java Basics - Anfänger-Themen 4
G Java Hilfe Java Basics - Anfänger-Themen 3
J Java List, Bitte um Hilfe Java Basics - Anfänger-Themen 15
J Java List, bitte um Hilfe Java Basics - Anfänger-Themen 3
U anfänger braucht hilfe . wir konnten die aufgaben nicht beantworten Java Basics - Anfänger-Themen 5
A Schleifen, Hilfe! Java Basics - Anfänger-Themen 6
LeonDerStudent Hilfe bei Uniprojekt Java Basics - Anfänger-Themen 2
H Brauche Hilfe in Java Eclipse Programmieraufgabe Neuling Java Basics - Anfänger-Themen 3
B Hilfe bei Map Liste erstellen Java Basics - Anfänger-Themen 10
Kapfski Was habe ich falsch gemacht? Hilfe! Java Basics - Anfänger-Themen 17
R Java (Eclipse) "Lagerverwaltung" HILFE Java Basics - Anfänger-Themen 13
M Bräuchte Hilfe bei diesen Methoden Java Basics - Anfänger-Themen 4
dieter000 Aufgabe Hilfe Java Basics - Anfänger-Themen 17
Gaudimagspam Dringend Java Hilfe benötigt Java Basics - Anfänger-Themen 19
jonathanpizza Hilfe bei einer Übungsaufgabe Java Basics - Anfänger-Themen 3
dieter000 Hilfe bei dem Beispiel, wie gehe ich sowas am besten an? Java Basics - Anfänger-Themen 32
jonathanpizza Hilfe bei einer Aufgabe Java Basics - Anfänger-Themen 5
Q Hilfe auf Aufgabe(Matrixmultiplikation) Java Basics - Anfänger-Themen 1
jonathanpizza Hilfe bei der Aufgabe Java Basics - Anfänger-Themen 19
pry bitte Hilfe beim Kreditrechner objektorientiert Java Basics - Anfänger-Themen 6
R Hilfe bei removeduplicates Java Basics - Anfänger-Themen 5
D Brauche Dringend Hilfe...Prozedur/Funktionsprozedur Ergebnis augeben Java Basics - Anfänger-Themen 11
marcooooo einmal noch schnell hilfe bitte:/ Java Basics - Anfänger-Themen 2
Q Hilfe bei Hausaufgeben Java Basics - Anfänger-Themen 2
J Hilfe beim Label animieren Java Basics - Anfänger-Themen 1
S Hilfe Java Basics - Anfänger-Themen 1
JD_1998 Random Array sortieren mit Hilfe einer Methode Java Basics - Anfänger-Themen 4
Kawastori Hilfe bei Methoden Übung Java Basics - Anfänger-Themen 6
Chabub Hilfe bei Stacks und Queue Java Basics - Anfänger-Themen 2
J Hilfe beim verstehen Java Basics - Anfänger-Themen 3
A Hilfe bei Java Projekt Java Basics - Anfänger-Themen 4
I Brauche Hilfe bei Objektorientiertem programmieren Java Basics - Anfänger-Themen 23
B Hilfe bei Generics Java Basics - Anfänger-Themen 11
L Anfänger braucht Hilfe - Stecke beim Lernen fest Java Basics - Anfänger-Themen 10
M Brauche Hilfe bei If-Scheifen Java Basics - Anfänger-Themen 2
M Hilfe bei Strukturierung eines Buchungssystems Java Basics - Anfänger-Themen 3
J Replace mit Hilfe von ArrayLists Java Basics - Anfänger-Themen 6
J Hilfe bei Übungsaufgabe Java Basics - Anfänger-Themen 17
Bluedaishi Hilfe beim erklären dieser Methode Java Basics - Anfänger-Themen 5
K Error bei meinem Programm - Hilfe Java Basics - Anfänger-Themen 8
B Hilfe bei einer rekursiven Methode Java Basics - Anfänger-Themen 3
K Java Projekt Hilfe Java Basics - Anfänger-Themen 5
F ich brauche Hilfe bei Listen Java Basics - Anfänger-Themen 13
J Hilfe beim Programmieren Java Basics - Anfänger-Themen 5
A suche dringend Hilfe!! Java Basics - Anfänger-Themen 6
S Hilfe. Generics und BiFunctions Java Basics - Anfänger-Themen 10
L hilfe run button funktioniert nicht Java Basics - Anfänger-Themen 13
S Hilfe : Unendlich viele Zufallszahlen erstellen? Java Basics - Anfänger-Themen 8
J Ich brauche Hilfe bei einem Code (Variablen speichern) Java Basics - Anfänger-Themen 29
E Ich Brauche Hilfe Java Basics - Anfänger-Themen 3
L Brauche Hilfe beim arbeiten mit Konstruktoren Java Basics - Anfänger-Themen 20
F Hilfe - Wahrheitswert überprüfen ohne If Java Basics - Anfänger-Themen 2
M Hilfe bei Testfällen. Java Basics - Anfänger-Themen 12
I Methoden char Array Aufgabe (bitte hierbei um Hilfe) Java Basics - Anfänger-Themen 3
J Brauche Hilfe bei einer aufgabe Java Basics - Anfänger-Themen 1
A Hilfe, LinkedList Java Basics - Anfänger-Themen 2
F Hilfe für einen Anfänger! Java Basics - Anfänger-Themen 4
F Regex Hilfe Java Basics - Anfänger-Themen 3
ZH1896ZH OOP Verstehe nicht was der Hinweis bedeutet, bitte um Hilfe! Java Basics - Anfänger-Themen 2
S Ein Java Anfänger braucht Hilfe Java Basics - Anfänger-Themen 5
S Hilfe bei meinem Code [Schleife]? Java Basics - Anfänger-Themen 5
S Brauche hilfe in Java [Fehler in mein Code]? Java Basics - Anfänger-Themen 2
S Wie ende ich mein Pogrammierung? [Hilfe] Java Basics - Anfänger-Themen 1
S Unbedingte hilfe bei Java Aufgabe [Schleife / Zinsrechnung] Java Basics - Anfänger-Themen 14
I Dezimalzahlen - Hilfe Java Basics - Anfänger-Themen 2
J Hilfe bei Java Aufgabe (Restschuld berechnen) Java Basics - Anfänger-Themen 11
S Hilfe bei Java Aufgabe (Schleifen) Java Basics - Anfänger-Themen 25
S Ein- Ausgaben Java [Hilfe] Java Basics - Anfänger-Themen 3
P Hilfe bei Double Java Basics - Anfänger-Themen 1
J Hilfe zu Codingame Java Basics - Anfänger-Themen 1
I Objekte Hilfe Java Basics - Anfänger-Themen 8
B Hilfe bei InputStream To File Java Basics - Anfänger-Themen 22
B Dropbox Anbindung, Hilfe bei Authentification -> HttpServletRequest request Java Basics - Anfänger-Themen 3
L Kleine Hilfe beim Schreiben eines Programmes benötigt :D Java Basics - Anfänger-Themen 40
Blender3D GOTO (aus Digitaluhr, Hilfe !) Java Basics - Anfänger-Themen 38
Z Digitaluhr, Hilfe ! Java Basics - Anfänger-Themen 24
W Hilfe beim Chat Programm Java Basics - Anfänger-Themen 14
Z Hilfe, Summenformel in Java Java Basics - Anfänger-Themen 15
I Hilfe bei experiment Java Basics - Anfänger-Themen 2
I Hilfe bei der Logik Java Basics - Anfänger-Themen 9
N Hilfe bei Unistoff Java Basics - Anfänger-Themen 3
S Bitte Hilfe zu Fehlermeldung am Handy Java Basics - Anfänger-Themen 2
M Hilfe bei Projektorientierungs-Aufgabe !! Java Basics - Anfänger-Themen 3
I Do-While / Kalkulator / Bitte um Hilfe Java Basics - Anfänger-Themen 9
M Hamstersimulator- lösung hilfe benotigt Java Basics - Anfänger-Themen 3
M Hamstersimulator Hilfe Java Basics - Anfänger-Themen 46
S Erste Schritte Hilfe beim lernen von Programmieren Java Basics - Anfänger-Themen 2
D Hilfe um Pseudocode Analyse! Java Basics - Anfänger-Themen 1

Ähnliche Java Themen

Anzeige

Neue Themen


Oben