Que signifie un algorithme plus rapide en informatique théorique?

S'il existe un algorithme fonctionnant dans le temps $O(f(n))$ pour un problème A, et que quelqu'un propose un algorithme fonctionnant dans le temps, $O(f(n)/g(n))$ , où $g(n) = o(f(n))$ , est-il considéré comme une amélioration par rapport à l'algorithme précédent?

Est-il sensé, dans le contexte de l'informatique théorique, de proposer un tel algorithme?

Non, un algorithme fonctionnant dans le temps $O(f(n)/g(n))$ , où $g(n) = o(f(n))$ , n'est pas nécessairement considéré comme une amélioration. Par exemple, supposons que $f(n) = n$ et $g(n) = 1/n$ . Alors $O(f(n)/g(n)) = O(n^2)$ est une limite de temps pire que$O(f(n)) = O(n)$ .

Afin d'améliorer un algorithme fonctionnant au temps , vous devez trouver un algorithme fonctionnant au temps o ( f ( n ) ) , c'est-à-dire au temps g ( n ) pour une fonction g ( n ) = o ( f ( n ) ) .$f(n)$$o(f(n))$$g(n)$$g(n) = o(f(n))$

Si tout ce que vous savez, c'est qu'un algorithme s'exécute dans le temps , il n'est pas clair si un algorithme fonctionnant dans le temps O ( g ( n ) ) est une amélioration, quel que soit f ( n ) , g ( n ) le sont. C'est parce que le grand O n'est qu'une limite supérieure sur le temps d'exécution. Au lieu de cela, il est courant de considérer la complexité temporelle dans le pire cas, et d'estimer comme un grand Θ plutôt que comme un grand O .$O(f(n))$$O(g(n))$$f(n),g(n)$$\Theta$$O$

Rappelez - vous que La notation est destiné à analyser la façon dont la tâche se développe pour les différentes tailles d'entrée, et en particulier sur les feuilles des facteurs multiplicatifs, terme d'ordre inférieur, et des constantes.$O(...)$

Supposons que vous ayez un algorithme dont le temps d'exécution réel est de 1 n 2 + 2 n + 1 (en supposant que vous pouvez réellement compter les instructions et connaître les horaires exacts, etc., ce qui est certes une hypothèse énorme dans les systèmes modernes). Supposons ensuite que vous proposiez un nouvel algorithme qui se trouve être O ( n ) , mais le temps d'exécution réel est de 1000 n + 5000 . Supposons également que vous savez que le logiciel qui utilise cet algorithme ne verra jamais un problème de taille n > 10 .$O(n^2)$$1n^2+2n+1$$O(n)$$1000n + 5000$$n>10$

Alors, lequel choisiriez-vous - l' algorithme qui va prendre 15 000 unités de temps, ou celui O ( n 2 ) qui ne prendra que 121 unités? Maintenant, si votre logiciel évolue pour gérer des problèmes de taille n > 100000 , lequel choisiriez-vous? Que feriez-vous si la taille de votre problème varie considérablement?$O(n)$$O(n^2)$$n>100000$

Généralement, cela signifie que, pour toute taille d'entrée suffisamment grande, le temps d'exécution le plus défavorable de l'ancien algorithme est plus lent que le nouveau. Cela équivaut au formalisme , où g est la complexité temporelle du nouvel algorithme et f la complexité temporelle de l'ancien.$g(n) \in o\bigl(f\left(n\right)\bigr)$$g$$f$

Parfois, cependant, les informaticiens se soucient des performances moyennes des cas. L'exemple classique est Quicksort: son pire cas d'exécution est alors que nous en connaissons d'autres qui s'exécutent en temps Θ ( n log n ) , mais il est largement utilisé dans la pratique en raison de son bon temps d'exécution moyen. Il peut en outre être modifié pour fonctionner très rapidement dans les cas les plus fréquents dans la nature, tels que les tableaux qui sont pour la plupart dans le bon ordre.$\Theta(n^2)$$\Theta(n \log n)$

