Vergleich des (Zeit-)Wachstum von Ordnungsklassen |
| 27.01.2022, 13:40 | Enomine | Auf diesen Beitrag antworten » |
| Vergleich des (Zeit-)Wachstum von Ordnungsklassen wir beschäftigen uns mit Berechenbarkeit und Komplexität. In dieser Vorlesung sollen wir zu vorhandenem Code Laufzeitanalysen machen. Dazu benutzen wir die Ordnungsklassen O(...). So kann z.B. heraus kommen, dass unser Code in O(n²) liegt, falls wir 2 geschachtelte for-Schleifen haben, die je über die gesamte Eingabe laufen. Jetzt gibt es aber auch andere und kompliziertere Fälle. Z.B.: O(m² * (l über m)) Wir haben gelernt, dass wir z.B einen Fall von O(m² * m³) einfach nach O(m^5) nach oben abschätzen. Das möchten wir mit der Zeile O(m² * (l über m)) auch machen. Wir sind uns aber unsicher wo (l über m) einzuordnen ist in: konstant < logarithmisch < polylogarithmisch < linear < linearithmisch < quadratisch < polynomial < exponentiell < faktoriell Siehe auch https://de.wikipedia.org/wiki/Komplexit%...ankenfunktionen Dort kommt ein (n über k) [bzw. (l über m)] nicht vor. Können wir m² nach (l über m) abschätzen? Wohin können wir (l über m) abschätzen, falls wir dies müssten (was wir in diesem Fall nicht müssen) Kann man (l über m) nach irgendwas exponentiellen abschätzen, oder muss man (l über m) immer faktoriell abschätzen und dann nach l! oder nach m!? Dankeschön Michael |
||
| 27.01.2022, 13:53 | URL | Auf diesen Beitrag antworten » |
| RE: Vergleich des (Zeit-)Wachstum von Ordnungsklassen Meinst du mit (l über m) den Binomialkoeffizienten? Der ist doch Null für m>l 
|
||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|
