 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
|
|
26.02.2017 15:07 |
|
|
InformaTiger 
Tripel-As
Dabei seit: 19.02.2013
Beiträge: 228
Herkunft: Südtirol
 |
|
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 ![[latex]O(n^{2})[/latex]](http://www.matheboard.de/latex2png/latex2png.php?O(n^{2})) pro Element benötigen soll, macht mich allerdings ein wenig skeptisch... welche Funktion verwendest du denn?
Mit freundlichen Grüßen
InformaTiger
__________________
Why do Java developers wear glasses? Because they can't C#
|
|
|
27.02.2017 08:34 |
|
|
|
|
Der Spaß ist so vorgegeben - es geht mir hauptsächlich u die Bestätigung, dass ich multiplizieren muss
|
|
|
28.02.2017 16:15 |
|
|
|
