Exemple de complexité temporelle exponentielle dans le monde réel
je suis à la recherche d'un exemple intuitif, réel d'un problème qui prend (dans le pire des cas) la complexité exponentielle de temps à résoudre pour un discours que je donne.
Voici des exemples pour d'autres complexités de temps que j'ai trouvé avec (beaucoup d'entre eux pris de cette question ainsi ):
- O (1) - Déterminer si un nombre est impair ou Pair
- O (log n) - recherche d'un mot dans le dictionnaire (à l'aide de de recherche)
- O(N) - la lecture d'un livre
- O(N log n) - tri d'un jeu de cartes à jouer (en utilisant merge sort)
- O (N^2) - vérifier si vous avez tout sur votre liste d'achats dans votre chariot
- O (infini) - lancer une pièce de monnaie jusqu'à ce qu'elle atterrisse sur des têtes
des idées?
4 réponses
- O(10^N): essayer de casser un mot de passe en testant toutes les combinaisons possibles (en supposant un mot de passe numérique de longueur N)
p. S. pourquoi votre dernier exemple est-il de complexité O(infini) ? c'est la recherche linéaire O(N) .. il y a moins de 7 milliards de personnes dans le monde.
La force brute de la solution du problème du voyageur de commerce est O(n!) qui est approximativement O(N^N) 151910920"
Une force brute et naïve n-reines solution du problème.
Vous devez placer n reines sur un n*n conseil d'administration, sans qu'elles soient prises par d'autres.
while there are untried configs,
go to next solution and
test it
en supposant que chaque reine est sur une rangée donnée, il y a n possibilités pour la reine d'être placée et n pour les (n-1) autres reines (parce que les rangées doubles ne sont pas vérifiées).
par conséquent, vous avez une o (n^n) complexité
Qu'en est-il de trouver un sous-ensemble d'entiers dans un ensemble tel que leur somme est une valeur désignée X?
je crois que cela a une complexité de O(2^(n/2))