Qu'est-ce qu'un algorithme efficace?

Du point de vue du comportement asymptotique, qu'est-ce qui est considéré comme un algorithme "efficace"? Quelle est la norme / raison de tracer la ligne à ce point? Personnellement, je penserais que tout ce que je pourrais naïvement appeler "sous-polynôme", tel que tel que serait efficace et tout ce qui est serait "inefficace". Cependant, j'ai entendu tout ce qui est de n'importe quel ordre polynomial être appelé efficace. Quel est le raisonnement?n 1 + ϵ Ω ( n 2$f(n) = o(n^2)$$n^{1+\epsilon}$$\Omega(n^2)$

Cela dépend du contexte. En informatique théorique, chaque algorithme de temps polynomial est généralement considéré comme «efficace». Dans les algorithmes d'approximation par exemple, un temps d'exécution de serait considéré comme efficace, même s'il ne sera pas utilisable en pratique pour une valeur raisonnable de ϵ . Un algorithme pour SAT qui s'exécute en n 2 100 serait une percée étonnante.$n^{1/\epsilon^{1/\epsilon}}$$\epsilon$$n^{2^{100}}$

En algorithmique classique, c'est-à-dire les algorithmes des années 80 et avant, les temps d'exécution inférieurs à environ (pensez à la multiplication matricielle, à l'appariement des coûts min, aux flux, à la programmation linéaire) sont considérés comme efficaces. Ils sont toujours considérés comme efficaces par la plupart des gens, je dirais. Bien entendu, un algorithme n 2 n'est pas considéré comme efficace si un algorithme n log n est connu, comme pour le tri par exemple.$n^3$$n^2$$n\log n$

De nos jours, il existe une tendance vers des algorithmes sublinéaires ou des algorithmes de streaming capables de traiter des téraoctets de données. Essayez d'utiliser la multiplication matricielle pour calculer le classement des pages de toutes les pages de l'index de Google. Ça ne marchera pas.

Bien sûr, bien que certainement utile, le temps d'exécution asymptotique d'un algorithme ne raconte pas toute l'histoire. Il existe des algorithmes qui ont un bon temps d'exécution asymptotique, mais des constantes si énormes qu'elles ne peuvent effectivement pas être utilisées. Déjà. Lipton les appelle des algorithmes galactiques . Robert Sedgewick déclare même que les limites du pire des cas sont "souvent inutiles pour la prédiction, souvent inutiles pour les garanties" et "l'analyse du pire des cas est inutile pour prédire les performances" dans son discours Remettre la science en informatique .

Mes 2 cents sous l'angle des algorithmes distribués: Lorsque l'on regarde les réseaux à grande échelle (P2P, réseaux sociaux, etc.), un algorithme distribué est considéré comme efficace si son temps de fonctionnement est pour une constante c > 0 et l'algorithme utilise des messages de O ( log n ) bits. Il est à noter que l'exigence relative aux tailles de message est généralement donnée encore plus d'importance que le temps d'exécution, en particulier pour les problèmes "globaux" qui ont une limite inférieure plus grande sur le temps d'exécution, par exemple MST distribué.$O(\log^c n)$$c>0$ $O(\log n)$

Le raisonnement derrière est que, du point de vue du comportement asymptotique, un taux de croissance polynomial est trivialement inférieur à un taux de croissance super-polynomial. En pratique, un algorithme temporel polynomial s'exécute beaucoup plus rapidement qu'un algorithme temporel superpolynomial lorsque la taille d'entrée augmente.

$O(n^{2000})$$O(n^5)$

$O(n^2)$

En théorie, un algorithme est dit efficace si son pire temps d'exécution est limité par un polynôme dans sa longueur d'entrée. Le raisonnement étant que les polynômes ont de belles propriétés de fermeture. L'ajout, la multiplication et la composition de polynômes sont des opérations qui produisent des polynômes et elles sont bonnes si vous réduisez les problèmes les uns aux autres.

Bien sûr, l'écart entre le polynôme et l'exponentielle devient très grand à mesure que la longueur d'entrée augmente, de sorte que les algorithmes polynomiaux sont bien meilleurs. En pratique, un algorithme à temps polynomial peut prendre beaucoup de temps avant la fin, mais il se peut que ce soit un algorithme optimal (le meilleur possible), auquel cas je dirais qu'il est efficace.

$n^3$$n^2$