Hallo,
(hab den Titel leider vergessen zu ändern!)
ich hab eine Aufgabe in Pseudocode gegeben und soll dazu die O-Notation bestimmen. Doch leider stehe ich total auf dem Schlauch.
Hier erst einmal die Aufgabe:
Leider verstehe ich schon a) nicht.
Meine Überlegung bei dieser Aufgabe war folgende:
nun kämm das Problem denn dann wäre:
Meine Abschätzung geht dann in O(n³) das stimmt aber nicht da ich es in Java getextet habe und andere Ergebnisse raus kommen bei n = 6 kommen 182 Schleifen Durchläufe raus und keine 216. Da es nur eine Abschätzung ist denke ich liege ich trotzdem daneben
Kann mir das vielleicht irgendwie jemand erklären?
LG
(hab den Titel leider vergessen zu ändern!)
ich hab eine Aufgabe in Pseudocode gegeben und soll dazu die O-Notation bestimmen. Doch leider stehe ich total auf dem Schlauch.
Hier erst einmal die Aufgabe:
Code:
Gegeben sei der folgende Algorithmus in Pseudocode-Notation.
Bemerkung: a[] ist ein Array [0..n-1] gefüllt mit n Zahlen aus der Menge {0,1}
T = 0
For i = 0 to (n-1) {
For j = n downto (n+i) {
k = j
while ( k >= 0){
k= k -1
T = (T + a[k]) mod 2 // „mod“ gibt den ganzzahligen Divisionsrest zurück
}
}
}
GibAus(T) // zu interpretierendes Ergebnis
a) Schätzen Sie anhand der O-Notation den Laufzeitaufwand ab hinsichtlich der inneren Additi-
on von T.
b) Was können Sie anhand des Ergebnisses/der Ausgabe über den Inhalt des Arrays aussagen?
c) Welche Komplexität (in O-Notation) hat das Problem (Aussage aus b) eigentlich?
Leider verstehe ich schon a) nicht.
Meine Überlegung bei dieser Aufgabe war folgende:
For i = 0 to (n-1) {
läuft n-1 malFor j = n downto (n+i) {
wäre n = 0 so ergibt sich hier das die Schleife i mal läuftnun kämm das Problem denn dann wäre:
while ( k >= 0)
mehr oder weniger 0 bzw. ist ja abhängig von j somit j mal somit i mal!Meine Abschätzung geht dann in O(n³) das stimmt aber nicht da ich es in Java getextet habe und andere Ergebnisse raus kommen bei n = 6 kommen 182 Schleifen Durchläufe raus und keine 216. Da es nur eine Abschätzung ist denke ich liege ich trotzdem daneben
Kann mir das vielleicht irgendwie jemand erklären?
LG
Zuletzt bearbeitet: