big-o - for ループから Big O(n!) 時間の複雑さを表す方法は?

Question

例えば

の上）

for (int i=0;i<n;i++)

編集後：私の最終的な答えは

for(int i =(n - 1); i > 1; i--)
 {
         factorial = factorial * i;             
 }  
 for (int j=n-2;j<factorial;j++)
 {

 }

Answer 1

最も簡単な答えは for (int i = 0; i < Factorial(n); i++) {...

実際には、通常、O(n!) アルゴリズムは、リストのさまざまな順列をすべて試すことによって機能するアルゴリズムです。つまり、リストを並べ替えるさまざまな方法をすべて試します。1 つの例は、巡回セールスマン問題と呼ばれる、マップ内のすべてのポイントを通過する最短の線を見つけることです。すべてのポイントを通過するには、さまざまな方法をすべて試す必要があり、それは O(n!) になります。

IEnumerable<List<int>> nextPermutation(List<int> nodesLeft)
{
    if (nodesLeft.Count == 0)
    {
        yield return new List<int>();
    }
    else
    {
        for (int i = 0; i < nodesLeft.Count; i++)
        {
            List<int> newNodesLeft = new List<int>(nodesLeft);
            newNodesLeft.removeAt(i);

            foreach (List<int> subPermutation in nextPermutation(newNodesLeft)
            {
                subPermutation.add(nodesLeft[i]);
                yield return subPermutation;
            }
        }
    }
}

void main()
{
    foreach (List<int> permutation in nextPermutation(new List<int>(new int[]{1,2,3,4,5}))) {
        //every permutation of [1,2,3,4,5] will be generated here
        //this will take O(n!) to complete, where n is the number of nodes given (5 in this case)
    }
}

Answer 2

再帰が許可されている場合:

void loop(int n)
{
    if(n == 1) 
        return; // the program gets here exactly n! times

    for(int i=0; i<n; i++)
        loop(n-1);
}