Schleifen & O Notation

[Xpisto]

hey ich hab gestern über den gast account geschrieben weil ich über dem handy geschrieben habe. Irgendwie ist keiner auf mein ergebnis eingegangen soondern nur auf die antwort meines vorgängers Kann mir jemand sagen ob ich O(n^4) richtig ist?


Noch eine andere Frage:

Wurzel(n-1) * log(n) * Wurzel(n)

Ist O(log(n)) richtig oder wäre O(Wurzel(n)) richtig?

Nächste Frage

n(n-1) + n² = O(n³)

Diese Aussage ist doch falsch oder? O(n³) wächst schneller als die linke gleichung.

 

[XHelp]

1. Darauf wurde doch eingegangen, ließ den Post von HimBromBeere
2. plot sqrt(n), log(n) n=1 to 100000 - Wolfram|Alpha
3. Dadurch dass n³ schneller wächst, ist ja die Aussage richtig. Aber wie kommst du denn von n+n² auf n³???

 

[langhaar!]

Nächste Frage

n(n-1) + n² = O(n³)

Diese Aussage ist doch falsch oder? O(n³) wächst schneller als die linke gleichung.

Die Aussage ist richtig.
Das = ist eine (schlampige) Vereinfachung und müsste eigentlich 'ist Element von' heissen.

 

[XHelp]

Gleichheitszeichen ist bei der O-Notation zulässig. Es ist zwar rein formal gesehen nicht richtig (ist ja keine Gleichung, außerdem ist das eine eine Funktion und das andere eine Menge), aber bei der O-Notation eben "erlaubt".

 

[langhaar!]

Gleichheitszeichen ist bei der O-Notation zulässig. Es ist zwar rein formal gesehen nicht richtig (ist ja keine Gleichung, außerdem ist das eine eine Funktion und das andere eine Menge), aber bei der O-Notation eben "erlaubt".

Ich habe nichts anderes geschrieben, oder?
Ich vermute aber, dass der TE Schwierigkeiten hatte, weil das verwendete = keine symmetrische Relation impliziert.

 

[XHelp]

Ich habe dann deinen Hinweis mit "müsste eigentlich" falsch interpretiert. Nehme alles zurück

 

[HimBromBeere]

Wurzel(n-1) * log(n) * Wurzel(n)

Ist O(log(n)) richtig oder wäre O(Wurzel(n)) richtig?

Sollte es nicht O(n*log(n)) sein?

 

[xKoRe]

xKoRe, entweder hast du dich falsch ausgedrückt oder ich muss dir widersprechen:
Bei der O-Notation gibt es keinen "exakten Aufwand". Es gibt natürlich eine exakte Laufzeit, aber das hat nichts mehr mit O-Notation zu tun. Darüber hinaus ist O(3n) genau die selbe Menge wie auch O(n), O(n+100), O(n+log(n)) usw.

Falsch ausgedrückt, ich weiss es gibt ein O und ein Theta was aussieht wie ein O mit Strich in der Mitte. Letzteres handelt sich dann wohl um den exakten Aufwand. Ich wollte das nur der Vollständigkeit halber dazugesagt haben.

Dass dies alles wie du sagst in der selben Menge liegt, denke ich habe ich klar gemacht. Nicht jedoch z.b. O(n * log(n)). Der kleine aber feine Unterschied

 

[langhaar!]

Falsch ausgedrückt, ich weiss es gibt ein O und ein Theta was aussieht wie ein O mit Strich in der Mitte. Letzteres handelt sich dann wohl um den exakten Aufwand.

Sorry, wieder falsch.
Auch das Theta ist nicht der exakte Aufwand; es beschreibt eine Klasse von Aufwänden in einem bestimmten Bereich, die asymptotisch gleich sind. Das hat mit exaktem Aufwand nichts zu tun.

3n +4 ist nicht n/2. Trotzdem liegen beide asymptotisch im Bereich Theta(n).

 

[Xpisto]

