Hi,

sorry hab den überblick über neue Posts verloren ...

Das Forum hat auch eine RSS-Feed, so ist das nicht.
Aber gut, ich nutze den auch nicht, schaue lieber hin und wieder so mal rein.

PS:
Darf ich jetzt C&P Deiner Mail oder nicht?
ja[...]

Aber die Quotingzeichne ändere ich jetzt nicht, da bin ich viel zu faul zu. (Privaten Kram gestrichen und noch etwas gekürzt, aber nicht geändert. Alle Fehler die vorher drin waren, sind also drin geblieben)

Aber da auch ich mich irren kann und es auch häufig tue, klapper ich das mal durch.

»» Ja, genau das meinte ich und das bedeutet eine Komplexität von
O(n*log(n)).

Nö, ich muss im Worstcase jedes _höchtens_insgesamt_genau_ 1 mal anfassen,
nicht jede Paarung.

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?

Worst Case:
S_1 = {a,b,c}
S_2 = {x,y,z}

Nötige Vergleiche:
ax
ay
az
bx
by
bz
cx
cy
cz

Dadurch, das die Listen geordnet sind und die Richtung bekannt, wären nötig:
ax
bx
cx
(bzw umgekehrt)

Dadurch, das auch noch die Länge bekannt ist _und_ das zugrundeliegende Alphabet:
ax

Da wir so viel wissen ist also aus dem ehemaligem WorstCase hier der BestCase geworden, wir können in O(1) feststellen, ob die Schnittmenge leer ist.
Schonmal nicht schlecht.
Wie sieht das denn mit zwei gleichen Mengen S_1 = S_2 aus?
S_1 = {a,b,c}
S_2 = {a,b,c}

Worst case:
aa
bb
cc

Geordnet:
aa
bb
cc

Länge und Alphabet bekannt:
aa
bb
cc

Das ist O(n).
Kann man irgendeinen Fall konstruieren, der komplizierter ist? Ich finde keinen, also ist WorstCase O(n).

Fehler gefunden?

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)

Ich glaub auch nicht dass es besser ginge als O(n),  da sich für jeden
"besseren" Ansatz (z.B mit Baumsortierung) ein Gegenbeispiel konstruieren
ließe, wo doch jedes Element angefasst werden muss.
Und die Ordnung richtet sich ja nach der _maximalen_ Zeitkomplexität.

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)! Wenn ich also
nur entscheiden will, ob die Schnittmenge leer ist und die Wahrscheinlichkeit
dafür auch relativ hoch, könnte sich der Aufwand der vorherigen Sortierung
durchaus lohnen.

Ah, BTW: das Suchen in geordneten Listen ist normalerweise O(log(n)) (per Divide&Conquer, das Übliche also), habe ich also oben irgendwo einen Fehler gemacht?

(Was nicht heißen soll, dass man im Schnitt nicht schnellere Ergebnisse
haben kann, z.B. Baumsortierung um ganze Teillisten auszuschließen, aber
das wäre jetzt für _mich_ Microoptimierung)

Ja, das wäre es durchaus, Vorsortierung ist hier wohl die einzig zulässige Optimierung.

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

1. streiche ich in beiden listen
2. vergleiche ich immer nur die beiden untersten.

(rein formal müßte ich noch verlangen dass es in den Listen keine Duplikate
gibt, aber geschenkt oder?)

Das war schon vorausgesetzt. Ist auch egal, wenn die Liste geordnet ist.(Nur funktioniert dann das Spiel unten nicht, das setzt schon voraus, das es keine Doubletten gibt.)

Überzeugt? >:)

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

so short

Christoph Zurnieden