Algorithmes Divide and Conquer - Pourquoi ne pas diviser en plus de deux parties?

Dans les algorithmes de division et de conquête tels que quicksort et mergesort, l'entrée est généralement divisée en deux (du moins dans les textes d'introduction) , puis les deux plus petits ensembles de données sont traités de manière récursive. Cela me semble logique de résoudre un problème plus rapidement si les deux moitiés prennent moins de la moitié du travail de traitement de l'ensemble des données. Mais pourquoi ne pas scinder le jeu de données en trois parties? Quatre? n ?

Je suppose que le travail de fractionnement des données dans de très nombreux sous-ensembles le rend inutile, mais je manque d'intuition pour voir qu'il faut s'arrêter à deux sous-ensembles.

J'ai également vu de nombreuses références au tri rapide. Quand est-ce plus rapide? Qu'est-ce qui est utilisé dans la pratique?

Cela me semble logique de résoudre un problème plus rapidement si les deux moitiés prennent moins de la moitié du travail de traitement de l'ensemble des données.

Ce n'est pas l'essence des algorithmes diviser pour régner. Habituellement, le fait est que les algorithmes ne peuvent pas "traiter l'ensemble du jeu de données". Au lieu de cela, il est divisé en éléments faciles à résoudre (comme le tri de deux nombres), puis résolus de manière triviale et les résultats recombinés de manière à obtenir une solution pour l'ensemble de données complet.

Mais pourquoi ne pas scinder le jeu de données en trois parties? Quatre? n?

Principalement parce que le diviser en plus de deux parties et la recombinaison de plus de deux résultats aboutit à une implémentation plus complexe mais ne modifie pas la caractéristique fondamentale (Big O) de l'algorithme - la différence est un facteur constant et peut entraîner un ralentissement si la division et la recombinaison de plus de 2 sous-ensembles crée une surcharge supplémentaire.

Par exemple, si vous effectuez un tri par fusion, vous devez maintenant trouver, dans la phase de recombinaison, le plus grand des 3 éléments pour chaque élément, ce qui nécessite 2 comparaisons au lieu de 1, de sorte que vous ferez globalement deux fois plus de comparaisons. . En échange, vous réduisez la profondeur de récursivité d'un facteur ln (2) / ln (3) == 0.63, ce qui vous donne 37% moins de swaps, mais 2 * 0.63 == 26% de comparaisons supplémentaires (et d'accès mémoire). Que cela soit bon ou mauvais dépend de ce qui coûte le plus cher dans votre matériel.

J'ai également vu de nombreuses références au tri rapide. Quand est-ce plus rapide?

Apparemment, une variante à double pivot de quicksort peut nécessiter le même nombre de comparaisons mais en moyenne 20% moins de conversions, ce qui en fait un gain net.

Qu'est-ce qui est utilisé dans la pratique?

De nos jours, presque personne ne programme ses propres algorithmes de tri; ils en utilisent un fourni par une bibliothèque. Par exemple, l' API Java 7 utilise en réalité le tri rapide à double pivot.

Les personnes qui programment leur propre algorithme de tri pour une raison quelconque auront tendance à s'en tenir à la simple variante à deux voies, car moins de risques d'erreurs sont 20% plus performants que la plupart du temps. Rappelez-vous: l’amélioration des performances la plus importante est de loin le moment où le code passe de "ne fonctionne pas" à "fonctionne".

Asymptotiquement parlant, cela n'a pas d'importance. Par exemple, la recherche binaire effectue approximativement des  comparaisons de log ₂ n et la recherche ternaire effectue approximativement des  comparaisons de ₃ n. Si vous connaissez vos logarithmes, vous savez que log _a  x = log _b  x / log _b  a, la recherche binaire ne fait donc qu'environ 1 / log ₃ 2 ≈ 1,5 fois plus de comparaisons que la recherche ternaire. C’est aussi la raison pour laquelle personne ne spécifie jamais la base du logarithme dans la notation Oh grande: c’est toujours un facteur constant qui s’éloigne du logarithme dans une base donnée, quelle que soit la valeur réelle de la base. Ainsi, diviser le problème en plusieurs sous-ensembles n'améliore pas la complexité temporelle et ne suffit pratiquement pas à compenser la logique plus complexe. En fait, cette complexité peut affecter négativement les performances pratiques, en augmentant la pression du cache ou en rendant les micro-optimisations moins réalisables.

