¿Ejemplo de O(n!)?

5 minutos de lectura

avatar de usuario
derek largo

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

  • rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation

    –Charlie Collins

    17 de octubre de 2010 a las 12:43

  • Solo para ser pedante, te refieres a Ω(n!) [lower bound on asymptotic growth] o “tiempo proporcional a n!” [upper and lower]¡no en!) [upper bound on asymptotic growth]. Dado que O(n!) es solo el límite superior, muchos algoritmos son O(n!) de forma poco interesante, porque son O(n) u O(n log n) u O(1) o algo así.

    – jacobm

    17 de octubre de 2010 a las 14:16


avatar de usuario
sepp2k

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

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

  • Dado que este es un cálculo uno por uno de n!, esto es la definición misma de O(n!) orden de crecimiento.

    – Adán Robinson

    17 de octubre de 2010 a las 12:51

  • Pensándolo bien, ¿el método recursivo nFac afectará la complejidad temporal de este algoritmo?

    – Derek largo

    18 de octubre de 2010 a las 3:54

  • @Derek: Definitivamente es O(n!) (y más importante Θ(n!)). Y sí, la complejidad temporal de una función llamada en un ciclo afecta la complejidad temporal del ciclo. Si el bucle se ejecuta n veces y la función en el ciclo se ejecuta (n-1)! pasos, entonces un total de n * (n-1)! = n! se realizarán los pasos. Que es exactamente cómo prueba que la complejidad temporal de esta función está en Θ(n!).

    – sepp2k

    18 de octubre de 2010 a las 10:24

  • @Derek Long, el ciclo es O (n), ya que se llama de forma recursiva con (n-1), obtienes n * (n-1) * (n-2) * … * 1 = n. entonces la función es O(n!).

    – josefx

    18 de octubre de 2010 a las 10:43

  • @AdamRobinson Aunque se votó a favor, su comentario es completamente incorrecto. Cálculo de n! toma solo O (n) tiempo: un ciclo for con multiplicación. De manera similar, el cálculo de n2 no tomará un tiempo O(n2), será O(1), una sola multiplicación.

    – definición

    1 de agosto de 2017 a las 8:15

avatar de usuario
coadicto

Un ejemplo clásico es el problema del vendedor ambulante 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 permutaciones de estos N ciudades 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!)).

  • No hice DV, pero tal vez sea porque no tiene un código de muestra y no se proporciona la notación de gran o…

    – aioobe

    17 de octubre de 2010 a las 12:49

  • @aioobe: dado que la pregunta es “¿Qué es un problema O (n!)” Y la respuesta es “aquí hay uno”, no creo que tengas que decir O (n!) explícitamente …

    – claudio

    17 de octubre de 2010 a las 14:22

  • Imagina 3 ciudades. Para verificar cualquier ruta potencial, debe verificar la distancia entre dos ciudades dos veces. A->B y B->C. Tienes que empezar desde las 3 esquinas. Sume la distancia hasta la primera ciudad, por lo que en total son 3 comprobaciones, luego sume la distancia desde la 2.ª ciudad hasta la 3.ª para un total de 6 comprobaciones. eso es 3! = 6. Haz esto para 4 ciudades y los cheques se convierten en 24.

    –Eric Leschinski

    15 mayo 2012 a las 15:49


Ver el Órdenes de funciones comunes sección de la Gran O Wikipedia artículo.

Según el artículo, resolver el problema del vendedor ambulante a través de la búsqueda de fuerza bruta y encontrar el determinante con expansión por menores ambos son O(n!).

avatar de usuario
John

Cualquier algoritmo que calcula todas las permutaciones de una matriz dada es O(N!).

Hay problemas, que son NP-complete(verificable en tiempo polinomial no determinista). Lo que significa que si la entrada se escala, entonces su cálculo necesario para resolver el problema aumenta más que mucho.

Alguno NP-hard problemas son: Problema del camino hamiltoniano( abrir imagen ), Problema del vendedor ambulante( abrir imagen )
Alguno NP-complete problemas son: Problema booleano de satisfacibilidad (Sat.)( abrir imagen ), N-rompecabezas( abrir imagen ), Problema de mochila( abrir imagen ), Problema de isomorfismo de subgrafo( abrir imagen ), Problema de suma de subconjuntos( abrir imagen ), problema de la camarilla( abrir imagen ), Problema de cobertura de vértices( abrir imagen ), Problema de conjuntos independientes( abrir imagen ), Problema del conjunto dominante( abrir imagen ), Problema de coloreado de grafos( abrir imagen ),

Fuente: enlace 1, enlace 2

texto alternativo

Fuente: Enlace

  • NP significa no determinista Polinomio, es decir, más rápido que el tiempo exponencial (pero solo en teoría). Factorial es más lento que exponencial, en teoría y práctica. Entonces, esto es totalmente irrelevante.

    – Patatas

    18 de octubre de 2010 a las 6:39


avatar de usuario
Gabi Purcarú

Creo que llego un poco tarde, pero encuentro especie de caracol ser el mejor ejemplo de algoritmo determinista O(n!). Básicamente, encuentra la siguiente permutación de una matriz hasta que la ordena.

Se parece a esto:

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

  • NP significa no determinista Polinomio, es decir, más rápido que el tiempo exponencial (pero solo en teoría). Factorial es más lento que exponencial, en teoría y práctica. Entonces, esto es totalmente irrelevante.

    – Patatas

    18 de octubre de 2010 a las 6:39


Hallar el determinante con expansión por menores.

muy buena explicacion aquí.

# 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 aquí. También encontrará lo necesario .hpp archivos allá.

¿Ha sido útil esta solución?