total geordnete Menge, Laufzeit |
| 29.04.2010, 18:13 | Hellboy256 | Auf diesen Beitrag antworten » | ||||
| total geordnete Menge, Laufzeit Was ist eine total geordnete Menge? Mein Antwort: Wenn zwei verschiedene Elemente x,y € M dann gilt x<y oder y<x und die Elemente liegen in M geordnet vor, d.h. M:= {y0, y1, y2,..., y(n)} wobei gilt y0<y1<y2<y3...<y(n) stimmt das? Und dann wäre noch die Frage: Sie M eine total gordnete Menge und sei N={y0,y1,...y(n-1)} eine Teilmenge von M mit y0<y1<...<y(n-1). Um nachzuprüfen, ob ein beliebiges Element x von M in N enthalten ist, kann man x mit dem mittleren Element y(n/2) vergleichen und dann in der vorderen bzw. hinteren Hälfte suchen. Nun soll die asymptotische Laufzeit mit dem Master Theorem berechnet werden! Also als Laufzeit hätte ich mal T(n) = 2*T(n/2)+1 könnte das stimment? |
||||||
| 30.04.2010, 17:48 | Elvis | Auf diesen Beitrag antworten » | ||||
RE: total geordnete Menge, Laufzeit
Stimmt
Das stimmt nicht. 1. M muss nicht endlich sein, also kann man die Element nicht nummerieren. 2. Eine Menge ist durch ihre Elemente vollständige bestimmt, die Reihenfolge der Aufschreibung kann also keine Rolle spielen, auch nicht die Reihenfolge einer i.a. unmöglichen Nummerierung. |
||||||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|
