Hi

ne expliziteres Posting ist leider mit meinem Rechner abgestürzt aber ich denke folgende Argumente reichen:

Sei p,q die Länge zweier _geordneter_ Listen, dann braucht obiger Algo
höchstens p+q Vergleiche, desdewegen O(n) mit n=p+q.

Bitte genau lesen, ich _streiche_ die untersten Elemente in beide Listen,
beide sortiert und gehe linear weiter.

Das ist Best Case, denn ein Streichen _beider_ Elemente bedeutet, das der Vergleich erfolgreich war. Ist es das wirklich?

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.

Denk an die frühen Assemblersprachen wo man vor jeder Operation erstmal die Werte in ein Register laden mußte,
hier müßte ich vor jedem Vergleich mindestens einen neuen Wert in einen von 2 Register laden, ist er erstmal drinnen brauche ich ihn nie wieder anzufassen.

O(log(n)) bräuchte ich nur zum zusätzlichen Ordnen, wenns nicht bereits
wäre.

Um etwas zu ordnen, mußt Du irgendwann schon feststellen, ob es geordnet ist, Mindestkomplexität ist also O(n), im Schnitt liegen die guten etwas besser als O(n*log(n)). Bei gleichn voraussetzungen, wie oben bei den Schnittmengen, gibt es aber auch noch Pidgeonsort, das ist O(1) und funktioniert ähnlich, wie eine Hashtabelle (der 2.6er  Linuxkernel verwaltet so z.B. seine Pozesse)

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

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

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! 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.

»» Du mußt jeden einmal anfassen (n), weil Du aber nach dem Vergleich
streichen kannst (bzw eine Suche in einer sortierten Liste bekannter Länge
eh nur log(n) dauert), mußt Du nicht n-mal vergleichen, sondern nur
log(n)-mal.

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

Die Frage ist wie du n wählst, beschränken wir uns auf p,q als Längen der Listen, log() der aufgerundete log_2(). Dann gilt tatsächlich grob
T_2(p,q) = p*log(q)
was aber nur für p << q besser ist als
T_1(p,q) = p+q.

A1 sei mein Vorschlag, A2 die logarithmische Suche.

T() beschreibt die Zeitkomplexität, die Anzahl aller Operationen eines Algo. Das Landausymbol O() beschreibt dann die asymptotische Entwicklung des schlechtesten T().

Ich hab das Wochenende noch ein bißchen gegrübelt und meine mit 2 Ansätzen auf
T_3(p,q)= p* log(q/p) + p
hinzukommen, indem ich A1 und A2 kombiniere.

1. Ansatz :
(OBdA p<q) wähle ich den Streichalgorithmus und vergleiche alle Elemente {x aus P} mit denen {y aus Q die Schrittweite q/p auseinanderliegen}. Dann kann ich jedem x aus P ein Intervall der Länge q/p in Q zuordnen., wo er liegen müßte. Diese Intervalle durchsuche ich anschließend binär.

T_3 hat den Vorteil das er immer (!) kleiner als T_1, T_2 ist. Also Methode der Wahl, ich glaube auch nicht an eine Verbesserungsmöglichkeit.

Der 2. Ansatz ginge mit Divide&Conquer: stetiges halbieren beider Intervalle und zurückführen auf je 2 Teilproblem mit T(p/2,q/2). Allerdings saukomplizierte Fallunterscheidungen -  habe deswegen abgebrochen.

Wie das funktioniert? Das war mir schon klar, nur über die Notation bzgl der Komplexität herrschte doch Uneinigkeit?

Es geht um asymptotische Entwicklung!

O(n) beschreibt die Annäherung an eine Gerade bei großen Werten. Also egal ob wir n =p,q, oder p+q wählen existiert immer eine Konstante c sodass T(p,q)< c*n.

Tschau
 rolf