Laufzeit und O-Notation

Mkhitaryan

Neues Mitglied
Sers

ich hätte da eine Frage bezüglich laufzeit und o-notationen. wie es ungefähr funktioniert, scheine ich kapiert zu haben, aber will nur noch mal sicher gehen.

Ich habe hier folgenden Codeausschnitte (ist aus einer früheren Klausur, wo es noch keine lösungen gibt und mehr ist nicht gegeben) und will daraus die laufzeitkomplexität berechnen:

Java:
		for ( int j = n-1; j>1; j--) { //wird n-2 mal durchlaufen
			
			for ( int i = 1; i<n ; i++) {  //wird n-1 mal durchlaufen
				
				array [j] = array [j] - 1;
				}
			}

Ist das Ergebnis dann O ( (n-1) (n-2) ) = O (n² - 3n + 2) ? Ich zweifle eigentlich nur daran, weil es ein ziemlich "unschönes" ergebnis ist :bloed:

Und zweitens, wie berechne ich sowas im Falle von if-else?
Java:
		if (x < 100) { //wird einmal durchlaufen
			y = x;
		} else
			for (int i = 1; i < n; i++) { //wird n-1 mal durchlaufen
				if (a[i] > y) //wird einmal durchlaufen
					y = a[i];
			}

Im besten fall ist das ja nur O(1), wenn x >= 100 ist. Oder muss ich hier sowas wie eine Fallunterscheidung machen oder nur den Worst-Case nehmen?
Für letzteres wäre es doch, wenn ich mich nicht irre, dann doch O (1 * (n-1) * 1) = O (n-1)

Sehe ich das alles so richtig oder habe ich irgendwo einen denkfehler gemacht?

Danke schon mal :)
 

Klösp

Aktives Mitglied
Ich lasse mich gerne korrigieren, aber soweit ich das in Erinnerung habe zählt nur die höchste Potenz.
Konstanteteile werden auf jeden Fall weggelassen, weil es um die Wachstumsklasse geht.
 

rme

Top Contributor
Schau dir mal die Rechenregeln an, z.B. hier: Formelsammlung O-Notation ? Wedelwiki

