Komplexität und O-Notation

breakdownfever

Neues Mitglied
Hallo,

da ich ein bisschen überfragt bin mit theoretischen Java-Fragen und um zu wissen ob ich das Thema mit dem Aufwand richtig verstanden habe, wollte ich kurz mal fragen ob meine Lösung so richtig ist.

In dieser Übung sollten wir den genauen Aufwand und den Aufwand in O-Notation für folgende for-Schleife angeben, wobei x++ den Aufwand O(1) hat und Verwaltungsaufwand nicht berücksichtigt wird.

Java:
 for (int i=n; i>1; i/=3) 
x++;

Da es sich um ein Integer handelt, wird die Schleife maximal n/3 mal ausgeführt. Dementsprechend wäre der genaue Aufwand bei
Java:
 n/3 * O(1)
und der Aufwand in O-Notation
Java:
 1/3 * n * O(1) => 1/3 * O(n) => O(n)
da Konstanten ja weggelassen werden.

Das Thema genauer Aufwand wurde im Skript jedoch auch nicht behandelt und die Beispiele sehr Basic gehalten. Ich bin mir recht sicher, dass meine O-Notation richtig ist nur kann ich mit dem Begriff "genauem Aufwand" nicht wirklich anfangen. Ich hoffe ihr könnt mir weiterhelfen.
Grüße
 
Zuletzt bearbeitet:

njans

Top Contributor
Genauer Aufwand? So habe ich den Begriff noch nicht gehört, aber es könnte Theta damit gemeint sein. Während die groß O Funktion dir den WorstCase angibt, gibt Theta den genauen Aufwand an, siehe Wikipedia.

P.S. dein O(n) für deine Schleife würde ich als richtig erachten.
 
Zuletzt bearbeitet:

qwert

Aktives Mitglied
Ich möchte einwerfen, dass der Aufwand O(n) für die Schleife keinesfalls richtig ist. Die Schleife wird nicht (n/3)-mal ausgeführt, sondern log3(n)-mal!
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
C Komplexität [-1] Java Basics - Anfänger-Themen 1
M Komplexität Algorithmus Java Basics - Anfänger-Themen 8
J Komplexität Java Basics - Anfänger-Themen 11
M Komplexität Java Basics - Anfänger-Themen 10
H Erste Schritte Frage zur Komplexität O Java Basics - Anfänger-Themen 2
H Komplexität Java Basics - Anfänger-Themen 14
F komplexität bestimmen Java Basics - Anfänger-Themen 10
T Komplexität gesucht Java Basics - Anfänger-Themen 10
M Komplexität Java Basics - Anfänger-Themen 2
M Abstrakte Klassen - Notation Java Basics - Anfänger-Themen 9
monsterherz Punkt Notation funktioniert nicht Java Basics - Anfänger-Themen 4
berserkerdq2 Wo finde ich in der Java Api die Notation zu Threads bezüglich Synchronized? Java Basics - Anfänger-Themen 14
X UML Klassendiagramm, UML Notation Java Basics - Anfänger-Themen 2
P Suche Aufwandsgenerator (o-notation) Java Basics - Anfänger-Themen 1
H O-Notation Java Basics - Anfänger-Themen 2
A JavaScript Object Notation einbinden mittels Maven Java Basics - Anfänger-Themen 7
G Laufzeit/ O/Θ-Notation einer Treeset Methode Java Basics - Anfänger-Themen 0
C O-Notation Java Basics - Anfänger-Themen 1
M Laufzeit und O-Notation Java Basics - Anfänger-Themen 3
J O-Notation Java Basics - Anfänger-Themen 0
N Zeitaufwand - O-Notation Java Basics - Anfänger-Themen 11
H O notation Java Basics - Anfänger-Themen 5
R O-Notation Java Basics - Anfänger-Themen 11
X Schleifen & O Notation Java Basics - Anfänger-Themen 82
I Externer Methodenaufruf, Punkt-Notation Java Basics - Anfänger-Themen 11
X O-Notation ausdrücken Java Basics - Anfänger-Themen 7
K Wissenschaftliche Notation bei double "abschalten" Java Basics - Anfänger-Themen 3
R funktion und o-notation angeben Java Basics - Anfänger-Themen 2
F Zahlen ine-notation aus string Java Basics - Anfänger-Themen 4
M Gleitkommazahlen - Notation ändern Java Basics - Anfänger-Themen 4
S HTML mit num. Unicode Notation (was:Probleme bei Encoding) Java Basics - Anfänger-Themen 7
A UML-Notation Java Basics - Anfänger-Themen 2

Ähnliche Java Themen

Neue Themen


Oben