laufzeit zu algorithmen |
| 27.06.2005, 10:51 | wsch | Auf diesen Beitrag antworten » | ||
| laufzeit zu algorithmen Gegeben seien die folgenden Laufzeitverhalten log n, n2, 2n, n log n, n! von fünf verschiedenen Algorithmen, die das gleiche Problem lösen. Diskutieren Sie die Laufzeitverhalten und filtern Sie jeweils den effizientesten Algorithmus für kleine, mittlere und große n (element) N heraus. Nehmen wir an, dass zwei Algorithmen dasselbe Laufzeitverhalten (z.B. O(n log n)) haben. Erläutern Sie warum dies nicht bedeutet, dass beide auch die gleiche Laufzeit haben. log n ist doch das effizienteste Algorithmus für kleine, mittlere und große n´s ? (egal was für eine Zahl ich einsätzte mit log n habe ich das kleinste ergebnis) oder habe ich da was falsch verstanden? zum zweiten teil: was ist der unterschied zw. laufzeitverhalten und laufzeit? warum müssen die nicht gleich sein? vielen dank |
||||
| 27.06.2005, 11:03 | JochenX | Auf diesen Beitrag antworten » | ||
algo A braucht n rechenschritte, algo B 2n; beide liegen also in O(n) jetzt ist aber A einfach viel schneller als B. eingesehen? |
||||
| 27.06.2005, 11:15 | wsch | Auf diesen Beitrag antworten » | ||
warum liegen beide in O(n) ? wofür steht O ? |
||||
| 27.06.2005, 12:28 | AD | Auf diesen Beitrag antworten » | ||
Einfach mal googeln: http://www.pohlig.de/Unterricht/Inf2002/..._O-Kalkuels.htm |
||||
| 29.06.2005, 17:39 | wsch | Auf diesen Beitrag antworten » | ||
hab ich es richtig verstanden: Beispiel: Algo1 braucht für 10 Elemente 10 sek, für 20 Elemente 20 sek usw, hat also O(n). Algo2 braucht für 10 Elemente nur 5 sek, für 20 Elemente 10 sek usw, hat also auch O(n), aber eine halb so große Laufzeit. |
||||
| 29.06.2005, 18:15 | JochenX | Auf diesen Beitrag antworten » | ||
bei meinem beispiel braucht algo B für 5 elemente 10 zeiteinheiten (rechenschritte) wenn du dir arthurs link durchgelesen hast, dann weißt du, dass dieses O-Kalkül keine genauen sondern nur "skalierte" dinge angibt hier geht es insbesondere darum zu testen, wie sich programme bei großen n verhalten seien A und B in O(n) und C in O(n^2) B braucht vielleicht für n daten 10n rechenschritte, A nur n, C braucht irgendwas mit n^2 schritten bei wenigen n ist B also relativ ineffizient, vermutlich ist C sogar besser bei größeren n hingegen wird klar, dass völlig unabhängig vom vorfaktor B C überlegen ist hoffe das hilft |
||||
| Anzeige | ||||
|
|
||||
|
|
Verwandte Themen
| Die Beliebtesten » |
| Die Größten » |
|
| Die Neuesten » |