Dort steht, und so habe ich es auch gelernt, dass für O(f(n) + g(n)) = max(O(f(n), O(g(n))) gilt. Das bedeutet, dass Summen in der Klasse ihrer größten (im Sinne der O-Notation) Summanden liegen. Also ist O(n² + n) = O(n²). Mit diesen Regeln kann man die Ausdrücke vereinfachen, in der entsprechenden Vorlesung werden diese Regeln üblicherweise auch bewiesen.

Zur Frage mit der Fallunterscheidung: Beim großen O gilt, dass der worst-case untersucht wird. Überleg dir also, wie für deinen Algorithmus der Worst-Case aussieht, d.h. in welchem Fall das äußerste if falsch ist und das innerste if am häufigsten wahr ist. Dann betrachtest du die Laufzeit dieser schlimmsten Eingabe.
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
G Laufzeit/ O/Θ-Notation einer Treeset Methode Java Basics - Anfänger-Themen 0
Detlef Bosau Nachladen von Klassen zur Laufzeit Java Basics - Anfänger-Themen 24
E Alter (Laufzeit) berechnen Java Basics - Anfänger-Themen 11
W Array zur Laufzeit bearbeiten? Java Basics - Anfänger-Themen 31
D Objekterzeugungen mit zur Laufzeit variierenden Attributen Java Basics - Anfänger-Themen 7
J GroupLayout zur Laufzeit erweitern Java Basics - Anfänger-Themen 1
B Übersetzungszeit und Laufzeit Java Basics - Anfänger-Themen 3
amgadalghabra Die vier Sortieralgorithmen die durchschnittliche Laufzeit in Millisekunden Java Basics - Anfänger-Themen 37
U Dijkstra Algorithmus Laufzeit Java Basics - Anfänger-Themen 3
S Laufzeit Quicksort wenn alle Elemente gleich sind Java Basics - Anfänger-Themen 4
L Anzahl der Elemente key in einem Array mit log(N) Laufzeit Java Basics - Anfänger-Themen 4
S Interpreter-Fehler Endlosschleife zur Laufzeit aber warum? Java Basics - Anfänger-Themen 15
J JavaFX Label,Button zur Laufzeit Java Basics - Anfänger-Themen 30
H Laufzeit Java Basics - Anfänger-Themen 11
C Laufzeit eines Sortier-Algorithmus ermitteln Java Basics - Anfänger-Themen 4
L Objekt Typ zur Laufzeit ermitteln Java Basics - Anfänger-Themen 1
J Datei im Package zur Laufzeit editieren Java Basics - Anfänger-Themen 1
M Quicksort Laufzeit langsam Java Basics - Anfänger-Themen 5
M Quicksort Laufzeit langsam Java Basics - Anfänger-Themen 0
R Objekte zur Laufzeit in Schleife erzeugen und in ArrayList ablegen Java Basics - Anfänger-Themen 4
C Laufzeit von Stack Operation Java Basics - Anfänger-Themen 5
D Laufzeit von einfachem Programm Java Basics - Anfänger-Themen 21
J Laufzeit berechnen/Laufzeitanalyse Java Basics - Anfänger-Themen 2
M Input/Output Datei in Laufzeit-JAR kopieren Java Basics - Anfänger-Themen 6
V Laufzeit Java Basics - Anfänger-Themen 23
W Klassen [GELÖST] Objekte während der Laufzeit mit neuen veränderten Werten beliebig oft initialisieren Java Basics - Anfänger-Themen 2
M Erste Schritte Code zur Laufzeit ändern lassen Java Basics - Anfänger-Themen 3
C Klassen aus einem Package ermitteln und per Laufzeit laden Java Basics - Anfänger-Themen 17
J Objekte zur Laufzeit erzeugen und direkt verwenden Java Basics - Anfänger-Themen 9
M Möglich? Methode aufrufen deren Bezeichner zur Laufzeit durch einen überg. String festgelegt wird Java Basics - Anfänger-Themen 3
K JLabel zur Laufzeit dynamisch erzeugen Java Basics - Anfänger-Themen 7
M Methoden miteinander verbinden (Laufzeit) Java Basics - Anfänger-Themen 6
llabusch Interface Layout eines Labels während der Laufzeit ändern Java Basics - Anfänger-Themen 0
Streeber reale Laufzeit meines Programms ausgeben Java Basics - Anfänger-Themen 1
D Algorithmus zu gegebener Laufzeit implementieren Java Basics - Anfänger-Themen 1
R Variablen Datentyp erst während Laufzeit festlegen Java Basics - Anfänger-Themen 6
S Klassentyp zur Laufzeit ändern? Java Basics - Anfänger-Themen 3
M Variablen Variable zur Laufzeit erzeugen Java Basics - Anfänger-Themen 3
A Laufzeit von verschachtelter for-Schleife Java Basics - Anfänger-Themen 4
B Variablen Instanz von Enum zur Laufzeit erstellen und zuweisen Java Basics - Anfänger-Themen 2
L Panels zur Laufzeit ändern Java Basics - Anfänger-Themen 2
A Laufzeit Java Basics - Anfänger-Themen 11
M Methodennamen zur Laufzeit ausgeben Java Basics - Anfänger-Themen 5
F JTable zur laufzeit füllen Java Basics - Anfänger-Themen 7
P GUI - Layout per Laufzeit erstellen/verändern? Java Basics - Anfänger-Themen 6
N Variablen VariableNamen auswirkung auf Laufzeit Java Basics - Anfänger-Themen 3
R Rekursionsformel für Laufzeit von Algorithmus Java Basics - Anfänger-Themen 3
J Erste Schritte Zinseszinsberechnung Ermittlung Laufzeit Java Basics - Anfänger-Themen 3
S Laufzeit bei rekursiver Methode messen Java Basics - Anfänger-Themen 6
S Erste Schritte Weihnachtsbaum / Laufzeit O(n) Java Basics - Anfänger-Themen 9
E Laufzeit verkürzen Java Basics - Anfänger-Themen 14
A Threads Zur Laufzeit hinzufügen/entfernen Java Basics - Anfänger-Themen 10
D Classpath compiler zur Laufzeit aufrufen & lib-classpath Java Basics - Anfänger-Themen 6
E Input/Output Inputstream während der Laufzeit füllen Java Basics - Anfänger-Themen 2
B Laufzeit berechnen? Java Basics - Anfänger-Themen 7
S Klasse bei Laufzeit laden? Java Basics - Anfänger-Themen 2
B Klassen Objekte während der Laufzeit dynamisch anlegen Java Basics - Anfänger-Themen 8
K jButton zur Laufzeit hinzufügen Java Basics - Anfänger-Themen 22
D globale Variablen zur Laufzeit erzeugen Java Basics - Anfänger-Themen 5
A Frage zur Laufzeit / Optimierung Java Basics - Anfänger-Themen 2
N Laufzeit in Nanosekunden - in Minuten umrechnen Java Basics - Anfänger-Themen 6
alderwaran objekthierarchie darstellen während der laufzeit Java Basics - Anfänger-Themen 2
G Objekte von Klassen die erst zur Laufzeit bekannt sind erstellen Java Basics - Anfänger-Themen 6
B Frage zur Laufzeit Java Basics - Anfänger-Themen 2
Luk10 Variablen zur Laufzeit ändern! Java Basics - Anfänger-Themen 7
G JAR zur Laufzeit nachladen Java Basics - Anfänger-Themen 2
S JDialog resize zur Laufzeit PROBLEM!!! Java Basics - Anfänger-Themen 5
E Pfad zu einem gif-Bild wird zur Laufzeit nicht gefunden Java Basics - Anfänger-Themen 5
A Applet Bild zu laufzeit hinzufügen Java Basics - Anfänger-Themen 4
C Frage zu Syntax-,Laufzeit-, Semantikfehler Java Basics - Anfänger-Themen 3
R JVM zur laufzeit manipulieren? Java Basics - Anfänger-Themen 4
S Zur Laufzeit Strings Compilieren Java Basics - Anfänger-Themen 5
A Objekte während der Laufzeit erstellen Java Basics - Anfänger-Themen 3
A Objektzugriff zur Laufzeit ändern Java Basics - Anfänger-Themen 20
G Text eines JLabels zur Laufzeit ändern Java Basics - Anfänger-Themen 4
M Laufzeit von Programmen Java Basics - Anfänger-Themen 3
A Jar-Archive zur Laufzeit erstellen Java Basics - Anfänger-Themen 3
G Zu Laufzeit von Tastatur einlesen Java Basics - Anfänger-Themen 11
E Einen String auch über die Laufzeit hinaus speichern Java Basics - Anfänger-Themen 4
A Neue Objekte zur Laufzeit erzeugen Java Basics - Anfänger-Themen 5
D Locale zur Laufzeit über JComboBox laden? Java Basics - Anfänger-Themen 17
S Ausdruck zur Laufzeit auswerten Java Basics - Anfänger-Themen 10
G Anzahl Textfelder zur Laufzeit verändern. Java Basics - Anfänger-Themen 4
Z Benutzerdaten währen Laufzeit speichern Java Basics - Anfänger-Themen 2
K JProgressbar, zur laufzeit steuern Java Basics - Anfänger-Themen 7
V Vektoren zur Laufzeit erzeugen Java Basics - Anfänger-Themen 7
N zur Laufzeit gefundene class-Datei verwenden - wie geht das? Java Basics - Anfänger-Themen 2
G Look and Feel zur Laufzeit ändern Java Basics - Anfänger-Themen 2
A Text einer JComboBox während der Laufzeit ändern ? Java Basics - Anfänger-Themen 4
K Chart zur Laufzeit erstellen und aktualisieren Java Basics - Anfänger-Themen 2
G JAR: Externe Dateien zur Laufzeit aufrufen Java Basics - Anfänger-Themen 12
C Variablen zur Laufzeit erstellen? Java Basics - Anfänger-Themen 14
B Warum hat dieser einfache Algorithmus lineare Laufzeit? Java Basics - Anfänger-Themen 3
M JButton zur laufzeit erzeugen/ löschen Java Basics - Anfänger-Themen 3
B Laufzeit und Übersetzungszeit Java Basics - Anfänger-Themen 11
H ComboBox zur Laufzeit erzeugen? Fehler. Java Basics - Anfänger-Themen 8
M Java Heap Space während der Laufzeit ändern Java Basics - Anfänger-Themen 2
M Klassen zur Laufzeit laden, aus einer jar heraus. Java Basics - Anfänger-Themen 14
A classpath zur Laufzeit erweitern Java Basics - Anfänger-Themen 4
G Anpassen einer JComboBox zur Laufzeit Java Basics - Anfänger-Themen 7

Ähnliche Java Themen

Neue Themen


Oben