二項係数関数階乗または多項式の増加です。

Question

単語のリストを指定するアルゴリズムを作成しました。その単語のリスト内の4つの単語のそれぞれの固有の組み合わせを（順序に関係なく）チェックする必要があります。

チェックすべき組み合わせの数、xは、n、リスト内の単語の総数であり、rは私の場合、各組合せにおけるワードの数、であるx = n!/(r!(n-r)!)すなわち、二項係数を用いて計算することができます。常に4なので、関数はx = n!/(4!(n-4)!) = n!/(24(n-4)!)です。したがって、合計単語数がnであるため、チェックする組み合わせの数が増えますので、x、したがっては、因子的にはに増えますか？

ので、今ではnが成長多項式としてを育てるように見える、私はWolframAlphaがx = (n^4)/24 − (n^3)/4 + (11.n^2)/24 − n/4として、この機能を書き換えることができたということです何を投げましたか？それはどちらですか？ Rの固定値について

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

Answer 1

、この関数はO（N^R）です。あなたの場合、r = 4、それはO（n^4）です。

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! 

これは、nで第四次多項式である：分子内の用語のほとんどは分母によって相殺されるためです。