D'autre part, certaines structures de données arborescentes utilisent un facteur de ramification élevé (beaucoup plus grand que 3, souvent 32 ou plus), bien que généralement pour d'autres raisons. Il améliore l'utilisation de la hiérarchie de la mémoire: les structures de données stockées dans la RAM optimisent l'utilisation du cache, les structures de données stockées sur le disque nécessitent moins de lectures HDD-> RAM.

Il existe des algorithmes de recherche / tri qui subdivisent non pas en deux mais en N.

Un exemple simple est la recherche par codage de hachage, qui prend O (1) fois.

Si la fonction de hachage préserve l'ordre, elle peut être utilisée pour créer un algorithme de tri O (N). (Vous pouvez considérer n'importe quel algorithme de tri comme une simple recherche de N où un nombre doit figurer dans le résultat.)

La question fondamentale est la suivante: lorsqu'un programme examine certaines données et entre ensuite les états suivants, combien y a-t-il d'états suivants et quelle est leur probabilité proche de l'égalité?

Lorsqu'un ordinateur compare deux nombres, disons, puis saute ou non, si les deux chemins sont également probables, le compteur de programme "connaît" un bit d'information supplémentaire sur chaque chemin, de sorte qu'en moyenne, il en a "appris" un. bit. Si un problème nécessite que M bits soient appris, alors en utilisant des décisions binaires, il ne peut pas obtenir la réponse en moins de M décisions. Ainsi, par exemple, rechercher un nombre dans un tableau trié de taille 1024 ne peut pas être effectué en moins de 10 décisions binaires, ne serait-ce que parce que moins aurait pas assez de résultats, mais cela peut certainement être fait en plus que cela.

Lorsqu'un ordinateur prend un nombre et le transforme en un index en tableau, il "apprend" jusqu'à enregistrer la base 2 du nombre d'éléments dans le tableau, et le fait en temps constant. Par exemple, s'il existe une table de saut de 1024 entrées, toutes plus ou moins vraisemblablement égales, le saut de cette table "apprend" 10 bits. C'est le truc fondamental derrière le codage de hachage. Un exemple de tri de ceci est comment vous pouvez trier un jeu de cartes. Ayez 52 cases, une pour chaque carte. Jetez chaque carte dans sa corbeille, puis ramassez-les toutes. Aucune subdivision requise.

Puisqu'il s'agit d'une question sur la division et la conquête générale, et pas seulement le tri, je suis surpris que personne n'ait évoqué le théorème principal.

En bref, la durée d'exécution des algorithmes de division et de conquête est déterminée par deux forces opposées: le gain que vous obtenez en transformant de plus gros problèmes en petits problèmes et le prix à payer pour résoudre davantage de problèmes. En fonction des détails de l'algorithme, il peut être avantageux ou non de scinder un problème en plus de deux morceaux. Si vous divisez le même nombre de sous-problèmes à chaque étape et que vous connaissez la complexité temporelle de la combinaison des résultats à chaque étape, le théorème principal vous indiquera la complexité temporelle de l'algorithme global.

L’ algorithme de multiplication de Karatsuba utilise une division et conquête à 3 voies pour obtenir une durée de fonctionnement de 0 (3 n ^ log_2 3) qui bat le 0 (n ^ 2) de l’algorithme de multiplication ordinaire (n est le nombre Nombres).

En raison de sa nature binaire, un ordinateur est très efficace pour diviser les choses en 2 et pas tellement en 3. Vous obtenez une division en 3 en divisant d'abord en 2, puis en divisant à nouveau l'une des parties en 2. Donc si vous devez diviser par 2 pour obtenir votre 3 division, vous pourriez aussi bien diviser en 2.