Komplexitätstheorie - Zeiten
-
Ist diese Zeitordnung entsprechend der mathematischen Funktionen richtig:
Lineare Zeit:
2 * x
x ist variabel und 2 steht für einen konstanten Faktorlogarithmische Zeit:
ln(x)
x ist variabelpolynomiale Zeit:
x^2
x ist variabel und 2 steht für einen konstanten Faktorexonentielle Zeit:
2^x
2 ist der konstante Faktor und der Exponent x variabel.Stimmt das so?
Und ist die Reihenfolge von oben nach unten für den zu berechnenden Aufwand richtig?
-
nimm einfach mal eine nicht allzuklien zahl wie 100 und berechne die vier ausdrücke und sortiere.
das mußt du eh öfters mal machen, um eine vorstellung davon zu bekommen.
-
Mit Faktor meint man eigentlich eine Multiplikation.
Bei x^2 ist 2 kein Faktor sondern ein Exponent.Logarithmisch ist schneller als linear, also sollten die beiden getauscht werden.
-
nwp2 schrieb:
Mit Faktor meint man eigentlich eine Multiplikation.
-
Gibt es eigentlich eine Datenbank aller bekannten Computeralgorithmen inkl. ihrer Einteilung in welche Zeitordnung für die Komplexität sie gehören?
-
nwp2 schrieb:
Mit Faktor meint man eigentlich eine Multiplikation.
Bei x^2 ist 2 kein Faktor sondern ein Exponent.Logarithmisch ist schneller als linear, also sollten die beiden getauscht werden.
Thx
-
Datenbank schrieb:
Gibt es eigentlich eine Datenbank aller bekannten Computeralgorithmen inkl. ihrer Einteilung in welche Zeitordnung für die Komplexität sie gehören?
Nein. Aber vielleicht magst Du den Complexity Zoo.
-
Da fehlt noch was :o
O(!x)
-
Zeus schrieb:
Da fehlt noch was :o
O(!x)Kenne wenige Algos, die diese Komplexität haben.
Aber klar fehlen in dieser Aufzähluung viele durchaus übliche Komplexitäten wie O(x*log(x))