Ejemplo de O (n!)?

Question

¿Qué es un ejemplo (en código) de una función O (n!)? Debe ejecutar el número apropiado de operaciones en referencia a n; es decir, estoy preguntando sobre la complejidad del tiempo.

Answer 1

Ahí lo tiene. Este es probablemente el ejemplo más trivial de una función que se ejecuta en el tiempo O(n!) (donde n es el argumento de la función):

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

Answer 2

Un ejemplo clásico es el traveling salesman problem a través de la búsqueda de fuerza bruta.

Si hay N ciudades, el método de fuerza bruta probará todas y cada una de las permutación de estas ciudades N para encontrar cuál es la más barata. Ahora el número de permutaciones con N ciudades es N! haciendo su complejidad factorial (O(N!)).

Answer 3

el ejemplo más simple :)

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

ahí va :)

Como un ejemplo real: ¿qué hay de generar todas las permutaciones de un conjunto de elementos?

Answer 4

Encontrar el determinante con expansión por menores.

Muy buena explicación here.

# 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; 
} 

Código de here. También encontrará los archivos .hpp necesarios there.

Answer 5

Hay problemas, que son NP-complete (verificables en tiempo polinominal no determinista). Es decir, si las escalas de entrada, su cálculo necesario para resolver el problema aumenta más que un montón.

Algunos NP-hard problemas son: Hamiltonian path problem ( open img), Travelling salesman problem ( open img)
Algunos NP-complete problemas son: Boolean satisfiability problem (Sat.) ( open img), N-puzzle ( open img), Knapsack problem ( open img), Subgraph isomorphism problem ( open img), Subset sum problem ( open img), Clique problem ( open img), Vertex cover problem ( open img), Independent set problem ( open img), Dominating set problem ( open img), Graph coloring problem ( open img),

Fuente: link 1, link 2

Fuente: link

Answer 6

Consulte la sección Orders of common functions del artículo Big O Wikipedia.

De acuerdo con el artículo, resolver el traveling salesman problem a través de la búsqueda de fuerza bruta y encontrar el determinant con expansion by minors son ambos O (n!).

Answer 7

En Wikipedia

Resolver el problema del viajante de comercio a través de la búsqueda de fuerza bruta; encontrar el determinante con la expansión de menores.

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

Answer 8

Bogosort es el único "oficial" que he encontrado que se adentra en el O (n!) Zona. Pero no es un O (n!) Garantizado ya que es de naturaleza aleatoria.

Answer 9

Creo que estoy un poco tarde, pero creo que snailsort es el mejor ejemplo del algoritmo determinista O (n!). Básicamente encuentra la siguiente permutación de una matriz hasta que la ordena.

Parece que este:

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

Answer 10

El método recursivo que probablemente aprendió por tomarse el determinante de una matriz (si se toma el álgebra lineal) toma tiempo O (n!). Aunque particularmente no tengo ganas de codificar todo eso.

Answer 11

Cualquier algoritmo que calcule toda la permutación de una matriz dada es O (N!).

Answer 12

En C#

¿No sería esto O (N!) En la complejidad del espacio? porque, la cadena en C# es inmutable.

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

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

    return reversedString; 
} 

Answer 13

printf("Hello World");

Sí, esto es O (n!). Si crees que no es así, te sugiero que leas la definición de BigOh.

Solo agregué esta respuesta debido al hábito molesto que las personas tienen que usar siempre BigOh independientemente de lo que realmente signifiquen.

Por ejemplo, estoy bastante seguro de que la pregunta tenía como objetivo preguntar a Theta (n!), Al menos cn! pasos y no más que Cn! pasos para algunas constantes c, C> 0, pero eligió usar O (n!) en su lugar.

Otra instancia: Quicksort is O(n^2) in the worst case, aunque técnicamente correcta (¡Even heapsort es O (n^2) en el peor de los casos!), Lo que en realidad quieren decir es Quicksort is Omega(n^2) in the worst case.

Answer 14

@clocksmith Tienes toda la razón. Esto no está calculando n !. Tampoco es de O (n!). Lo ejecuté recolectó los datos en la tabla a continuación. Por favor compare la columna 2 y tres. (#nF es la cantidad de llamadas a 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 

Así que claramente si funciona mucho peor que O (n!). A continuación se muestra un código de muestra para calcular n! recursivamente. notarás que es de orden O (n).

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

Answer 15

Tiene razón, las llamadas recursivas deberían tomar exactamente n! hora. aquí hay un código como para probar el tiempo factorial para n valores diferentes. ¡El lazo interno corre para n!tiempo para diferentes valores de j, por lo que la complejidad de bucle interior es 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; 
     } 
    } 

Éstos son el resultado de la prueba para n = 5, es iterar tiempo exactamente factorial.

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

Función exacta con la complejidad del tiempo 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); 
    }