Laufzeit Algorithmus |
26.02.2017, 15:07 | Auf diesen Beitrag antworten » |
DreadPirateRoberts | Laufzeit Algorithmus Hallo zusammen, ich habe eine kurze, ich denke schnell zu beantwortende Frage. Wenn ich einen Algorithmus habe, der n Elemente bearbeiten soll. Die Elemente werden erst sortiert, was die Bearbeitungszeit auf O(n^2) pro Element reduziert. Ich habe ja N-Elemente, daraus ergibt sich ja zuerst schoneinmal die Laufzeit von O (n^3), denn O(N^2*n)! Wenn ich jetzt ein möglich schnelles Sortierverfahren benutze, zB Radix sort oder Merge, ändert sich dann die Laufzeit auf O(n^4) bei Radix, bzw O(n^4 log n) bei Merge? werden die Sachen denn aufmultipliziert oder ist das kompletter Mumpitz? Vielen Dank für eure Antworten |
|
|
27.02.2017, 08:34 | Auf diesen Beitrag antworten » |
InformaTiger | RE: Laufzeit Algorithmus Hallo DreadPirateRoberts, grundsätzlich ist es so, dass für eine grobe Abschätzung der Laufzeit die Anzahl der verschachtelten Schleifen verwendet wird. Je mehr Schleifen desto länger die Laufzeit. Innerhalb der Schleifen können natürlich Funktionsaufrufe stattfinden, diese werden bei einer einfachen for-Schleife n mal ausgeführt. Wenn also deine Funktion die du aufrufst ebenso eine Lineare Komplexität aufweist, hättest du als Gesamtergebnis eine Quadratische Laufzeit. Dass deine Sortierfunktion pro Element benötigen soll, macht mich allerdings ein wenig skeptisch... welche Funktion verwendest du denn? Mit freundlichen Grüßen InformaTiger |
28.02.2017, 16:15 | Auf diesen Beitrag antworten » |
DreadPirateRoberts | RE: Laufzeit Algorithmus Der Spaß ist so vorgegeben - es geht mir hauptsächlich u die Bestätigung, dass ich multiplizieren muss |
|
Verwandte Themen
Die Beliebtesten » |
Die Größten » |
|
Die Neuesten » |
|