Laufzeit Algorithmus

Neue Frage »

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? smile


Vielen Dank für eure Antworten
 
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 [latex]O(n^{2})[/latex] pro Element benötigen soll, macht mich allerdings ein wenig skeptisch... welche Funktion verwendest du denn?

Mit freundlichen Grüßen
InformaTiger
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 smile
 
Neue Frage »
Antworten »


Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »