| paco89 |
Laufzeit eines Algorithmus bestimmen - Wie?
hallo,
ich habe mich gefragt wie man die laufzeit eines algorithmus´ berechnen kann und hab im inet folgende aufgabe dazu gefunden (s.bild im anhang).
bei der a) habe ich keine probleme. die best case-analyse ist ja nicht so schwer. im besten fall ist das gesuchte feld schon im ersten feld, sodass die best-case-analyse 1 ist.
aber mit der b) und c) habe ich so meine probleme...kann mir da jmd. evtl. weiterhelfen?
edit: also für die average-case- laufzeit habe ich eine formel im inet gefunden:
A(n) = n(1-1/2 Pr{K in E} ) + 1/2 Pr {K in E}
das Pr {K in E} steht für die wahrscheinlichkeit, dass das gesuchte K in dem array E enthalten ist. also wenn ich weiß ja aus der aufgabenstellung, dass es ein duplikat mit der wahrscheinlichkeit von 0.3 existiert. also muss ich doch nur die 0.3 eisetzen, oder?
ich habs mal gemacht und erhalte 0.7 n + 0,15
kann das stimmen?
für den worst case habe ich immer noch keine idee....
paco89 hat dieses Bild (verkleinerte Version) angehängt:
|
