Exemplo de O (n!)

O que é um exemplo (no código) de uma function O (n!)? Deve levar o número apropriado de operações para executar em referência a n; isto é, estou perguntando sobre a complexidade do tempo.

Ai está. Este é provavelmente o exemplo mais trivial de uma function que é executada no tempo O(n!) (Onde n é o argumento para a function):

 void nFacRuntimeFunc(int n) { for(int i=0; i 

Um exemplo clássico é o problema do vendedor ambulante através da busca por força bruta.

Se houver N cidades, o método da força bruta tentará toda e qualquer permutação dessas N cidades para descobrir qual delas é mais barata. Agora o número de permutações com N cidades é N! fazendo sua complexidade fatorial ( O(N!) ).

Consulte a seção Ordens de funções comuns do artigo da Wikipédia Big O.

De acordo com o artigo, resolver o problema do vendedor ambulante através da busca por força bruta e encontrar o determinante com a expansão por menores são ambos O (n!).

Existem problemas, que são NP-complete (verificáveis ​​no tempo polinomial não determinístico). O que significa que, se a input for dimensionada, a computação necessária para resolver o problema aumenta muito mais.

Alguns NP-hard são: Problema de caminho Hamiltoniano ( img aberto ), Problema de vendedor ambulante ( img aberto )
Alguns NP-complete são: Problema de satisfatibilidade booleana (Sat.) ( img aberto ), N-quebra-cabeça ( img aberto ), Problema de mochila ( img aberto ), Problema de isomorfismo de subgrafia ( img aberto ), Problema de sum de subconjunto ( img aberto ) Problema de clique ( img aberto ), Problema de cobertura de vértice ( img aberto ), Problema de conjunto independente ( img aberto ), Problema de conjunto dominador ( img aberto ), Problema de coloração de gráfico ( img aberto ),

Fonte: link 1 , link 2

texto alternativo
Fonte: link

Encontrar o determinante com a expansão de menores.

Muito boa explicação aqui .

 # include  # include  bool det_by_minor() { bool ok = true; // dimension of the matrix size_t n = 3; // construct the determinat object CppAD::det_by_minor 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 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; } 

Código daqui . Você também encontrará os arquivos .hpp necessários lá .

Acho que estou um pouco atrasado, mas acho que o snailsort é o melhor exemplo do algoritmo determinístico O (n!). Basicamente, ele encontra a próxima permutação de um array até que ele seja ordenado.

Se parece com isso:

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

o exemplo mais simples 🙂

pseudo-código:

 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!) 

ai está 🙂

Como um exemplo real – que tal gerar todas as permutações de um conjunto de itens?

Qualquer algoritmo que calcule toda a permutação de um dado array é O (N!).

printf("Hello World");

Sim, isso é O (n!). Se você acha que não é, sugiro que leia a definição de BigOh.

Eu só adicionei esta resposta por causa do hábito irritante que as pessoas têm de usar sempre BigOh, independentemente do que elas realmente significam.

Por exemplo, tenho certeza que a pergunta pretendia perguntar a Theta (n!), Pelo menos, cn! passos e não mais do que Cn! passos para algumas constantes c, C> 0, mas optou por usar O (n!) em vez disso.

Outra instância: Quicksort is O(n^2) in the worst case , enquanto tecnicamente correto (Mesmo heapsort é O (n ^ 2) no pior dos casos!), O que eles realmente querem dizer é Quicksort is Omega(n^2) in the worst case .

Na Wikipedia

Resolver o problema do vendedor ambulante através da pesquisa de força bruta; encontrar o determinante com a expansão por menores.

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

Em c #

Isso não seria O (N!) Na complexidade espacial? porque, string em C # é imutável.

 string reverseString(string orgString) { string reversedString = String.Empty; for (int i = 0; i < orgString.Length; i++) { reversedString += orgString[i]; } return reversedString; } 

Bogosort é o único “oficial” que encontrei que se aventura na área O (n!). Mas não é um O (n!) Garantido, pois é random por natureza.

O método recursivo que você provavelmente aprendeu ao tomar o determinante de uma matriz (se você tomou a álgebra linear) leva o tempo O (n!). Embora eu não me sinta particularmente como codificar tudo isso.

@clocksmith Você está absolutamente correto. Isso não está calculando n !. Nem é de O (n!). Eu corri, coletou os dados na tabela abaixo. Por favor, compare as colunas 2 e 3. (#nF é o número de chamadas para 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 

Então, claramente, se executa muito pior do que O (n!). Abaixo está o código de exemplo para calcular n! recursivamente. você notará que é de ordem O (n).

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

Você está certo, as chamadas recursivas devem levar exatamente n! Tempo. aqui está um código como testar tempo fatorial para n valores diferentes. O loop interno é executado por n! tempo para diferentes valores de j, então a complexidade do laço interno é 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; } } 

Aqui está o resultado do teste para n = 5, iterar exatamente o tempo fatorial.

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

Função exata com complexidade de tempo 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); }