Hey Leute, was sagt ihr eigentlich zu der folgender Aussage:


Algorithmen mit einer Laufzeit von O(n^k) werden als effizient bezeichnet? Dabei steht k für eine Konstante.

 

[XHelp]

Was sagst du zu der Aussage:
Beton ist ein leichtes Material?
Wenn du es mit Eisen vergleichst - dann ja, wenn du es mit Holz vergleichst, dann nicht :bahnhof:

 

[Xpisto]

Also sind es keine effiziente algorithmen hab ichs richtig angekreuzt ja?

 

[HimBromBeere]

Im Übrigen gibt es praktisch keine Effizienzklasse, die noch schlechter wäre...

guckst du hier: http://www.java-forum.org/java-basics-anfaenger-themen/131011-schleifen-o-notation-3.html#post858724

EDIT:

Also sind es keine effiziente algorithmen hab ichs richtig angekreuzt ja?

Ja, haste fein gemacht:toll:

 

[Xpisto]

Wunderbar

Ich möchte mich nochmal recht herzlich bei euch bedanken für alle hilfreichen Antworten. Mal schaun obs mich bei der Klausur weitergebracht hat

 

[XHelp]

Ich finde nach wie vor, dass die Aussage falsch ist. Ist 40 eine große Zahl? Sind 5 Tage eine große Zeitspanne? Sind 30 cm lang?

 

[Xpisto]

Ja es war doch eine ankreuzfrage die mit wahr oder falsch beantwortet werden musste undich hab falsch angekreuzt, Algorithmen mit O(n^k) sind nicht effizient.

Oder was meinst du jetzt?

 

[HimBromBeere]

Ich gebe XHelp recht, dass die Aussage eigtl. nicht mit richtig oder falsch beantwortet werden kann, da es einer Relation bedürfte. Es müsste vielleicht eher heißen: solche Algorthmen GELTEN als ineffizient (da es durchaus theoretisch auch NOCH schlimmer geht).
Aber wie ich bereits erwähnt hab ist O(n^k) schon wirklich mies und sollte vermieden werden, soweit dies möglich ist.

 

[Xpisto]

Im Übrigen gibt es praktisch keine Effizienzklasse, die noch schlechter wäre...

Ehm da wollt ich jetzt doch n ochmal nachhaken, du sagst es gibt keine effizienzklasse die schlechter ist? Dabei wäre doch O(n³) schlechter als O(n²). Beide sind doch O(n^k) oder nicht?

 

[HimBromBeere]

Ehm da wollt ich jetzt doch n ochmal nachhaken, du sagst es gibt keine effizienzklasse die schlechter ist? Dabei wäre doch O(n³) schlechter als O(n²). Beide sind doch O(n^k) oder nicht?

O(n³) ist natürlich schlechter als O(n²). Aber nach der exponentiellen Effizienzklasse kommt halt nicht mehr viel, das sollte damit gemeint sein...

EDIT: Bevor mich noch jemand in die Pfanne haut: k >= 2

 

[Xpisto]

Ja richtig, also das wird schon gepasst haben. Dank dir

 

[Paddelpirat]

Moment mal. O(n^k) für k konstant ist doch polynomiell und gilt somit (in Relation zu exponentiellen Laufzeiten, also O(k^n) für k konstant und n variabel) als effizient.

 

[XHelp]

und gilt somit (in Relation zu exponentiellen Laufzeiten, also O(k^n) für k konstant und n variabel) als effizient

Ja, aber in Relation zu O(log(n)) ineffizient. Es kommt eben darauf an was du womit vergleichst.
Oder mal ein ganz anderes Beispiel: wenn du es schaffst ein NP-schweres Problem (z.B. Clique in Graphen) in O(n^k) zu lösen, dann ist a) diese Laufzeit SUPER effizient und b) du ein SUPER reicher Mann.

 

[Paddelpirat]

