Hi,

ne expliziteres Posting ist leider mit meinem Rechner abgestürzt

Ja, auch Windows hat seine Vorteile >;->

OK ... räusper ... ich streiche mindestens eins der beiden Startelemente Listen und gehe linear weiter.
D.h. nach spätestesten p+q Schritten habe ich alle gestrichen und der Algo terminiert, das ist linear.

Ja, das kommt davon, wenn man die Mails/Postings linear [sic] beantwortet. Das gilt dann aber für uns beide befürchte ich.

Denk an die frühen Assemblersprachen wo man vor jeder Operation erstmal die Werte in ein Register laden mußte,

Das gilt doch auch noch für die modernen Assemblersprachen?
Aua, aua, doch nich' gleich hauen!

(Ich hab zur Zeit und leider auch "mal wieder" eine Rechtschreibung drauf, das geht doch auf keine Kuhhaut und jetzt habe ich gerade auch noch den Absatz gelöscht auf den sich dieser Klammerinhalt bezog. Tsk tsk tsk.)

ja da habe ich was falsch abgeschrieben, Pidgeonsort schau ich mir gerne bald mal an :)

Ich putze mir gearde angelegentlich meine Sehhilfe, wenn Du zufällig gerade mit Telegraphenmasten winken solltest sehe ich das nicht.

Obwohl ich in diesem Fall auch Bloomfilter spannend fände.

Ist in Arbeit, aber da es nun auch in Javascript funktionieren muß, ist das leider nicht ganz so einfach, wie das bischen Bitschuppserei in C. Zudem wird der Bitstring, der den Bloomfilter darstellt verdammt lang. Bei 4 Hashfunktionen und den irgendwann einmal geschätzten 400 Einträgen bräuchte man für eine Fehlerrate von einem Promille 8172 Bits für den Bloomfilter. Das ist also ziemlich genau ein MiB (hier gesetzt: Byte == Oktet). Es ist zwar durch Kompression eine theoretische Ersparnis von rund 30% möglich, aber das ist erstens kompliziert und zweitens: Dekompression in Javascript? Das ist dann wirklich nur noch theoretisch, aber mit Sicherheit nicht mehr praktikabel.

Na, Best- und Worstcase werden schon meist angegeben, wenn sie sich
signifikant und begründbar unterscheiden. Ist eine wichtige
Entscheidungshilfe. BestCase hier oben ist ja schließlich O(1)!

Bitte? Ne, dazu müßte eine Liste einelementig sein!

Nein, unter unseren Voraussetzungen wie gezeigt nicht.
Voraussetzungen waren:

• geordnete Liste
• keine Doubletten
• bekannte Länge der Listen
• bekanntes Alphabet
• bekannte Länge des Alphabets
• alle Listen in gleicher Richtung sortiert

In diesem Fall tritt BestCase ein falls S_1 != S_2, es ist nur noch ein Vergleich nötig. Gut, dazu müßte der generische Algorithmus etwas geändert werden, aber das schlägt sich nicht auf die Komplexität nieder.

Ein Bestcase ist wenn der letzte der einen Liste kleiner ist als der erste der anderen Liste (aufsteigend geordnet) und es deswegen keinen Schnitt gibt. Trotzdem mußt du erst zum Ende der einen Liste gelangen.

Bei unseren Bedingungen wäre das sogar WorstCase: beide Listen haben nicht nur die gleiche Anzahl Elemente, sondern sogar die gleichen Elemente: S_1 = S_2.
Allerdings würde ich hier wieder die Bedingungen ausnutzen können: da Alphabet und Länge der Listen bekannt sind, hier vor allem die Länge des Alphabets und das es keine Doubletten gibt, kann ich das gut mittels Divide&Conquer angehen. AverageCase also O(log(n)), BestCase O(1).

Ah, eine Bedingung habe ich ganz unterschlagen: als Elemente der Listen sind natürlich nur Elemente des Alphabets zulässig, keine Kombinationen. Das war mein Fehler, den mal wieder keiner gesehen hat.

Aber gut: Selbsterkenntnis ist der erste Weg zur Besserung, gelle? ;-)

Das hieß für mich immer O(n*log(n)), aber ich lasse mich gerne eines besseren belehren.

[Rolfs sorgfältige Erklärung]

Ah, danke, das hat geholfen!

Hoffe ich zumindest, aber das würde dann ja wieder an mir selber liegen, nicht an Deiner Erklärung.

so short

Christoph Zurnieden