O-Notation

ChillStudent

Mitglied
hallo,
ich bin dabei O-Notation zu lernen und muss dafür hausaufgaben abgeben. Nur blicke ich da nicht wirklich durch und in google finde ich auch nicht alle die große hilfe...ich hoffe, ihr könnt mir weiter helfen!



Welche worst-case Laufzeit in O-Notation hat der folgende Algorithmus?

Java:
static void makeTrue(boolean[][] a, int n) {
for (int i = 0; i < n/3; i++) {
if (i%6 == 0) continue;
else a[i][0] = true;
}
for (int i = 0; i < n/2; i++) {
for (int j = 0; j < n-i; j += i+1) {
a[i][j] = true;
}
}
}

Ich bin mir nicht sicher aber ich komme auf die Laufzeit: O(n²)
die obere Schleife durchläuft n/3 Iterationen, somit O(n) und die untere verschachtelte O(n²). Summiert man den Aufwand, so ergibt die Laufzeit O(n²).
 
Zuletzt bearbeitet:

Thunderstorm

Mitglied
Bedenke aber folgendes :

Die Schleife führt den Inhalt x MAL aus. Dementsprechend wird nicht summiert, sondern multipliziert. Was die verschachtelte Schleife angeht, hatt ich jetzt keine Lust zu überlegen, es ist Sonntag Abend :popcorn:

mfg Thunder
 
Zuletzt bearbeitet:
Ähnliche Java Themen
  Titel Forum Antworten Datum
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
B Komplexität und O-Notation Java Basics - Anfänger-Themen 2
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