Y a-t-il des cas où vous préféreriez un algorithme de complexité temporelle big-O supérieur à l'algorithme inférieur?

Y a-t-il des cas où vous préféreriez la O(log n)complexité O(1)temporelle à la complexité temporelle? Ou O(n)pour O(log n)?

Avez-vous des exemples?

Il peut y avoir de nombreuses raisons de préférer un algorithme avec une complexité de temps O plus élevée à celui inférieur:

• la plupart du temps, une complexité plus faible du big-O est plus difficile à atteindre et nécessite une implémentation qualifiée, beaucoup de connaissances et beaucoup de tests.
• big-O cache les détails d'une constante : l'algorithme qui fonctionne 10^5est meilleur du point de vue big-O que 1/10^5 * log(n)( O(1)vs O(log(n)), mais pour la plupart raisonnable, nle premier fonctionnera mieux. Par exemple, la meilleure complexité pour la multiplication matricielle est, O(n^2.373)mais la constante est si élevée qu'aucune bibliothèque informatique (à ma connaissance) ne l'utilise.
• big-O est logique lorsque vous calculez sur quelque chose de grand. Si vous devez trier un tableau de trois nombres, peu importe que vous utilisiez O(n*log(n))ou un O(n^2)algorithme.
• Parfois, l'avantage de la complexité temporelle en minuscules peut être vraiment négligeable. Par exemple, il y a un arbre de tango de structure de données qui donne une O(log log N)complexité temporelle pour trouver un élément, mais il y a aussi un arbre binaire qui le trouve dans O(log n). Même pour un grand nombre de n = 10^20différences, la différence est négligeable.
• la complexité du temps n'est pas tout. Imaginez un algorithme qui s'exécute O(n^2)et nécessite de la O(n^2)mémoire. Cela peut être préférable dans le O(n^3)temps et dans l' O(1)espace lorsque le n n'est pas vraiment grand. Le problème est que vous pouvez attendre longtemps, mais vous doutez fortement que vous puissiez trouver une RAM suffisamment grande pour l'utiliser avec votre algorithme
• la parallélisation est une bonne fonctionnalité dans notre monde distribué. Il existe des algorithmes qui sont facilement parallélisables, et certains ne se parallélisent pas du tout. Parfois, il est logique d'exécuter un algorithme sur 1000 machines de base avec une complexité plus élevée que d'utiliser une machine avec une complexité légèrement meilleure.
• dans certains endroits (sécurité), une complexité peut être une exigence. Personne ne veut avoir un algorithme de hachage qui peut hacher incroyablement rapide (car alors d'autres personnes peuvent vous brutaliser beaucoup plus rapidement)
• bien que cela ne soit pas lié au changement de complexité, mais certaines des fonctions de sécurité doivent être écrites de manière à empêcher une attaque temporelle . Ils restent pour la plupart dans la même classe de complexité, mais sont modifiés de manière à ce qu'il soit toujours pire de faire quelque chose. Un exemple est de comparer que les chaînes sont égales. Dans la plupart des applications, il est logique de rompre rapidement si les premiers octets sont différents, mais en termes de sécurité, vous attendez toujours la fin pour annoncer la mauvaise nouvelle.
• quelqu'un a breveté l'algorithme de moindre complexité et il est plus économique pour une entreprise d'utiliser une complexité plus élevée que de payer de l'argent.
• certains algorithmes s'adaptent bien à des situations particulières. Le tri par insertion, par exemple, a une complexité temporelle moyenne de O(n^2), pire que le tri rapide ou le fusionnement, mais en tant qu'algorithme en ligne, il peut trier efficacement une liste de valeurs à mesure qu'elles sont reçues (en tant qu'entrée utilisateur) où la plupart des autres algorithmes ne peuvent fonctionner efficacement sur une liste complète de valeurs.

Il y a toujours la constante cachée, qui peut être inférieure sur l' algorithme O (log n ). Il peut donc fonctionner plus rapidement dans la pratique pour les données réelles.

Il y a aussi des problèmes d'espace (par exemple courir sur un grille-pain).

Il y a aussi le souci du temps du développeur - O (log n ) peut être 1000 × plus facile à implémenter et à vérifier.

Je suis surpris que personne n'ait encore mentionné d'applications liées à la mémoire.

Il peut y avoir un algorithme qui a moins d'opérations en virgule flottante soit en raison de sa complexité (ie O (1) < O (log n )) soit parce que la constante devant la complexité est plus petite (ie 2 n ² <6 n ² ) . Quoi qu'il en soit, vous pouvez toujours préférer l'algorithme avec plus de FLOP si l'algorithme FLOP inférieur est plus lié à la mémoire.

Ce que je veux dire par «lié à la mémoire», c'est que vous accédez souvent à des données qui sont constamment hors du cache. Afin de récupérer ces données, vous devez extraire la mémoire de votre espace mémoire réel dans votre cache avant de pouvoir effectuer votre opération dessus. Cette étape de récupération est souvent assez lente - beaucoup plus lente que votre opération elle-même.

Par conséquent, si votre algorithme nécessite plus d'opérations (pourtant ces opérations sont effectuées sur des données qui sont déjà dans le cache [et donc pas de récupération requise]), il surclassera toujours votre algorithme avec moins d'opérations (qui doivent être effectuées sur out-of -cache data [et nécessite donc une extraction]) en termes de temps réel du mur.

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

Alistra l'a cloué mais n'a fourni aucun exemple, donc je vais le faire.

Vous avez une liste de 10 000 codes UPC pour ce que votre magasin vend. CUP à 10 chiffres, entier pour le prix (prix en centimes) et 30 caractères de description pour le reçu.

Approche O (log N): Vous avez une liste triée. 44 octets si ASCII, 84 si Unicode. Alternativement, traitez l'UPC comme un int64 et vous obtenez 42 et 72 octets. 10000 enregistrements - dans le cas le plus élevé, vous regardez un peu moins d'un mégaoctet de stockage.

Approche O (1): Ne stockez pas l'UPC, au lieu de cela, vous l'utilisez comme entrée dans le tableau. Dans le cas le plus bas, vous regardez près d'un tiers d'un téraoctet de stockage.

L'approche que vous utilisez dépend de votre matériel. Sur la plupart des configurations modernes raisonnables, vous allez utiliser l'approche log N. Je peux imaginer que la deuxième approche est la bonne réponse si, pour une raison quelconque, vous exécutez dans un environnement où la RAM est extrêmement courte, mais vous avez beaucoup de stockage de masse. Un tiers de téraoctet sur un disque n'est pas un gros problème, obtenir vos données dans une seule sonde du disque vaut quelque chose. L'approche binaire simple prend 13 en moyenne. (Notez, cependant, qu'en regroupant vos clés, vous pouvez obtenir cela à 3 lectures garanties et en pratique, vous mettriez en cache la première.)

Prenons un arbre rouge-noir. Il a accès, recherche, insertion et suppression de O(log n). Comparez avec un tableau qui a accès à O(1)et le reste des opérations le sont O(n).

Donc, étant donné une application où nous insérons, supprimons ou recherchons plus souvent que nous n'y accédons et un choix entre seulement ces deux structures, nous préférerions l'arbre rouge-noir. Dans ce cas, vous pourriez dire que nous préférons le O(log n)temps d'accès plus lourd de l'arbre rouge-noir .

Pourquoi? Parce que l'accès n'est pas notre préoccupation principale. Nous faisons un compromis: les performances de notre application sont plus fortement influencées par des facteurs autres que celui-ci. Nous permettons à cet algorithme particulier de souffrir de performances car nous réalisons des gains importants en optimisant d'autres algorithmes.

La réponse à votre question est donc simplement la suivante: lorsque le taux de croissance de l'algorithme n'est pas ce que nous voulons optimiser , quand nous voulons optimiser autre chose. Toutes les autres réponses en sont des cas particuliers. Parfois, nous optimisons le temps d'exécution d'autres opérations. Parfois, nous optimisons pour la mémoire. Parfois, nous optimisons pour la sécurité. Parfois, nous optimisons la maintenabilité. Parfois, nous optimisons le temps de développement. Même la constante dominante étant suffisamment faible pour avoir de l'importance optimise le temps d'exécution lorsque vous savez que le taux de croissance de l'algorithme n'est pas le plus grand impact sur le temps d'exécution. (Si votre ensemble de données était en dehors de cette plage, vous optimiseriez le taux de croissance de l'algorithme car il finirait par dominer la constante.) Tout a un coût, et dans de nombreux cas, nous échangeons le coût d'un taux de croissance plus élevé pour le algorithme pour optimiser autre chose.

Oui.

Dans un cas réel, nous avons effectué des tests pour effectuer des recherches de table avec des clés de chaîne courtes et longues.

Nous avons utilisé un std::map, un std::unordered_mapavec un hachage qui échantillonne au plus 10 fois sur la longueur de la chaîne (nos clés ont tendance à être guidées, donc c'est décent), et un hachage qui échantillonne chaque caractère (en théorie, réduit les collisions), un vecteur non trié où nous faisons une ==comparaison, et (si je me souviens bien) un vecteur non trié où nous stockons également un hachage, comparons d'abord le hachage, puis comparez les caractères.

Ces algorithmes vont de O(1)(unordered_map) à O(n)(recherche linéaire).

Pour un N de taille modeste, assez souvent l'O (n) bat l'O (1). Nous pensons que cela est dû au fait que les conteneurs basés sur les nœuds ont exigé que notre ordinateur se déplace davantage dans la mémoire, contrairement aux conteneurs basés sur les linéaires.

O(lg n)existe entre les deux. Je ne me souviens pas comment ça s'est passé.

La différence de performances n'était pas si grande, et sur des ensembles de données plus volumineux, celui basé sur le hachage fonctionnait beaucoup mieux. Nous sommes donc restés avec la carte non ordonnée basée sur le hachage.

En pratique, pour n de taille raisonnable, O(lg n)c'est O(1). Si votre ordinateur ne dispose que de 4 milliards d'entrées dans votre tableau, il O(lg n)est délimité ci-dessus par 32. (lg (2 ^ 32) = 32) (en informatique, lg est l'abréviation de log based 2).

En pratique, les algorithmes lg (n) sont plus lents que les algorithmes O (1) non pas à cause du facteur de croissance logarithmique, mais parce que la partie lg (n) signifie généralement qu'il y a un certain niveau de complexité à l'algorithme, et que la complexité ajoute un facteur constant plus grand que n'importe quelle "croissance" du terme lg (n).

Cependant, les algorithmes O (1) complexes (comme le mappage de hachage) peuvent facilement avoir un facteur constant similaire ou supérieur.

La possibilité d'exécuter un algorithme en parallèle.

Je ne sais pas s'il existe un exemple pour les classes O(log n)et O(1), mais pour certains problèmes, vous choisissez un algorithme avec une classe de complexité plus élevée lorsque l'algorithme est plus facile à exécuter en parallèle.

Certains algorithmes ne peuvent pas être parallélisés mais ont une classe de complexité si faible. Considérez un autre algorithme qui atteint le même résultat et peut être parallélisé facilement, mais a une classe de complexité plus élevée. Lorsqu'il est exécuté sur une machine, le deuxième algorithme est plus lent, mais lorsqu'il est exécuté sur plusieurs machines, le temps d'exécution réel diminue de plus en plus tandis que le premier algorithme ne peut pas accélérer.

Imaginons que vous implémentiez une liste noire sur un système embarqué, où des nombres entre 0 et 1 000 000 peuvent être sur liste noire. Cela vous laisse deux options possibles:

1. Utilisez un jeu de bits de 1 000 000 bits
2. Utilisez un tableau trié des entiers sur liste noire et utilisez une recherche binaire pour y accéder

L'accès au jeu de bits aura un accès constant garanti. En termes de complexité temporelle, elle est optimale. D'un point de vue théorique et pratique (c'est O (1) avec un surcoût constant extrêmement faible).

Pourtant, vous voudrez peut-être préférer la deuxième solution. Surtout si vous vous attendez à ce que le nombre d'entiers sur liste noire soit très petit, car il sera plus efficace en mémoire.

Et même si vous ne développez pas pour un système embarqué où la mémoire est rare, je peux simplement augmenter la limite arbitraire de 1 000 000 à 1 000 000 000 000 et faire le même argument. Ensuite, le jeu de bits nécessiterait environ 125 Go de mémoire. Avoir une complexité garantie dans le pire des cas de O (1) pourrait ne pas convaincre votre patron de vous fournir un serveur aussi puissant.

Ici, je préférerais fortement une recherche binaire (O (log n)) ou un arbre binaire (O (log n)) au jeu de bits O (1). Et probablement, une table de hachage avec sa pire complexité d'O (n) les battra tous dans la pratique.

Ma réponse ici La sélection pondérée aléatoire rapide sur toutes les lignes d'une matrice stochastique est un exemple où un algorithme avec une complexité O (m) est plus rapide qu'un algorithme avec une complexité O (log (m)), quand il mn'est pas trop grand.

Les gens ont déjà répondu à votre question exacte, je vais donc aborder une question légèrement différente à laquelle les gens peuvent penser en venant ici.

De nombreux algorithmes et structures de données «O (1) time» ne prennent en fait que le temps O (1) attendu , ce qui signifie que leur moyenne temps de fonctionnement est O (1), éventuellement uniquement sous certaines hypothèses.

Exemples courants: tables de hachage, extension de "listes de tableaux" (alias tableaux / vecteurs de taille dynamique).

Dans de tels scénarios, vous préférerez peut-être utiliser des structures de données ou des algorithmes dont le temps est garanti d'être absolument borné logarithmiquement, même si leur performance peut être pire en moyenne.
Un exemple pourrait donc être un arbre de recherche binaire équilibré, dont le temps d'exécution est pire en moyenne mais meilleur dans le pire des cas.

Une question plus générale est de savoir s'il y a des situations où l' on aimerait un O(f(n))algorithme à un O(g(n))algorithme , même si g(n) << f(n)comme ntend vers l' infini. Comme d'autres l'ont déjà mentionné, la réponse est clairement «oui» dans le cas où f(n) = log(n)et g(n) = 1. C'est parfois oui même dans le cas qui f(n)est polynomial mais g(n)exponentiel. Un exemple célèbre et important est celui de l' algorithme Simplex pour résoudre des problèmes de programmation linéaire. Dans les années 1970, cela a été démontré O(2^n). Ainsi, son comportement dans le pire des cas est irréalisable. Mais - son comportement de cas moyen est extrêmement bon, même pour des problèmes pratiques avec des dizaines de milliers de variables et de contraintes. Dans les années 80, les algorithmes de temps polynomiaux (telsL'algorithme du point intérieur de Karmarkar) pour la programmation linéaire ont été découverts, mais 30 ans plus tard, l'algorithme simplex semble toujours être l'algorithme de choix (à l'exception de certains très gros problèmes). C'est pour la raison évidente que le comportement de cas moyen est souvent plus important que le comportement de cas pire, mais aussi pour une raison plus subtile que l'algorithme simplex est en quelque sorte plus informatif (par exemple, les informations de sensibilité sont plus faciles à extraire).

Pour mettre mes 2 cents:

Parfois, un algorithme de complexité pire est sélectionné à la place d'un meilleur, lorsque l'algorithme s'exécute sur un certain environnement matériel. Supposons que notre algorithme O (1) accède de manière non séquentielle à chaque élément d'un très grand tableau de taille fixe pour résoudre notre problème. Ensuite, placez cette matrice sur un disque dur mécanique ou une bande magnétique.

Dans ce cas, l'algorithme O (logn) (supposons qu'il accède au disque séquentiellement), devient plus favorable.

Il existe un bon cas d'utilisation pour utiliser un algorithme O (log (n)) au lieu d'un algorithme O (1) que les nombreuses autres réponses ont ignoré: l'immuabilité. Les cartes de hachage ont O (1) met et obtient, en supposant une bonne distribution des valeurs de hachage, mais elles nécessitent un état mutable. Les cartes d'arbres immuables ont O (log (n)) met et obtient, ce qui est asymptotiquement plus lent. Cependant, l'immuabilité peut être suffisamment précieuse pour compenser de mauvaises performances et dans le cas où plusieurs versions de la carte doivent être conservées, l'immuabilité vous permet d'éviter d'avoir à copier la carte, qui est O (n), et peut donc s'améliorer performance.

Tout simplement: parce que le coefficient - les coûts associés à la configuration, au stockage et au temps d'exécution de cette étape - peut être beaucoup, beaucoup plus grand avec un problème big-O plus petit qu'avec un problème plus important. Big-O n'est qu'une mesure de l' évolutivité des algorithmes .

Prenons l'exemple suivant du Hacker's Dictionary, proposant un algorithme de tri basé sur l' interprétation des mondes multiples de la mécanique quantique :

1. Permutez le tableau au hasard en utilisant un processus quantique,
2. Si le tableau n'est pas trié, détruisez l'univers.
3. Tous les univers restants sont désormais triés [y compris celui dans lequel vous vous trouvez].

(Source: http://catb.org/~esr/jargon/html/B/bogo-sort.html )

Notez que le big-O de cet algorithme est O(n), ce qui bat tout algorithme de tri connu à ce jour sur les éléments génériques. Le coefficient du pas linéaire est également très faible (car ce n'est qu'une comparaison, pas un swap, qui se fait linéairement). Un algorithme similaire pourrait, en fait, être utilisé pour résoudre tout problème à la fois NP et co-NP en temps polynomial, puisque chaque solution possible (ou preuve possible qu'il n'y a pas de solution) peut être générée en utilisant le processus quantique, puis vérifiée dans Temps polynomial.

Cependant, dans la plupart des cas, nous ne voulons probablement pas prendre le risque que plusieurs mondes ne soient pas corrects, sans mentionner que l'acte de mise en œuvre de l'étape 2 est toujours "laissé comme un exercice pour le lecteur".

À tout moment lorsque n est borné et que le multiplicateur constant de l'algorithme O (1) est supérieur à la borne sur log (n). Par exemple, le stockage de valeurs dans un hachage est O (1), mais peut nécessiter un calcul coûteux d'une fonction de hachage. Si les éléments de données peuvent être comparés de manière triviale (par rapport à un certain ordre) et que la limite sur n est telle que log n est nettement inférieur au calcul de hachage sur un élément quelconque, le stockage dans un arbre binaire équilibré peut être plus rapide que le stockage dans un hachage.

Dans une situation en temps réel où vous avez besoin d'une borne supérieure ferme, vous devez par exemple sélectionner un heapsort par opposition à un Quicksort, car le comportement moyen de heapsort est également son comportement le plus défavorable.

Ajout aux réponses déjà bonnes.Un exemple pratique serait les index Hash vs les index B-tree dans la base de données postgres.

Les index de hachage forment un index de table de hachage pour accéder aux données sur le disque tandis que btree comme son nom l'indique utilise une structure de données Btree.

En temps Big-O, ce sont O (1) vs O (logN).

Les index de hachage sont actuellement découragés dans les postgres car dans une situation réelle, en particulier dans les systèmes de bases de données, le hachage sans collision est très difficile (peut conduire à une complexité O (N) dans le pire des cas) et de ce fait, il est encore plus difficile à faire les écraser en toute sécurité (appelé écriture en avance de journalisation - WAL en postgres).

Ce compromis est fait dans cette situation car O (logN) est assez bon pour les index et l'implémentation de O (1) est assez difficile et la différence de temps n'aurait pas vraiment d'importance.

Quand nest petit et O(1)constamment lent.

1. Lorsque l'unité de travail "1" dans O (1) est très élevée par rapport à l'unité de travail dans O (log n) et que la taille de jeu attendue est petite. Par exemple, il est probablement plus lent de calculer des codes de hachage Dictionary que d'itérer un tableau s'il n'y a que deux ou trois éléments.

ou

2. Lorsque la mémoire ou d'autres ressources non temporelles requises dans l'algorithme O (1) sont exceptionnellement grandes par rapport à l'algorithme O (log n).

1. lors de la refonte d'un programme, une procédure s'avère optimisée avec O (1) au lieu de O (lgN), mais si ce n'est pas le goulot d'étranglement de ce programme, et il est difficile de comprendre l'alg O (1). Ensuite, vous n'auriez pas à utiliser l'algorithme O (1)
2. quand O (1) a besoin de beaucoup de mémoire que vous ne pouvez pas fournir, alors que le temps de O (lgN) peut être accepté.

C'est souvent le cas pour les applications de sécurité que l'on souhaite concevoir des problèmes dont les algorithmes sont lents à dessein afin d'empêcher quelqu'un d'obtenir une réponse à un problème trop rapidement.

Voici quelques exemples du haut de ma tête.

• Le hachage de mot de passe est parfois rendu arbitrairement lent afin de rendre plus difficile de deviner les mots de passe par force brute. Ce message sur la sécurité de l'information a une puce (et bien plus).
• Bit Coin utilise un problème lent et contrôlable pour un réseau d'ordinateurs à résoudre afin de "miner" les pièces. Cela permet à la monnaie d'être extraite à un taux contrôlé par le système collectif.
• Les chiffrements asymétriques (comme RSA ) sont conçus pour rendre le déchiffrement sans les clés intentionnellement lent afin d'empêcher quelqu'un d'autre sans la clé privée de casser le chiffrement. Les algorithmes sont conçus pour être piratés dans le O(2^n)temps, espérons -le, où se ntrouve la longueur en bits de la clé (c'est la force brute).

Ailleurs dans CS, le tri rapide est O(n^2)dans le pire des cas, mais dans le cas général l'est O(n*log(n)). Pour cette raison, l'analyse «Big O» n'est parfois pas la seule chose qui vous intéresse lors de l'analyse de l'efficacité d'un algorithme.