Y a-t-il des cas où vous préféreriez un algorithme de complexité supérieur big-O temps sur celle du bas ?

Question

Sont il y a des cas où vous préféreriez complexité à temps temps la complexité ? Ou à ?

Avez-vous des exemples ?

Answer 1

Il ne peut y avoir de nombreuses raisons de préférer un algorithme d'une plus grande complexité temporelle O sur la partie inférieure:

• la plupart du temps, la baisse big-O complexité est plus difficile à réaliser et nécessite la mise en œuvre qualifiée, beaucoup de connaissances et beaucoup de tests.
• big-O cache les détails sur une constante: l'algorithme qui effectue en 10^5 est mieux de la part de big-O le point de vue qu' 1/10^5 * log(n) (O(1) vs O(log(n)), mais pour les plus raisonnables n le premier fonctionnera mieux. Par exemple le meilleur de la complexité pour la multiplication matricielle est - O(n^2.373) , mais la constante est si élevé que personne (à ma connaissance) de calcul des bibliothèques de l'utiliser.
• big-O a du sens lorsque vous calculez sur quelque chose de grand. Si vous avez besoin de trier tableau de trois numéros, il importe vraiment peu de savoir si vous utilisez O(n*log(n)) ou O(n^2) de l'algorithme.
• parfois, l'avantage de la minuscule temps de complexité peut être vraiment négligeable. Pour exemple, il existe une structure de données tango arbre qui donne un O(log log N) du temps de la complexité pour trouver un article, mais il y a aussi un arbre binaire qui trouve les mêmes en O(log n). Même pour un grand nombre de n = 10^20 la différence est négligeable.
• le temps de la complexité n'est pas tout. Imaginer un algorithme qui s'exécute en O(n^2) et exige O(n^2) de la mémoire. Il pourrait être préférable à d' O(n^3) du temps et O(1) de l'espace lorsque la n est pas vraiment grand. Le problème, c'est que vous pouvez attendre pendant une longue période, mais très doute, vous pouvez trouver une RAM assez grand pour l'utiliser avec votre algorithme
• la parallélisation est un bon élément dans notre distribués dans le monde. Il y a des algorithmes qui sont facilement parallélisables, et il ya certains qui ne sont pas paralléliser. Parfois de sens pour exécuter un algorithme sur 1000 produits de base des machines avec une plus grande complexité que l'utilisation d'une machine avec un peu plus de complexité.
• dans certains endroits (de sécurité) d'une complexité peut être une exigence. Personne ne veut avoir un algorithme de hachage qui peut hachage hyper rapide (car alors d'autres personnes peuvent bruteforce-vous un chemin plus rapide)
• bien que ce n'est pas lié à l'interrupteur de la complexité, mais certaines des fonctions de sécurité doivent être écrits de façon à prévenir l'attaque temporelle. Ils ont surtout rester dans la même classe de complexité, mais ils sont modifiés en ce sens qu'il prend toujours le pire des cas, de faire quelque chose. Un exemple est celui de la comparaison que les chaînes sont égales. Dans la plupart des applications, il est logique de fast break si les premiers octets sont différents, mais en matière de sécurité, vous aurez tout de même attendre la fin pour dire aux mauvaises nouvelles.
• quelqu'un a breveté la faible complexité de l'algorithme et il est plus économique pour une entreprise d'utiliser plus de complexité que de payer de l'argent.

Answer 2

Il y a toujours la constante cachée qui peut être situé plus bas dans l’algorithme O(log n). Si elle peut fonctionner plus rapidement dans la pratique pour les données réelles.

Il existe également des préoccupations de l’espace (par exemple en cours d’exécution sur un grille-pain).

On craint aussi développeur temps - O(log n) peut être 1000 × plus facile à mettre en œuvre et vérifier.

Answer 3

Je suis surpris que personne n'a mentionné liés à la mémoire des applications encore.

Il peut y avoir un algorithme qui a moins d'opérations à virgule flottante en raison de sa complexité (i.e. O(1) < O(log n)), soit parce que la constante devant la complexité est moindre (c'est à dire 2n² < 6n²). Peu importe, il peut toujours préférer l'algorithme avec plus de FLOP si le premier FLOP de l'algorithme est plus liées à la mémoire.

Ce que je veux dire par "mémoire", c'est que vous êtes souvent d'accéder à des données qui est constamment hors de la cache. Afin de récupérer ces données, vous devez tirer la mémoire de votre réalité de l'espace mémoire dans votre cache avant que vous puissiez effectuer votre opération. Extraction étape est souvent assez lent, beaucoup plus lent que votre opération elle-même.

Par conséquent, si votre algorithme nécessite plus d'opérations (et pourtant, ces opérations sont effectuées sur les données qui sont déjà dans le cache (et donc pas de corvée nécessaire]), il sera toujours plus performant que votre algorithme avec moins d'opérations (qui doit être effectuée sur des données en cache [et, par conséquent, nécessitent une extraction]) en termes de mur-temps.

Answer 4

Dans des contextes où la sécurité des données est une préoccupation, un algorithme plus complexe peut être préférable à un algorithme moins complex si l’algorithme plus complexe a une meilleure résistance aux attaques de chronométrage.

Answer 5

Alistra cloué, mais a échoué à fournir des exemples, je vais donc.

Vous avez une liste de 10 000 codes UPC, pour ce que votre magasin vend. Les 10 chiffres du code à barres, entier pour le prix (le prix en pièces d'un cent) et 30 caractères de la description de la réception.

O(log N) approche: Vous avez une liste triée. 44 octets si ASCII, 84 si l'Unicode. Alternativement, le traiter de l'UPC comme un int64 et vous obtenez 42 et 72 octets. 10 000 enregistrements--dans le plus haut le cas où vous êtes à la recherche à un peu moins d'un méga-octet de stockage.

O(1) approche: Ne pas stocker l'UPC, au lieu de l'utiliser comme une entrée dans le tableau. Dans les bas-cas où vous êtes à la recherche à de près d'un tiers d'un téraoctet de stockage.

L'approche que vous utilisez dépend de votre matériel. Sur les plus raisonnables moderne de configuration que vous allez utiliser le journal N approche. Je peux imaginer la deuxième méthode est la bonne réponse si pour une raison quelconque, vous êtes en cours d'exécution dans un environnement où la RAM est extrêmement court, mais vous avez beaucoup de stockage de masse. Un tiers d'un téraoctet sur un disque n'est pas une grosse affaire, de l'obtention de vos données dans une seule sonde du disque vaut quelque chose. La simple approche binaire prend 13 en moyenne. (Notez, cependant, que par le regroupement de vos clés, vous pouvez obtenir une garantie de 3 lectures et, dans la pratique, vous le cache de la première.)