laufzeit
-
hi,
wie kriegt man die theoretisch bestmögliche laufzeit eines algorithmus heraus?
also z.b. für das sortieren von n zahlen.
-
Hallo, blonde, blauäugige susi,
als erstes musst du dich auf eine Elementaroperation festlegen, die du beobachten willst. Beim Sortieren könnten es Vergleiche oder Vertauschungen sein. Dann schaust du dir deine Schleifen und Rekursionen an und überlegst dir die Komplexität. Dabei gehst du immer von der Möglichkeit aus (du wirst vermutlich ein paar Unterscheidungen haben), die dir am wenigsten Arbeit (Vertauschungen, Vergleiche) macht.
-
danke.
und wie beweise ich, dass man die aufgabe nicht mit einer besseren laufzeit lösen kann? (O(log(n)), anstatt O(n^3)) ?
-
Das lässt sich nur für manche Aufgaben beweisen und ist sehr speziell. Es gibt genug Probleme, wo man annimmt, dass keine besseren Algorithmen als die bisher bekannten existieren, wo es aber keiner schafft, das zu beweisen.
-
Beispiele für Beweise von Laufzeiten für Such-Algorithmen kannst du in
The Art of Computer Programming: Sorting and searching | ISBN: 0201896850
"beliebig" viele finden.
-
blonde, blauäugige susi schrieb:
danke.
und wie beweise ich, dass man die aufgabe nicht mit einer besseren laufzeit lösen kann? (O(log(n)), anstatt O(n^3)) ?die theoretisch mögliche beste laufzeit des sortierens durch vergleichen (also keine adressberechnung) mit O(log(n)*n) war schon ein großer trick. sowas gibt es ganz selten zu lesen. aber dauernd stolpert man über das einache "weil alle elemente angeschaut werden müssen, denn jedes element könnte das minimum sein, braucht die suche nach dem minimum in einem unsortierten array mindestens O(n)".