Laufzeit Fakulät vs Exponentiell?
-
Macht es eigentlich einen großen Unterschied ob ein Algorithmus eine Laufzeit von O(n!) oder eine exponentielle Laufzeit hat?
-
sdfsfsadf schrieb:
Macht es eigentlich einen großen Unterschied ob ein Algorithmus eine Laufzeit von O(n!) oder eine exponentielle Laufzeit hat?
n! wächst schneller als jede k^n.
naja, wenn ich 32 elemete hab, ist 2^32 nur 4294967296, das rechnet man schonmal durch.
32! ist leider 2,6313083693369353016721801216e+35wenn man also nen n! auf nen 2^n umstellen kann, ist das ein fetter gewinn. ich kann mich nur an keinen fall erinnern, wo das vorkam.
-
Aha und was ist der Unterschied zwischen exponentiell und polynomiell?
-
asdfasdfasf schrieb:
Aha und was ist der Unterschied zwischen exponentiell und polynomiell?
expo ist k^n
poly ist n^kexpo wächst schneller als jedes poly
-
Aber nichts geht über Ackermann!
-
OT: Hat die Ackermannfunktion eigentlich noch einen anderen Zweck als Rechner an die Grenzen zu bringen?
-
Ist ein eher theoretisches Werkzeug. Brauchste zum Beiuspiel in der Berechenbarkeitstheorie um ein paar Sachen zu zeigen (z.B. loop-Berechenbarkeit ist weniger als while-Berechenbarkeit), aber direkt praktisch ist sie glaub zu nix zu gebrauchen.
-
Was ist mit dem fleissigen Biber?
Bye, TGGC (Demo or Die)
-
Die Busy-Beaver-Funktion ist doch garnicht erst berechenbar.
Interessant an ACK ist, dass sie die erste bekannte totale, nicht primitiv rekursive Funktion war. Damals gabs die Vermutung, mit primitiver Rekursion hätte man die intuitiv berechenbaren Funktionen erfasst. Wie bei der Church'schen These heute. Durch ACK musste dann das Konzept erweitert werden zu allgemeinerer Rekursion, µ-rekursion, Turing Maschinen und so nem Zeug
-
Walli schrieb:
OT: Hat die Ackermannfunktion eigentlich noch einen anderen Zweck als Rechner an die Grenzen zu bringen?
die verzeichnisgröße bei einer sorte von dynamischen hashtables wachst mit der inversen ackermannfunktion der anzahl der zufälligen einfügungen und löschungen. also leider ist sie nicht konstant, aber sowas von flach, das ist geradezu unheimlich.
-
Jo, das stimmt, ACK-1 ist auch geil. Wirkt zwar nicht so extrem wie ACK, ist es aber eigentlich genauso.
