Exemple de O (n!)?

Question

Qu'est-ce qu'un exemple (en code) d'une fonction O (n!)? Il doit prendre un nombre approprié d'opérations à exécuter en référence à n; c'est-à-dire que je pose des questions sur la complexité du temps.

Answer 1

Voilà. C'est probablement l'exemple le plus trivial d'une fonction qui s'exécute en O(n!) temps (où n est l'argument de la fonction):

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

Answer 2

Un exemple classique est le problème des vendeurs ambulants grâce à la recherche par force brute.

S'il y a N villes, la méthode de la force brute va essayer chaque permutation de ces N villes pour trouver laquelle est la moins chère. Maintenant, le nombre de permutations avec N villes est N! ce qui rend sa complexité factorielle ( O(N!) ).

Answer 3

Voir les Commandes de fonctions communes de la section de la Big O Wikipédia article.

Selon l'article, la résolution du problème du voyageur de commerce par force brute de recherche et de trouver le déterminant avec l'expansion par des mineurs sont les deux O(n!).

Answer 4

Je pense que je suis un peu en retard, mais je trouve que le snailsort est le meilleur exemple d'algorithme déterministe O (n!). Il trouve essentiellement la permutation suivante d'un tableau jusqu'à ce qu'il le trie.

Cela ressemble à ceci:

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

Answer 5

Trouver le déterminant avec l'expansion des mineurs.

Très bonne explication ici .

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

Code d' ici . Vous trouverez également le nécessaire .hpp des fichiers il .