polynomial |
| 15.07.2005, 14:12 | amsel | Auf diesen Beitrag antworten » |
polynomial
ich bin neu hier. kann mir jemand erklären was polynomial in bezug auf zeit bedeutet? 
danke 
|
||
| 15.07.2005, 14:27 | quarague | Auf diesen Beitrag antworten » |
ich würde da an Aufwand denken. man misst die komplexität einer Aufgabe in Abhängigkeit von der Größe. zum Beispiel n Zahlen der Größe nach sortieren braucht je nach dem wie geschickt man sich dabei anstellt einen Aufwand von günstiigstenfalls n*log(n) das heisst, wenn ich um 10 Zahlen zu sortieren eine bestimmte Zeit brauche, brauche ich für 100 Zahlen 20 mal so lange (bei 10-er log) da man n*log(n) < n² durch ein Polynom abschätzen kann, ist das noch polynomialer Zeitaufwand. Um zum Beispiel das Handlungsreisender-Problem zu lösen, ist kein Verfahren bekannt, das dies in polynomialer Zeit schafft, alle bekannten Algorithmen brauchen exponential viel Zeit, das heisst um das Problem mit n Städten zu lösen braucht man e^n Rechenschritte |
||
| 15.07.2005, 16:18 | amsel | Auf diesen Beitrag antworten » |
dankeschön |
||
|
|
Verwandte Themen
| Die Beliebtesten » |
| Die Größten » |
| Die Neuesten » |