Deswegen habe ich auch in Relation geschrieben.
Die Frage, so wie sie hier steht ist unpräzise gestellt und die Antwort hängt meiner Meinung nach von dem Kontext und der Vorlesung ab. Wenn man da zwischen Algorithmen mit polynomieller und exponentieller Laufzeit unterschieden hat, dann könnte man schon erwarten, dass man O(n^k) für k konstant, als polynomielle Laufzeit erkennt.

Und so wie ich HimBromBeeres letzten Post lese, scheint er/sie unter n^k für (konstantes k) exponentielle Laufzeit zu verstehen. Das ist aber so nicht richtig, da es polynomiell ist.

Edit zu NP: Sorry, ich erkenne gerade nicht den Zusammenhang *g*. Habe auch nicht vor P=NP oder P!=NP zu zeigen, da zerbrechen sich schon genügend andere den Kopf drüber. So wie ich es aus meinen Vorlesungen kenne soll man vom Aufgabentyp her zeigen, dass man den Unterschied zwischen O(n^k) und O(k^n) verstanden hat. Aber ich stimme dir zu, die Frage ist unpräzise

 

[HimBromBeere]

Oooooh, tschuldigung, das hab ich tatsächlich komplett übersehen... ich bin (weiß der Kuckuck warum) von k^n ausgegangen und nicht n^k). Ja, mit n^k bewegen wir uns wirklich in einer Grauzone, die ziemlich ungenau zu definieren ist. Die Aufgabenstellung ist tatsächlich doof formuliert, ich meine mit

Im Übrigen gibt es praktisch keine Effizienzklasse, die noch schlechter wäre...

natürlich k^n, das ist schon so ziemlich Wurst-Käse.

Tschuldigung für die Verwirrung

EDIT: mal für Fach-Informatiker: Was ist NP?

 

[XHelp]

mal für Fach-Informatiker: Was ist NP?

Probleme, die von einer nichtdetermenistischen Turingmaschine in polynomieller Zeit gelöst werden können :joke: Hört sich abgefahren an, aber im Grunde sind es Probleme, die "normal" (determenistische Turingmaschine) eine exponentielle Laufzeit haben. Ist eine Komplexitätsklasse von Problemmen in der theoretischen Informatik. wiki. Es ist aber nichts, was man so kurz und knapp komplett erklären könnte.
Und was meine Anspielung auf "SUPER reich" angeht: Es gibt auch eine Klasse P, die eben "normal" eine polynomielle Laufzeit hat. Es ist nach wie vor nicht bewiesen, ob es dabei um die selben Klassen handelt, oder ob P eine Untermenge ist (wiki). Es ist eins der Millennium-Probleme, für die Lösung welcher man 1 Million Dollar kassiert. Darüber hinaus hätte man so ganz nebenbei gezeigt, dass man egal welches lösbares Problem in polynomieller Laufzeit lösen kann (wie z.B. das Knacken der PIN, oder Militärverschlüsselung ), dann werden die Hacker-Filme mit "klick, klick, klick - wir sind in Pentagon" plötzlich zur Wirklichkeit
(man geht stark aber davon aus, dass P!=NP ist)

 

[HimBromBeere]

Oooooookay... ich hab das wiki gelesen und annähernd nichts verstanden???:L... aber sei´s drum, es gibt Dinge, die muss man nicht verstehen. Ist auch Wurscht...

 

[Paddelpirat]

Eine Komplexitätsklasse in der einige interessante Problemstellungen liegen, wie das von XHelp erwähnte.
Es ist auch ein NP-schweres Problem (durch Reduktion zu zeigen). Wenn ein Problem NP-schwer ist und in NP liegt, heißt es NP-vollständig.

Für diese Probleme gibt es bisher keine effizienten (sprich polynomielle) Algorithmen. Würde man zu einem Problem einen effizienten Algorithmus finden, hätte man für all diese Probleme einen effizienten Algorithmus.

So das nur mal ganz grob. Hier gibts mehr: NP (Komplexitätsklasse) ? Wikipedia

