Grobanalyse

[Bort]

Hey!

Meine HÜ besteht darin den folgenden Algorithmus grob zu analysieren.

Also wieviele Abfragen er mir min., max. und im schnitt machen muss.

also mind. zwei wenn B1[n] <B2[n];
max. 2*n wenn alles gleich ist;

aber beim durchschnitt blick ich echt nicht durch.

ich hab zwar das ergebnis schon vor mir, kopiert von einem kollegen, aber ich will wissen wie man darauf kommt. (bei ihm versteh ich es nicht :bahnhof: - er ist weniger der erklärer, eher mehr der versteher.

Type
Bit = (0..1)
Result = (lower, equal, greater)

Result Compare(↓int n ↓Bit b1[n] ↓Bit b2[n]){
  For (int i=n-1..0){
     If (b1[i]==b2[i]) {}
     ElseIf (b1[i]<b2[i]) {return lower}
     Else {return greater}
  }
  return equal
}

Noch ein paar Fehler ausgebessert und Ergänzungen gemacht.
Die Bits sind von folgendem schema:

0001
0010
0011
0100
0101
0110
0111

 

[SlaterB]

angenommen B1[n] == B2[n], warum dann nur eine?
was passiert danach?

 

[Bort]

jap ausgebessert, das waren noch denkfehler vom ersten anlauf.

ich habe jetzt noch die bitfelder ergänzt. so sind zB zwei bits aufgebaut

0100 und 1000

 

[SlaterB]

also min und max weißt du doch nun,
(edit: halt, max 2*n ist falsch)

---------

für den Durchschnitt muss man wissen, was da für Daten kommen,

wahrscheinlich soll man davon ausgehen, dass sie zufällig sind,
also ist die Wahrscheinlichkeit, dass B1[n] == B2[n] ist 50%, für die anderen ebenso,

jetzt kannst du dir mal aufmalen was so passiert, bis das Programm zu Ende ist, z.B. ist es zu Ende, wenn die B1[n] != B2[n]:
wieviel Wahrscheinlichkeit hat das und wieviele Vergleiche?

wieviel Wahrscheinlichkeit bleibt für den Rest über und welches Ereignis ist das am nächsten interessante?
offensichtlich B1[n] != B2[n] + B1[n-1] != B2[n-1]
-> Wahrscheinlichkeit und Schritte ausrechnen,

das machst du so noch paar mal hinteinander, wie gesagt am besten als Baum auf Papier aufmalen,
dann kannst du den Endwert vielleicht schon erkennen/ abschätzen,

schlimmstenfalls aufhören, wenn nur noch eine Restwahrscheinlichkeit von wenigen Prozent unklar ist,
für die wichtigen Fälle hast du dann sowas wie:
zu 30% 3 Schritte
zu 10% 7 Schritte
zu 4% 11 Schritte
...
(Werte sind bewußt falsch)

diese Information musst du nun natürlich noch zu einem Durchschnitt zusammenfassen,
wenn dir das auch nicht bekannt ist.., naja, vielleicht erzähle ich das dann später auch noch
oder wer anders zur Abwechslung

 

[Bort]

Hmm, wieder ein Ausdrucksfehler von mir.

2*n nicht wenn die beiden gleich sind, sondern wenn das allerletzte bit größer bzw. kleiner ist.

--> n schleifendurchläufe mit je 2 abfragen

Ich hab jetz mit deiner hilfe und ner skype diskussion auch den durchschnitt ermittelt. ich denke er ist richtig, da er im unendlichen gegen 3 konvergiert

danke für die hilfe!

 

[SlaterB]

> n schleifendurchläufe mit je 2 abfragen

wenn alle Elemente gleich sind, dann hast du doch nicht 2 Abfragen pro Schleifendurchlauf