O (n!)의 예?

O (n!)의 예?

---

O(n!)함수 의 예 (코드)는 무엇입니까? 다음을 참조하여 실행하려면 적절한 수의 작업이 필요합니다 n. 즉, 시간 복잡성에 대해 묻습니다.

---

됐습니다. 이것은 아마도 제 O(n!)시간에 실행되는 함수의 가장 사소한 예일 것입니다 (함수 n에 대한 인수는 어디에 있습니까 ) :

void nFacRuntimeFunc(int n) {
  for(int i=0; i<n; i++) {
    nFacRuntimeFunc(n-1);
  }
}

---

한 가지 고전적인 예는 무차별 대입 검색을 통한 출장 세일즈맨 문제 입니다.

이 경우 N도시, 짐승의 힘 방법은 이들 각각의 모든 순열을 시도합니다 N하나는 저렴한이다 찾는 도시. 이제 N도시에 대한 순열의 수로 인해 N!복잡성이 계승됩니다 ( O(N!)).

---

참고 항목 일반적인 기능의 주문 의 섹션 빅 O 위키 백과의 기사를.

기사에 따르면 무차별 대입 검색을 통해 출장 세일즈맨 문제 를 해결하고 미성년자 에 의한 확장으로 결정 인자 를 찾는 것은 모두 O (n!)입니다.

---

문제가 있습니다 NP-complete(비 결정적 다항식 시간에서 확인 가능). 즉, 입력이 확장되면 문제를 해결하는 데 필요한 계산이 더 많이 증가합니다.

몇 가지 NP-hard문제 는 다음과 같습니다 : 해밀턴 경로 문제 ( open img ), 여행하는 세일즈맨 문제 ( open img )
몇 가지 NP-complete문제 는 다음과 같습니다 : Boolean satisfiability problem (Sat.) ( open img ), N-puzzle ( open img ), Knapsack problem ( open img ), Subgraph isomorphism 문제 ( open img ), Subset sum 문제 ( open img ), Clique 문제 ( open img ), Vertex cover 문제( open img ), 독립적 인 set 문제 ( open img ), Dominating set problem ( open img ), Graph coloring problem ( open img ),

출처 : 링크 1 , 링크 2

출처 : 링크

---

미성년자에 의한 확장으로 행렬식 찾기.

여기에 아주 좋은 설명 .

# include <cppad/cppad.hpp>
# include <cppad/speed/det_by_minor.hpp>

bool det_by_minor()
{   bool ok = true;

    // dimension of the matrix
    size_t n = 3;

    // construct the determinat object
    CppAD::det_by_minor<double> Det(n);

    double  a[] = {
        1., 2., 3.,  // a[0] a[1] a[2]
        3., 2., 1.,  // a[3] a[4] a[5]
        2., 1., 2.   // a[6] a[7] a[8]
    };
    CPPAD_TEST_VECTOR<double> A(9);
    size_t i;
    for(i = 0; i < 9; i++)
        A[i] = a[i];


    // evaluate the determinant
    double det = Det(A);

    double check;
    check = a[0]*(a[4]*a[8] - a[5]*a[7])
          - a[1]*(a[3]*a[8] - a[5]*a[6])
          + a[2]*(a[3]*a[7] - a[4]*a[6]);

    ok = det == check;

    return ok;
}

여기 에서 코드 . 거기 에서 필요한 .hpp파일 도 찾을 수 있습니다 .

---

나는 조금 늦었다 고 생각하지만 snailsort 가 O (n!) 결정 론적 알고리즘의 가장 좋은 예 라고 생각 합니다. 기본적으로 정렬 할 때까지 배열의 다음 순열을 찾습니다.

다음과 같이 보입니다.

template <class Iter> 
void snail_sort(Iter first, Iter last)
{
    while (next_permutation(first, last)) {}
}

---

주어진 배열의 모든 순열을 계산하는 모든 알고리즘은 O(N!)입니다.

---

가장 간단한 예 :)

의사 코드 :

input N
calculate N! and store the value in a vaiable NFac - this operation is o(N)
loop from 1 to NFac and output the letter 'z' - this is O(N!)

거기 간다 :)

실제 예로서-항목 세트의 모든 순열을 생성하는 것은 어떻습니까?

---

printf("Hello World");

네, O (n!)입니다. 그렇지 않다고 생각한다면 BigOh의 정의를 읽어 보시기 바랍니다.

나는 사람들이 실제로 의미하는 바에 관계없이 항상 BigOh를 사용해야하는 성가신 습관 때문에이 답변을 추가했습니다.

