| Die letzten 10 Beiträge |
| Batista |
Top erklärt 
Ich meld mich wieder wenn was unklar ist. |
| eulerscheZahl |
Das kommt auf den Algorithmus an.
Mergesort geht immer in ![[latex]\mathcal{O}(n\cdot\log(n))[/latex]](http://www.matheboard.de/latex2png/latex2png.php?\mathcal{O}(n\cdot\log(n))) , während es bei Quicksort auch n^2 sein kann. |
| Batista |
Wir haben n-elmente und wir wollen diese sortieren. Was ist worst case? und wie groß ist es?
Die Sortierverfahren haben mindestens eine Laufzeit von O(n *log n), sind doch sehr gute Algorithmen, die das erfüllen? |
| eulerscheZahl |
Meinst du, weil in deinem Script das minimal fett geschrieben ist?
Das liegt eben am balancierten Baum, das andere Extrem wäre eine Liste, also Höhe n!
Ich hoffe, ich habe deine Frage richtig verstanden. |
| Batista |
Gibt eine Formel für die Maximalanzahl Höhe, die sich aus den Elementen errechnen lässt? |
| eulerscheZahl |
Ah, verstehe.
Bei n Elementen gibt es m=n! Anordnungsmöglichkeiten, wie du schon erkannt hast.
Und Die Höhe des Baums mit m Elementen ist ![[latex]\lceil\log_2(m)\rceil[/latex]](http://www.matheboard.de/latex2png/latex2png.php?\lceil\log_2(m)\rceil) , also nach Rücksubstitution ![[latex]\lceil\log_2(n!)\rceil[/latex]](http://www.matheboard.de/latex2png/latex2png.php?\lceil\log_2(n!)\rceil)
| Zitat: |
| Um 3 Elemente miteinander zu vergleichen benötigt man auch 3 Knoten also 2^3=8 Blätter, die dabei entstehen |
Nein, du brauchst du 6 Blätter. |
| Batista |
directupload.net/file/d/3982/rv628iaj_jpg.htm |
| eulerscheZahl |
Ich wei0 nicht, was mit einem "Entscheidungsbaum für n Elemente" gemeint ist. |
| Batista |
Kannst du folgende erklären, vielleicht sogar beweisen?
"Entscheidungsbaum für n Elemente hat eine minimale Höhe von log_2(n!)"(binären Baum)
Mein versuch :
bei n Elementen entspricht ein Blatt eins der Permutationen
Wenn man 3 Elementen haben und mit 3!=6 mögliche Anordnungen der Elementen
Um 3 Elemente miteinander zu vergleichen benötigt man auch 3 Knoten also 2^3=8 Blätter, die dabei entstehen
Wenn es n Elemente gibt dann gilt 2^n<n! ist doch im -wiederspruch zur Aussage? |
| eulerscheZahl |
Richtig.
Die Formel hast du übrigens auch im Script stehen. |
| Es sind weitere Beiträge zu diesem Thema vorhanden. Klicken Sie hier, um sich alle Beiträge anzusehen. |
