Quand est-ce que Big-O = x est classé comme inefficace?

Disons que nous avons un problème que nous avons implémenté en utilisant l'algorithme X avec O(n) ou O(log n) ou etc.... Quand la valeur de n est-elle assez grande pour que nous puissions envisager une implémentation alternative? Voyons voir si je peux m'expliquer un peu mieux.Quand est-ce que Big-O = x est classé comme inefficace?

Pour n = 10000

O (n^2) = 100.000.000

O (n) = 10.000

O (log n) = 4

. . .

Évidemment, le meilleur algorithme sera celui avec le plus bas "Big-o". Donc, disons que nous allons trier un tableau de longueur 5 en utilisant le tri par bulles, le résultat est 25, ce n'est pas si grave. Mais quand le résultat de la notation O est-il si grand que, de façon réaliste, nous devons utiliser une autre implémentation.

Source

2010-11-24 Carlos

Eh bien, cela est de répondre, jamais question la plus facile. C'est quand c'est inefficace. Autrement dit, c'est quand il court trop lentement. Je pense que vous découvrez la différence entre l'efficacité théorique par rapport à l'exécution réelle des instances spécifiques. –

Tout dépend de ce que vous essayez de faire. N'optimisez pas quelque chose avant d'avoir découvert que vous l'avez. – Quentamia

@Noon: pourquoi n'avez-vous pas mis cela comme une réponse? –

Lorsqu'il s'agit d'un goulot d'étranglement dans votre application.

Mais en général, viser des algorithmes avec la plus faible complexité, tout en permettant également la facilité de mise en œuvre.

Source

2010-11-24 01:06:08

Et pour étendre cela, généralement lors de la première mise en œuvre quelque chose, * ne vous inquiétez pas de la vitesse *. Il suffit de l'implémenter de la manière la plus simple.Ensuite, s'il s'avère que la vitesse ou la complexité est un problème, affinez-la. –

Une certaine complexité Big O ne signifie pas que vous devriez toujours l'éviter; vous devriez tirer pour des algorithmes de complexités inférieures, mais O (n^2) où n vaut 12 va courir beaucoup vite sans tenir compte du fait que O (n^2) est habituellement considéré comme une "mauvaise" complexité.

O (n^2) ne signifie pas automatiquement "trop lent"; O (n log n) ne signifie pas automatiquement "yay, c'est rapide". Si un algorithme donné tourne trop lentement, alors vous voulez réduire son temps d'exécution, et vous pouvez souvent le faire en réduisant sa complexité, mais jusqu'à ce qu'il devienne un problème, ne le faites pas.

Source

2010-11-24 01:12:56

Une solution trop inefficace quand il y a une autre solution qui est inférieure à Big-O, et donc plus efficace.

Source

2010-11-24 01:14:54 JAL

Quand il est équivalent à alt text et alpha = 1.

Source

2010-11-24 01:27:25

en utilisant la notation little-o de Landau que je vois? –

:) toute chance que vous pouvez m'expliquer ce que signifie? – Carlos

Quand est-ce que Big-O = x est classé comme inefficace?

Répondre

Questions connexes