Algorithmus erstellen in O(n)
-
fricky schrieb:
mal angenommen jedes array-element besteht aus z bits. also brauchst du z zugriffe, um das element vollständig auszulesen. das ergibt O(z*n) und weil z konstant ist (muss so sein, wie soll man sonst die elemente auseinanderhalten?), fällt es weg. also hast du O(n).
Nein z ≥ ld(n). Sobald n wächst, werden auch die Arrays aus Bits größer. Klar das ist programmiertechnisch gesehen unlogisch und so nie vorkommend, aber um das gehts ja nicht.
@hustbear: Oh man das ist so natürlich erlaubt. Ich habe etwas ähnliches bereits auf meinem Schmierblatt gehabt, nur nicht begriffen, dass es wirklich O(n) ist.
-
Hallo,
sag mal, wie erbärmlich ist denn das hier?
Eine Prüfungsleistung von anderen erledigen lassen?!
Viele Grüße
ChrisM (Karlsruhe, auch Info 2)
-
Naja, ich hab ihm ja nur die Idee geliefert.
Ausformulieren und beweisen muss er es noch. Ich denke mal das ist der grössere Teil.
-
ChrisM schrieb:
sag mal, wie erbärmlich ist denn das hier?
Eine Prüfungsleistung von anderen erledigen lassen?!
Viele Grüße
ChrisM (Karlsruhe, auch Info 2)Wo genau siehst du das Problem? Es ist vollkommen legitim sich Hinweise zu holen, wenn man nicht weiterkommt. Und Prüfungsleistung ist wohl leicht übertrieben, das ist offensichtlich eine einzelne Teilaufgabe eines einzelnen Übungsblattes, deren gesamte Bearbeitung während des ganzen Semesters eventuell im Erwerb eines Übungsscheins resultiert.
Jester (Karlsruhe, nicht Info 2)
-
Hallo,
Jester schrieb:
Wo genau siehst du das Problem? Es ist vollkommen legitim sich Hinweise zu holen, wenn man nicht weiterkommt. Und Prüfungsleistung ist wohl leicht übertrieben, das ist offensichtlich eine einzelne Teilaufgabe eines einzelnen Übungsblattes, deren gesamte Bearbeitung während des ganzen Semesters eventuell im Erwerb eines Übungsscheins resultiert.
nun, vor nicht mal einer Woche hat unser Übungsleiter in dem Info2-Portal ausdrücklich in einem eigenen Thread darauf hingewiesen, dass zu deutliche "Tipps" seitens anderer Studenten (die teilweise schon vollständige Lösungswege waren) nicht erwünscht sind, weil die Übungsblätter eigenständig bearbeitet werden sollen. Und jetzt wird also einfach in einem anderen Forum gefragt, nachdem die "offizielle Quelle" versiegt ist?
Und IMHO gibt es auch einen Unterschied, ob man ein Übungsblatt zusammen mit Kommilitonen erarbeitet oder einfach mal die Fragestellung in einem öffentlichen Forum anonym einstellt und wartet, ob was Brauchbares zurückkommt.
Uebrigens findet man die Loesung ganz leicht, wenn man nach "fehlender zahl algorithmentechnik" googelt- auf einem Loesungsblatt von Karlsruhe. Und nein, das habe nicht ich entdeckt; ich habe davon erst erfahren, nachdem ich nach ca. zwei Stunden und einer falschen Loesung auf eine eigene Loesung gekommen bin (die zwar auch nicht 100%-ig korrekt ist, aber das ist ja egal).
Chris
-
Hm. Irgendwo hast du schon Recht, Chris. Ich werde mich in Zukunft hier noch mehr zurückhalten. Selber denken ist halt gerade für Informatiker wichtig. Wobei viel wichtiger ist sein Gehirn zu trainieren als immer zu einer richtigen Lösung zu kommen.
-
Hallo,
hustbaer schrieb:
Hm. Irgendwo hast du schon Recct, Chris. Ich werde mich in Zukunft hier noch mehr zurückhalten. Selber denken ist halt gerade für Informatiker wichtig. Wobei viel wichtiger ist sein Gehirn zu trainieren als immer zu einer richtigen Lösung zu kommen.
eben, so sehe ich das auch. Deswegen habe ich meine eventuell falsche Lösung jetzt auch stehen lassen, um zu sehen, ob der Tutor das gleiche Problem wie ich sieht oder ob sie vielleicht sogar "durchgeht".
Nachdem heute übrigens Abgabeschluss war, kann ich ja auch sagen: Deine Idee ist genau die richtige. Du gehst bitweise vor und guckst, welcher Zustand auf dem jeweiligen Bit häufiger vorkommt (den hat deine fehlende Zahl nicht). Das entscheidende ist nur, dass du alle "falschen" Lösungen nach jeder Iteration wegstreichst, sich deine Liste also jedes Mal (in etwa) halbiert. So kommst du unter n als obere Schranke für die Laufzeit.
Chris
-
Naja wenn man bei der Aufgabe aber auf "O(n) => einmal drüber" fixiert ist (was ja nicht gerade selten der Fall ist) dann kommt man bei der Aufgabe aber nicht wirklich weiter. Von daher finde ich es nicht zu viel geholfen wenn man da sagt, dass O(n) = O(2n) = O(n + 1/2*n + 1/4*n + ...).
-
Wenn hier in Mathe Leute Lösungen "geheimhalten" würden/müssten fänd ich das ehrlich gesagt ziemlich schräg. Studium ist schon so nicht einfach (wobei zumindest hier zwischen Mathematik und Informatik schwierigkeitsmäßig Welten liegen), da muss sowas eigentlich nicht sein.
Benedikt
(Bonn, Info 2 war letztes Jahr
... mit ziemlich genau 50% Punkten aus den Übungen ;))
-
ChrisM schrieb:
nun, vor nicht mal einer Woche hat unser Übungsleiter in dem Info2-Portal ausdrücklich in einem eigenen Thread darauf hingewiesen, dass zu deutliche "Tipps" seitens anderer Studenten (die teilweise schon vollständige Lösungswege waren) nicht erwünscht sind, weil die Übungsblätter eigenständig bearbeitet werden sollen. Und jetzt wird also einfach in einem anderen Forum gefragt, nachdem die "offizielle Quelle" versiegt ist?
Ich sehe einen gewissen Unterschied zwischen einem beliebigen Forum und dem offiziellen Anlaufpunkt aller, die die Aufgabe bearbeiten wollen/müssen.
Außerdem hat er ganz explizit nur nach einer Idee gefragt und auch gesagt, dass es sich um eine Übungsaufgabe handelt. Ich sehe da wirklich das Problem nicht. Offener kann man doch damit kaum umgehen.
edit: ja, es ist wichtig sein Gehirn zu trainieren, aber irgendwann ist mal der Punkt erreicht, wo man "alles" versucht hat und trotzdem nicht weiterkommt. Was spricht dagegen sich an dieser Stelle irgendwo nen Tipp zu holen? Das macht ja den vorherigen Lerneffekt nicht ungeschehen.
-
Jester schrieb:
Außerdem hat er ganz explizit nur nach einer Idee gefragt und auch gesagt, dass es sich um eine Übungsaufgabe handelt. Ich sehe da wirklich das Problem nicht. Offener kann man doch damit kaum umgehen.
edit: ja, es ist wichtig sein Gehirn zu trainieren, aber irgendwann ist mal der Punkt erreicht, wo man "alles" versucht hat und trotzdem nicht weiterkommt. Was spricht dagegen sich an dieser Stelle irgendwo nen Tipp zu holen? Das macht ja den vorherigen Lerneffekt nicht ungeschehen.
Hinzu kommt, dass es ja auch einfach die Verantwortung des Fragestellers ist. Wenn jemand einfach nur abschreiben will (was der Fragesteller hier ja definitiv nicht vorhatte), dann ist das sein Problem. Er schafft dann vielleicht mehr Prozent bei der Übung. Aber die Prüfung muss er ja auch noch bestehen, was dann dank mangelnder Übung wohl umso schwieriger werden dürfte.
Oft scheitert man an Kleinigkeiten. Da ist es imho durchaus gerechtfertigt, wenn man sich Hilfe holt. Man lernt deutlich mehr, wenn man eine Aufgabe zu 90% selbst löst, als wenn man die Aufgabe zu 0% löst und am Ende nur die offizielle Lösung nachvollzieht.
Und um Hilfe zu Fragen ist sicher nicht erbärmlich!
-
Das Problem is halt, dass viele gleich immer ne Komplettlösung posten (nicht nur hier). Und die meisten finden es auch noch schlimm, wenn man sagt, dass man nen debugger verwenden sollen, obwohl das viel mehr bringen würde, wenn man richtig debuggen lernt.
-
ChrisM schrieb:
Hallo,
sag mal, wie erbärmlich ist denn das hier?
Eine Prüfungsleistung von anderen erledigen lassen?!
Viele Grüße
ChrisM (Karlsruhe, auch Info 2)Ganz ruhig, wenns dich intressiert, ich habe eine andere/ähnliche Lösung als die hier vorgeschlagene abgegeben, weil ich die bereits durchdacht und aufgeschrieben habe. Nur dachte ich, dass ich in O(n*ln(n)) liege, und habe erst mit der Argumentation hier verstanden, dass ich eigentlich nur max. n + n/2 + n/4 + n/8 + ... =2*n lesende Zugriffe brauche. Zudem ist der Übungsschein ja nichtmal benotet...
Außerdem find ich es nichtmal schlimm auch nach Lösungen oder Lösungswegen oder zu fragen (Info jetzt weniger, aber in Matheforen mal), wenn man sich davor mit der Sache beschäftigt und das ganze dann auch nachvollzieht. Das hilft mir mehr als wenn ich gar nix mach, oder die Lösungen von jemand abschreib ohne überhaupt zu verstehen was ich da schreibe.
Gruß zurück
Student (immernoch Info 2, mal sehn wie lange noch, alles Nerds in KA)PS: Ne Ärztekarte für nächste Woche übrig?
-
ChrisM schrieb:
nun, vor nicht mal einer Woche hat unser Übungsleiter in dem Info2-Portal ausdrücklich in einem eigenen Thread darauf hingewiesen, dass zu deutliche "Tipps" seitens anderer Studenten (die teilweise schon vollständige Lösungswege waren) nicht erwünscht sind, weil die Übungsblätter eigenständig bearbeitet werden sollen. Und jetzt wird also einfach in einem anderen Forum gefragt, nachdem die "offizielle Quelle" versiegt ist?
Ich hab dieses Drecksportal nie verwendet, habe dort keine Zugang, lass mir die ÜB und Folien vom Freund aufn USB-Stick ziehen. Intressiert mich nicht wer wo Lösungen postet, wir bearbeiten die ÜB meist als Gruppe. Ich glaube nicht, dass es gewollt ist, dass jeder die ÜB "eigenständig" bearbeiten soll, vielmehr soll jeder bei der Bearbeitung mitdenken und dann eben eine eigene Lösung abgeben. Das bringt allen mehr.
-
Iss mal was
-
Was macht ihr denn so ein Drama daraus? Wer es selbst hinbekommt kann stolz auf sich sein und wer es abschreibt muss das ja mit sich selbst ausmachen. Am ende weiß doch jeder wieviel er selbst geleistet hat.
Ich finde hustbaer hat zu viel verraten (nämlich alles, der Rest ist ja nur noch Schreibarbeit) für einen ersten Tipp ein guter erster Tipp wäre der Hinweis gewesen, dass O(n) nicht immer ein oder mehrere Schleifen sein müssen die nacheinander kommen, sondern auch durchaus geschachtelt sein können, wenn man genügend Information mit jedem Schritt wegwerfen kann.
-
@ChrisM
du beginnst ja früh mit konkurrenzdenken...
-
besserwisser schrieb:
@ChrisM
du beginnst ja früh mit konkurrenzdenken...Wenn es darum ginge, hätte ich absichtlich eine falsche Lösung präsentiert
Btw, wenn man nach der Lösung mit meinen oben angegebenen Schlüsselwörtern googelt, komme jetzt ich auf Platz 1 (zu krass)
http://img294.imageshack.us/my.php?image=screenie4sz9.pngChris
-
Bin ich der einzige, der die Lösung in dem PDF der Uni Karlsruhe für wenn nicht falsch, dann doch zumindest für ziemlich wackelig hält?
Abgesehen davon, dass IMHO in Zeile 13 "<=" stehen müsste, wird da einfach ein kompletter Wert auf einen Rutsch von A nach B kopiert, und das in angeblich konstanter Zeit, obwohl genau das laut Aufgabenstellung nicht geht.
-
Hallo,
kopieren und vergleichen sind schon verschiedene Operationen, die auch unterschiedlich schnell sein können (z.B. das eine nur bitweise, das andere zahlenweise). Aber im Endeffekt ist das sowieso egal, im Notfall kopierst du halt nicht, sondern führst eine separate Liste mit, welche Indizies noch im Suchraum drin sind. Dort kannst du dann immer die entsprechenden rausnehmen, die es nicht mehr sein können (also an einer bestimmten Bitstelle "in der Mehrheit" sind).
Und der Algorithmus funktioniert, auf dem nächsten Blatt (das gerade aktuell ist) ist nämlich eine Aufgabe, wo man ihn auch wirklich mit Java implementieren soll.
Chris
