Was ist der Unterschied zwischen Laufzeit eines Problems und die Komplexität eines Problems(Informatik)?

Question

Diese Frage ist an Themen angelehnt wie z.B Sortieralgorithmen oder sonstige Algorithmen und Datenstrukuren. Bitte die Antwort so verständlich wie möglich (also nicht so "wissenschaftlich", wie in den Bücher :)- .
Danke

Answer 1

Der Unterschied ist, dass die Laufzeit angibt, wie lange es dauert, ein Problem zu lösen, die Komplexität hingegen, wie aufwändig die Lösung ist.

Nehmen wir an, du hast die Aufgabe, den Wert einer beliebigen Anzahl von Zahlen zu verdoppeln. Der Aufwand ist sehr einfach. Er besteht aus einer einfachen Multiplikation.
Die Laufzeit ist hier linear zur Anzahl der Zahlen, die multipliziert werden. D.h. doppelte Anzahl der Zahlen bedeutet doppelte Laufzeit.

Wenn du allerdings eine beliebige Anzahl von Zahlen sortieren sollst, dann ist der Aufwand mit einem einfachen Sortieralgoritmus wesentlich größer. Es müssen im ungünstigen Fall alle Zahlen mit allen anderen verglichen werden. Die Laufzeit wächst dann mit jeder Zahl um den Betrag der Laufzeit, den dieser Algorithmus ohne diese Zahl gebraucht hat.
Die Laufzeit ist also die Fakultät von n, wenn n die Anzahl der zu sortierenden Zahlen ist.

Komplexität und Laufzeit hängen also zusammen, sind aber nicht das gleiche.

Answer 2

die laufzeit eines problems ist die länge eines kredites. die komplexilität ist die gesamte summe. ich hoffe das hilft dir weiter.