NACHTRAG: weil letzte Nacht der Server um 4:30 abgestüzt war, (deswegen gings sicherheitshalber schonmal als mail an christoph und christian raus.)

" Leider konnte keine Verbindung zum Server hergestellt werden. (Grund: %s)"

----------------------------------------------
Hi

Wahrscheinlich die Schreibweise. Die O-Notation wird hin und wieder

verkürzt (durch n geteilt) bzw ist das 'O' eigentlich zwei verschiedene
Buchstaben, zwei verschiedene Angaben. Mach Dich einfach mal kundig über
"O-Notation", dsa Wiki ist hier glaueb ich ausnahmsweise gut, bin ich jetzt
aber zu faul, dsa zu kontrollieren.

Mein Inf-A-Vordiplom jährt sich zwar bald zum 15ten mal, aber ich hab doch
nix verwechselt. (Ich hab tatsächlich noch das "wunderbare Buch" zur
Vorlesung ausgegraben, das seit der Emiritierung der beiden Profs kein
Mensch mehr kauft, und ich bei jedem Umzug vergeblich wegzuschmeißen
versuche... :)

Ganz trivial: 2 geordnete Mengen, vergleiche die beiden kleinsten

Elemente, sind sie identisch dann sind sie im Schnitt und man streicht beide
ansonsten streicht man nur das kleinere. Das so lange bis eine Liste leer
ist.
»»

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.

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

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.

(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)

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.

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?)

Habe ich das richtig erklärt Christian? Stimmt alles?

er würde dir vielleicht antworten ...

P=(3,8,23,56,89)
Q=(2,23,89,100)

1. 3 > 2    : 2 streichen
2. 3 < 23   : 3 streichen
3. 8 < 23   : 8 streichen
4. 23 = 23  : SCHNITT ,beide 23 streichen und zu S
5. 56 < 89  : 56 streichen
6. 89 = 89  : SCHNITT ,beide 89 streichen und zu S, P leer, also Ende

also S=(23,89)

Zeitkomplexität T(n)=6 Operationen, mit n=p+q=9!

Es gilt T(n)<n-s-x wobei x hier die Restlänge der übrigen Liste am Ende ist.

Überzeugt? >:)

Gute Nacht
  Rolf

DENKAUFGABE: Wenn ich die Listen als Startwert und Deltas abspeichere
klappts genauso schnell, hehehe. Wieso?