Falls du dich noch mehr dafür interessierst, kannst du auch mal nach Satz von Cook / SAT / 3-SAT umgucken.

Edit:

Probleme, die von einer nichtdetermenistischen Turingmaschine in polynomieller Zeit gelöst werden können

Probleme, die von einer nichtdetermenistischen Turingmaschine in polynomieller Zeit "akzeptiert" werden. :bae:. Ich geh glaub ich besser gleich mal schlafen. Hatte nur im November meine Prüfung und musste das können.

 

[JustGuest123]

Moin Leute, auch mal eine kurze Frage, da es thematisch hier reinpasst. Habe online folgendes Beispiel gefunden, das mir spontan auch nicht einleuchtet. Abgesehen von der etwas wirren Zählerbezeichnung müssten meiner Auffassung nach bei Schleifen aus O(k²) sein. entnommen hier: O-Notation

bitte um kurze Info/Input. Danke&Gruß

Beispiele:

for (i = 0; i < k; i++) { for (i = 0, i < k; i++) {
for (j = 0; j < k; j++) { for (j = 0; j < k; j++) {
brett[j] = 0; if (a == a[j]) treffer = true;
} }
} }

k2 Schritte für k2 Daten k2 Schritte für k Daten
O(n) -Algorithmus O(n2) -Algorithmus

 

[SlaterB]

O(k^2), korrekt, das steht dort doch auch mehr oder weniger,
es ist nur die Frage als was man n ansieht, ist n == k, dann O(n^2), ist n aber k^2 dann offensichtlich O(n)

bei dem 2D-Array wird die gesamte Datenmenge als n aufgefasst,
stell dir vor es wäre nur ein Array mit entsprechend höhere Länge, die Schleife durchläuft jedes Datenfeld genau einmal,
linear zur (auf Kantenlänge bezogen quadaratischen) Gesamtgröße

 

[JustGuest123]

Moin,
erstmal vielen Dank. Hätte noch eine weitere Frage:

Countingsort: Countingsort ? Wikipedia

Mir leuchtet intuitiv nicht ein, wieso die Laufzeit dort so ist wie sie angegeben ist (O(n+m)) Wenn ich mir den Javacode anschaue:

die erste for-Schleife sucht aus dem Eingabearray int[] numbers die größten wert. Das ist ja eigentlich O(n) wenn n=length.numbers ist

das Zählen wie oft jede Zahl vorkommt auch O(n)

bei den nächsten beiden Schleifen bin ich nicht 100% sicher. die innere müsste eigentlich m sein (Anzahl aller Zahlen aufsummiert, dies wird hier wohl mit m bezeichnet). Das soll dann O(m) sein?

insgesamt ist das ja dann eigentlich schon O(n+n+m)? und vor allem, was ist mit der dritten for-schleife? unter den Teppich gekehrt? Letztendlich haben wir hier ja dann eine lineare Laufzeit mit irgendeiner Konstante...oder?

Danke für Input.

 

[Sonecc]

Wenn meine Erinnerung mich nicht trügt (ist nun schon 4 Jahre her seit ich das hatte), sollten konstanten in der o-notation vernachlässigt werden.
Das bedeutet bei deinem Beispiel:

O(n+n+m) = O(2n+m) <=> O(n+m)

 

[SlaterB]

Konstante ist ein gutes Stichwort, Konstanten sind eben hierbei egal,
es gibt Schleifen über n und Schleifen über m, deswegen gehen beide linear ein,
wenn man an n = 100, 100 Mio. oder 100 Mrd. denkt ist es ziemlich egal ob es eine oder 4 Schleifen sind, Konstante Faktoren fallen immer weg,

nur quadratisch oder log wäre eine wichtige neue Ordnung,
n^2 wird irgendwann immer größer, egal wie hoch die Konstante eines linearen Aufwands ist

 

[JustGuest123]

Danke Leute, wirklich hilfreich. Schönes WE