Un exemple classique est le problème du voyageur de commerce à travers la recherche par force brute.

S’il y a N villes, la méthode de la force brute essaiera chaque permutation de ces N villes pour trouver celle qui est la moins chère. Maintenant, le nombre de permutations avec N villes est N! rendre sa complexité factorielle ( O(N!) ).

Voir la section Commandes de fonctions communes de l’ article de Big O Wikipedia .

Selon l’article, la résolution du problème des vendeurs itinérants par la recherche par force brute et la détermination du facteur d’ expansion par les mineurs sont toutes les deux O (n!).

Il y a des problèmes, NP-complete (vérifiables en temps polynomial non déterministe). Ce qui signifie que si les échelles d’entrée, alors votre calcul nécessaire pour résoudre le problème augmente beaucoup plus que cela.

Certains problèmes NP-hard sont: Problème de chemin Hamiltonien ( open img ), Problème de vendeur itinérant ( open img )
Certains problèmes NP-complete sont: Problème de satisfiabilité booléenne (Sat.) ( img ouvert ), N-puzzle ( open img ), problème Knapsack ( open img ), problème d’isomorphisme de sous-graphe ( open img ), problème de sum de sous – ensemble ( open img ), Problème de clique ( open img ), problème de couverture de vertex ( open img ), problème de set indépendant ( open img ), problème de set dominant ( open img ), problème de coloration de graphe ( open img ),

Source: lien 1 , lien 2

Source: lien

Trouver le déterminant avec l’expansion par les mineurs.

Très bonne explication ici .

 # include  # include  bool det_by_minor() { bool ok = true; // dimension of the masortingx 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; } 

Code d' ici . Vous y trouverez également les fichiers .hpp nécessaires.

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

Cela ressemble à ceci:

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

l’exemple le plus simple 🙂

pseudocode:

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

Voilà 🙂

Comme exemple concret – qu’en est-il de la génération de toutes les permutations d’un ensemble d’éléments?

Tout algorithme qui calcule toute la permutation d’un tableau donné est O (N!).

printf("Hello World");

Oui, c’est O (n!). Si vous pensez que ce n’est pas le cas, je vous suggère de lire la définition de BigOh.

Je n’ai ajouté cette réponse que parce que les gens ont l’habitude d’utiliser BigOh indépendamment de ce qu’ils veulent dire.

Par exemple, je suis sûr que la question visait à demander à Theta (n!), Au moins cn! pas et pas plus que Cn! étapes pour certaines constantes c, C> 0, mais a choisi d’utiliser O (n!) à la place.

Autre exemple: Quicksort is O(n^2) in the worst case , bien que techniquement correct (Même le plus court est O (n ^ 2) dans le pire des cas!), Ce qu’ils veulent vraiment dire, c’est que Quicksort is Omega(n^2) in the worst case

Dans Wikipedia

Résoudre le problème du voyageur de commerce via la recherche par force brute; trouver le déterminant avec l’expansion par les mineurs.

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

En C #

Ne serait-ce pas O (N!) Dans la complexité de l’espace? car la chaîne en C # est immuable.

 ssortingng reverseSsortingng(ssortingng orgSsortingng) { ssortingng reversedSsortingng = Ssortingng.Empty; for (int i = 0; i < orgString.Length; i++) { reversedString += orgString[i]; } return reversedString; } 

Bogosort est le seul “officiel” que j’ai rencontré qui s’aventure dans la zone O (n!). Mais ce n’est pas un O garanti (n!) Car il est de nature aléatoire.

La méthode récursive que vous avez probablement apprise pour prendre le déterminant d’une masortingce (si vous avez pris une algèbre linéaire) prend O (n!) Temps. Bien que je n’aime pas particulièrement coder tout cela.

@clocksmith Vous avez absolument raison. Ce n’est pas en train de calculer n !. Ce n’est pas non plus de O (n!). J’ai couru il a rassemblé les données dans le tableau ci-dessous. Veuillez comparer les colonnes 2 et 3. (#nF est le nombre d’appels à 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 

Donc, clairement, si la performance est bien pire que O (n!). Voici un exemple de code pour calculer n! récursivement. vous noterez que sa de commande O (n).

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

Vous avez raison les appels récursifs devraient prendre exactement n! temps. voici un code comme pour tester le temps factoriel pour n valeurs différentes. La boucle intérieure fonctionne pour n! temps pour différentes valeurs de j, donc la complexité de la boucle interne est 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; } } 

Voici le résultat du test pour n = 5, il itère exactement le temps factoriel.

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

Fonction exacte avec la complexité du temps 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); }