Ist das Wachstum des Binomialkoeffizienten Funktion Fakultät oder Polynom

Question

Ich habe einen Algorithmus, der eine Liste von Wörtern gegeben, muss jede eindeutige Kombination von vier Wörtern in dieser Liste von Wörtern (unabhängig von der Reihenfolge) zu überprüfen.

Die Anzahl der Kombinationen x geprüft werden, kann mit dem Binomialkoeffizient dh x = n!/(r!(n-r)!) berechnet werden, wobei n die Gesamtzahl der Wörter in der Liste enthalten ist und r ist die Anzahl der Wörter in jeder Kombination, die in meinem Fall ist immer 4, daher ist die Funktion x = n!/(4!(n-4)!) = n!/(24(n-4)!). Daher, wie die Anzahl der gesamten Wörter, n, erhöht die Anzahl der zu überprüfenden Kombinationen, x, also erhöht faktoriell richtig?

Was hat geworfen mich ist, dass Wolframalpha der Lage war, diese Funktion als x = (n^4)/24 − (n^3)/4 + (11.n^2)/24 − n/4 neu zu schreiben, so dass jetzt scheint es polynomial als n wächst zu wachsen? Also was ist es ?!

Here is a graph to visualise the growth of the function (the letter x is switched to an l)

Answer 1

Für einen festen Wert von r ist diese Funktion O (n^r). In Ihrem Fall, r = 4, ist es O (n^4). Dies ist, weil die meisten der Bedingungen im Zähler durch den Nenner aufgehoben:

n!/(4!(n-4)!) 
    = n(n-1)(n-2)(n-3)(n-4)(n-5)(n-6)...(3)(2)(1) 
    ------------------------------------------- 
    4!(n-4)(n-5)(n-6)...(3)(2)(1) 

    = n(n-1)(n-2)(n-3) 
    ---------------- 
      4! 

Dies ist ein 4. Grad Polynom in n.