복

ersten ich hab den neuen zettel ancestral den wetzten ist schon 최대 ein humility

Material, erstens über Hennessy-Mühlen-Logik, was wir auch schon für den vorletzten Zettel brauchen, was ich also tödlichst heute nochmal anreißen sollte,

und was ich unterirdisch noch anbrenne, ist dazu immer.

Und zum anderen über Fixpunkte, also sechs gewissermaßen Hennessy-Mühlen-Logik und Fixpunkt-TOD zusammen.

Das muss man sich nicht selber ausdenken, das kommt schon auch noch in der Prolese.

Das ist eine Kombination von Hennessy-Mühlen-Logik und Fixpunkten besser bekannt als der Müh-Kalkül.

Das ist ein Erfinder, wie wir dieses Jahr hier Blockführung hatten.

Extra Kosen.

Das ist also das Thema nächste Woche.

Ja, wir hatten noch ein bisschen Schulden. Und zwar mussten wir uns klar machen, warum dieser Partition-Refinement-Algorithmus,

warum der in O von M mal M läuft, wobei M die Anzahl Knoten und M die Anzahl Konzents.

So, da müssen wir etwas importieren, was ich jetzt nicht mehr geschafft habe mir anzulesen.

Ich verstehe, es ist auch anhand Stichwort ungefähr, aber vielleicht erinnert sich jemand wieder mal aus Hello World Seminar oder so etwas genau dran.

Also lexikalisches Sortieren.

Stichwort.

Also normalerweise können wir ja bestenfalls in O von M log N sortieren, es sei denn wir wissen was über die Schlüsse.

Lexikografisches Sortieren, also nach alphabetischer Reihenfolge der Schlüssel, ist nun etwas, wo wir definitiv etwas über die Schlüssel wissen.

Und in der Tat lexikalisch sortieren, das können wir im

O von N plus K, da ist N die Länge der zu sortierenden Liste

und K ist die Alphabetgröße, also sowas wie 26 oder so.

So, also das geht in O von N plus K.

Siehe EU-Hopcroft an M.

So, die Idee wie man das macht ist, italiertes Radix-Sort.

So, damit habe ich so eine ungefähre Vorstellung, wie das geht.

Kann ja auch ungefähr denken, warum O von N plus K rauskommt, aber genau nachgucken konnte ich es leider nicht mehr, weil ich noch eine zweite Folie zum Heutevorzubereiten hatte,

wo ich es mir weniger gut leisten könnte, für nicht andersrums dazustehen, weil da mir Leute da sind um zu gucken.

Also ganz müde Veranstaltungen hier vorerst an der Stelle verloren.

Ja, noch eine Änderung aus Hello World, wie das genau geht mit dem iterierten Radix-Sort für lexikalisches Sortieren.

Ich habe gerade gesagt, Radix-Sort kann ich alle fünf Stellen von der Post beizahlen.

Das ist glaube ich das, was etabliert.

Das heißt, die Sachen alles fünf Stellen. Man könnte auch sagen, wer dir das Bucket-Sort nämlich macht.

Okay, ich fange mit der letzten Stelle an, also der am wenigsten wichtigen.

Dann haue ich das in die Buckets. Wie lange brauche ich dafür?

Da brauche ich erstmal, ist das schlimmer als lineare Länge?

Sollte nicht.

Naja, ich muss noch irgendwie auf die Buckets zugreifen.

Das kann ja eine verketzte Liste sein.

Ich weiß, wenn ich mein Input-Ding habe, wie groß die Buckets maximal sein müssen.

Dann kann ich sagen, ich mache jeden Bucket so groß wie meine Input-Liste und kann auf jeden Fall von eins bis zwei Array das Ding rein tun.

Dann haben wir linear den ersten Sortierschritt nach letztem Buchstaben.

Dann muss ich den Buckets nach das quasi rausnehmen, sodass die Sortierung nach der letzten Stelle erhalten bleibt.

Dann mache ich das Ganze mit der vorletzten Stelle. Bei der Sortierung nach der letzten Stelle war es schon.

Wenn ich das in der Reihenfolge wieder mache, bleibt die auch erhalten.

Dann habe ich nach den letzten beiden Sortierungen weiter gemacht.

Das Rausnehmen kostet wahrscheinlich immer O von N, weil ich Dinge irgendwo herausnehmen muss.

Das nächste Wiederreintun kostet O von N.

Der Trick in der Aufwandsanalyse ist, dass die Länge der Postweizsahler immer konstant ist.

Das ist hier eben nicht so. Deswegen ist bei der Analyse noch nicht klar, warum da O von N plus K auskommt.

Ich mache das so oft nacheinander, wie die Buchstaben maximal lang sind.