Et parfois, même les informaticiens théoriques utilisent «plus vite» de la même manière que les gens normaux. Par exemple, la plupart des implémentations des classes String ont une optimisation de chaîne courte (également appelée optimisation de petite chaîne), même si cela accélère les choses uniquement pour les chaînes courtes et est une surcharge pure pour les longues. Comme la taille d'entrée devient de plus en plus grande, le temps d'exécution d'une opération String avec SSO va être plus long d'un petit terme constant, donc selon la définition que j'ai donnée dans le premier paragraphe, supprimer SSO d'une classe String le rend «plus rapide ». En pratique, cependant, la plupart des chaînes sont petites, donc SSO accélère la plupart des programmes qui les utilisent, et la plupart des professeurs d'informatique savent mieux que d'aller en exigeant que les gens ne parlent que d'ordres de complexité temporelle asymptotique .

Il n'y a pas une définition unifiée de ce qu'est un «algorithme plus rapide». Il n'y a pas d'organe directeur qui décide si un algorithme est plus rapide qu'un autre.

Pour expliquer pourquoi, je voudrais proposer deux scénarios différents qui illustrent ce concept trouble.

Le premier exemple est un algorithme qui recherche une liste chaînée de données non ordonnées. Si je peux faire la même opération avec un tableau, je n'ai aucun changement sur la grande mesure Oh de performance. Les deux recherches sont O (n). Si je regarde simplement les grandes valeurs Oh, je pourrais dire que je n'ai fait aucune amélioration. Cependant, il est connu que les recherches de tableaux sont plus rapides que de parcourir une liste chaînée dans la majorité des cas, donc on peut décider que cela a rendu un algorithme "plus rapide", même si le grand Oh n'a pas changé.

Si je peux utiliser l'exemple traditionnel de programmation d'un robot pour faire un sandwich PBJ, je peux montrer ce que je veux dire d'une autre manière. Considérez juste le point où l'on ouvre le pot de beurre d'arachide.

Pick up the jar
Grab the lid
Unscrew the lid

Contre

Pick up the jar
Put the jar back down
Pick up the jar
Put the jar back down
Pick up the jar
Put the jar back down
Pick up the jar
Put the jar back down
Pick up the jar
Put the jar back down
Pick up the jar
Grab the lid
Unscrew the lid

Même dans le cadre théorique le plus académique auquel je puisse penser, vous constaterez que les gens acceptent que le premier algorithme soit plus rapide que le second, même si les résultats de la grande notation Oh sont les mêmes.

En revanche, nous pouvons considérer un algorithme pour briser le cryptage RSA. Pour l'instant, on perçoit que ce processus est probablement O (2 ^ n), où n est le nombre de bits. Considérons un nouvel algorithme qui s'exécute n ^ 100 plus rapidement. Cela signifie que mon nouveau processus s'exécute en O (2 ^ n / n ^ 100). Cependant, dans le monde de la cryptographie, une accélération polynomiale vers un algorithme exponentiel n'est traditionnellement pas considérée comme une accélération théorique. Lors de la réalisation de preuves de sécurité, il est supposé qu'un attaquant peut découvrir l'une de ces accélérations et que cela n'aura aucun effet.

Donc, dans une circonstance, nous pouvons changer un O (n) en O (n) et l'appeler plus rapidement. Dans une circonstance différente, nous pouvons changer un O (2 ^ n) en O (2 ^ n / n ^ 100), et affirmer qu'il n'y a eu aucune accélération significative du tout. C'est pourquoi je dis qu'il n'y a pas de définition unifiée pour un «algorithme plus rapide». Elle est toujours contextuellement dépendante.

$A(n) \in O(f(n))$

$$\exists \ 0 \le c_f \lt \infty \mid \ \limsup_{n \to \infty} \frac{A(n)}{f(n)} = c_f$$

$g(n)$$\limsup_{n\to\infty} g(n) = \infty$$h(n) = \frac{f(n)}{g(n)}$

$A'(n)$$O(h(n))$$A(n)$$O(h(n))$

$$\exists \ 0 \le c_h \lt \infty \mid \ \limsup_{n \to \infty} \frac{A(n)}{h(n)} = c_h$$

En utilisant les règles de limites, nous pouvons également écrire:

$$c_h = \limsup_{n \to \infty} \frac{A(n)}{h(n)} = \limsup_{n \to \infty} \frac{A(n)g(n)}{f(n)} = c_f \cdot \limsup_{n \to \infty} g(n)$$

$c_h \lt \infty$$c_f = 0$

$c_f \neq 0$$A(n) \notin O(h(n))$

$A'(n)$$A(n)$$A(n) \in \Theta(f(n))$$g(n)$

$A(n) \in O(f(n))$$A'(n)$$A(n)$$O(h(n))$