예를 들어, 나는 Theta (n!)에게 물어 보려는 질문이 적어도 cn! 단계와 Cn 이상! 일부 상수 c, C> 0에 대한 단계이지만 대신 O (n!)을 사용하도록 선택했습니다.

또 다른 예 : Quicksort is O(n^2) in the worst case, 기술적으로 정확하지만 (최악의 경우 힙 정렬조차도 O (n ^ 2)입니다!), 실제로 의미하는 것은 Quicksort is Omega(n^2) in the worst case.

---

Wikipedia에서

무차별 대입 검색을 통해 출장 세일즈맨 문제 해결 미성년자에 의한 확장으로 결정 인자를 찾습니다.

http://en.wikipedia.org/wiki/Big_O_notation#Orders_of_common_functions

---

C #에서

이것은 공간 복잡성에서 O (N!)가 아닐까요? 왜냐하면 C #의 문자열은 변경할 수 없기 때문입니다.

string reverseString(string orgString) {
    string reversedString = String.Empty;

    for (int i = 0; i < orgString.Length; i++) {
        reversedString += orgString[i];
    }

    return reversedString;
}

---

재귀 호출은 정확히 n이 필요합니다! 시각. 다음은 n 개의 다른 값에 대한 팩토리얼 시간을 테스트하는 것과 같은 코드입니다. n에 대한 내부 루프 실행! j의 다른 값에 대한 시간이므로 내부 루프의 복잡성은 Big O (n!)

public static void NFactorialRuntime(int n)
    {
        Console.WriteLine(" N   Fn   N!");
        for (int i = 1; i <= n; i++)  // This loop is just to test n different values
        {
            int f = Fact(i);
            for (int j = 1; j <= f; j++)  // This is Factorial times
            {  ++x; }
            Console.WriteLine(" {0}   {1}   {2}", i, x, f);
            x = 0;
        }
    }

다음은 n = 5에 대한 테스트 결과입니다. 정확히 계승 시간을 반복합니다.

  N   Fn   N!
  1   1   1
  2   2   2
  3   6   6
  4   24   24
  5   120   120

시간 복잡도 n의 정확한 함수!

// Big O(n!)
public static void NFactorialRuntime(int n)
    {
        for (int j = 1; j <= Fact(i); j++) {  ++x; }
        Console.WriteLine(" {0}   {1}   {2}", i, x, f);
    }

---

Bogosort 는 O (n!) 영역으로 모험을 떠나는 내가 만난 유일한 "공식적인"사람입니다. 그러나 그것은 본질적으로 무작위이기 때문에 보장 된 O (n!)가 아닙니다.

---

The recursive method you probably learned for taking the determinant of a matrix (if you took linear algebra) takes O(n!) time. Though I dont particularly feel like coding that all up.

---

@clocksmith You are absolutely correct. This is not calculating n!. Nor is it of O(n!). I ran it collected the data in the table below. Please compare column 2 and three. (#nF is the # of calls to nFacRuntimeFunc)

n #nF n!

0    0      1
1    1      1
2    4      2
3    15     6
4    65     24
5    325    120
6    1956   720
7    13699  5040

So clearly if performs much worse than O(n!). Below is the a sample code for calculating n! recursively. you will note that its of O(n) order.

int Factorial(int n)
{
   if (n == 1)
      return 1;
   else
      return n * Factorial(n-1);
}

---

Add to up k function

This is a simple example of a function with complexity O(n!) given an array of int in parameter and an integer k. it returns true if there are two items from the array x+y = k , For example : if tab was [1, 2, 3, 4] and k=6 the returned value would be true because 2+4=6

public boolean addToUpK(int[] tab, int k) {

        boolean response = false;

        for(int i=0; i<tab.length; i++) {

            for(int j=i+1; j<tab.length; j++) {

                if(tab[i]+tab[j]==k) {
                    return true;
                }

            }

        }
        return response;
    }

보너스로 이것은 jUnit을 사용한 단위 테스트이므로 잘 작동합니다.

@Test
    public void testAddToUpK() {

        DailyCodingProblem daProblem = new DailyCodingProblemImpl();

        int tab[] = {10, 15, 3, 7};
        int k = 17;
        boolean result = true; //expected result because 10+7=17
        assertTrue("expected value is true", daProblem.addToUpK(tab, k) == result);

        k = 50;
        result = false; //expected value because there's any two numbers from the list add up to 50
        assertTrue("expected value is false", daProblem.addToUpK(tab, k) == result);
    }

---

가장 간단한 예는 계승 함수입니다.

function factorial(n){
    let fact=1;
    for(var i=1; i<=n;i++){
        fact=fact*i;
    }
    return fact;
}

의 위에!)

참조 URL : https://stackoverflow.com/questions/3953244/example-of-on