Geschrieben von DreadPirateRoberts am 26.02.2017 um 15:07:
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
Geschrieben von InformaTiger am 27.02.2017 um 08:34:
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
![[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