Le matériel / l'implémentation affecteront-ils la complexité spatio-temporelle des algorithmes?

Je ne suis même pas un étudiant CS, donc cela pourrait être une question stupide, mais veuillez me supporter ...

À l'ère pré-informatique, nous ne pouvons implémenter une structure de données de tableau qu'avec quelque chose comme un tableau de tiroirs. Puisqu'il faut localiser le tiroir avec l'index correspondant avant d'en extraire la valeur, la complexité temporelle de la recherche de tableau est , en supposant une recherche binaire.$O(log(n))$

Cependant, l'invention des ordinateurs a fait une grande différence. Les ordinateurs modernes peuvent lire à partir de leur RAM si rapidement que nous considérons maintenant la complexité temporelle de la recherche de tableau comme étant (même si ce n'est techniquement pas le cas, car cela prend plus de temps pour déplacer le registre sur une plus grande distance, etc.)$O(1)$

Un autre exemple est celui des dictionnaires Python. Bien que l'on puisse obtenir une complexité d'accès au dictionnaire de avec une méthode magique surchargée mal écrite (ou ridiculement malchance, c'est-à-dire des clés ayant beaucoup de collisions de hachage), il est généralement présumé être . Dans ce cas, la complexité temporelle dépend à la fois de l'implémentation de table de hachage des dictionnaires Python et de l'implémentation des clés des fonctions de hachage.O ( 1 $O(n)$__hash__$O(1)$

Est-ce à dire que le matériel / l'implémentation peuvent affecter la complexité temporelle des algorithmes? (Bien que les deux exemples concernent des structures de données au lieu d'algorithmes, ces derniers sont construits sur les premiers, et je n'ai jamais entendu parler de la complexité temporelle des structures de données, donc j'utilise ici le terme "algorithmes")

Pour moi, les algorithmes sont abstraits et conceptuels, dont les propriétés comme la complexité temps / espace ne devraient pas être affectées par leur mise en œuvre d'une manière spécifique, mais le sont-elles?

Sûr. Certainement. Voici comment concilier votre inconfort.

Lorsque nous analysons le temps d'exécution des algorithmes, nous le faisons par rapport à un modèle particulier de calcul . Le modèle de calcul spécifie des choses comme le temps qu'il faut pour effectuer chaque opération de base (est-ce un temps de recherche de tableau ou O ( 1 ) ?). Le temps d'exécution de l'algorithme peut dépendre du modèle de calcul.$O(\log n)$$O(1)$

Une fois que vous avez choisi un modèle de calcul, l'analyse de l'algorithme est un exercice mathématique purement abstrait, conceptuel qui ne dépend plus du matériel.

Cependant, dans la pratique, nous voulons généralement choisir un modèle de calcul qui reflète la réalité de notre matériel - au moins dans une mesure raisonnable. Donc, si le matériel change, nous pourrions décider d'analyser nos algorithmes sous un modèle de calcul différent qui est plus approprié au nouveau matériel. C'est ainsi que le matériel peut affecter la durée de fonctionnement.

La raison pour laquelle cela n'est pas évident est que, dans les classes d'introduction, nous ne parlons souvent pas du modèle de calcul. Nous faisons simplement implicitement certaines hypothèses, sans jamais les rendre explicites. C'est raisonnable, à des fins pédagogiques, mais cela a un coût - cela cache cet aspect de l'analyse. Maintenant tu sais.

Je pense qu'il y a un malentendu fondamental dans la question. Vous comparez une personne trouvant un objet dans une liste triée (par exemple, une page spécifique dans un livre, compte tenu de son numéro) avec un ordinateur recherchant un élément d'un tableau.

$O(\log n)$$O(1)$

Donc, oui, le matériel (c'est-à-dire le modèle de calcul) affecte le temps d'exécution des algorithmes, comme l' explique DW , mais ce n'est pas ce sur quoi votre exemple d'accès au tableau semble se baser.

Non, le matériel n'affecte pas la complexité des algorithmes.

Mais , cela affecte le choix de l'algorithme, et il peut affecter l'utilité de l'analyse de complexité à un point où l'analyse devient à peu près vide de sens (ou simplement d'intérêt académique).

Trouver le bon tiroir (comme accéder à un élément de tableau) utilise l'algorithme "ouvrir le Nème élément directement par index", pas l'algorithme "rechercher linéairement" ou "faire une recherche binaire". Les algorithmes ne sont pas modifiés, mais le choix.

D'un autre côté, l'analyse de la complexité elle-même, ou plutôt sa signification, est grandement affectée par le matériel.

De nombreux algorithmes qui sont stellaires par leur analyse de complexité sont peu performants voire inutiles en pratique car le facteur constant insignifiant n'est pas du tout insignifiant, mais dominant .

Ou, parce que des hypothèses qui étaient autrefois vraies (ou pour la plupart vraies) ne sont plus valables. Tels que, par exemple, chaque opération est essentiellement la même (seulement de petites différences constantes qui n'ont pas d'importance), ou cela ne fait aucune différence sur les emplacements de mémoire auxquels vous accédez dans quel ordre. Par l'analyse de la complexité, vous pouvez conclure que certains algorithmes sont largement supérieurs car ils n'ont besoin que de tant d'opérations. Dans la pratique, vous pouvez constater que chaque opération provoque un échec de cache garanti (ou pire encore, un défaut de page), ce qui introduit un k si énorme qu'il n'est plus insignifiant, mais qu'il domine tout.
Si l'algorithme A prend 500 opérations pour traiter un ensemble de données d'une taille donnée et que l'algorithme B n'en prend que 5, mais que B provoque 5 défauts qui brûlent vingt millions de cycles chacun, alors malgré ce que l'analyse ou le bon sens peuvent vous dire, A est mieux.

Cela a conduit à de drôles de surprises comme par exemple dans Cuckoo Hashing il y a quelques années. Ce qui était largement supérieur parce que [longue liste d'avantages]. Une fois le battage médiatique refroidi, il s'est avéré qu'il était largement inférieur car il garantissait deux échecs de cache (défauts, pour des ensembles de données plus volumineux) à chaque accès.

Il en est de même pour l'identification et le traitement de sous-ensembles de données. Souvent, la solution correcte de nos jours est: "faites tout" , c'est-à-dire qu'au lieu de déterminer ce dont vous avez besoin pour procéder et faire cela, traitez le jeu de données complet de manière linéaire même si vous n'en avez peut-être besoin que de la moitié. Parce que, croyez-le ou non, c'est plus rapide en raison d'aucune erreur de prédiction de branche, d'aucun échec de cache, d'aucun défaut de page.
Besoin de lire les 8 premiers Ko et les 3 derniers Ko d'un fichier de 3 Mo? Eh bien, lisez le fichier complet et jetez ce que vous ne voulez pas, car la recherche entre les deux sera dix fois plus lente que la simple lecture du tout.

Utiliser une carte car elle a une complexité logarithmique? Ou une table de hachage, qui a un temps d'accès constant? Constant semble génial. Eh bien, pour tout ce qui contient moins d'un millier de choses (selon le matériel, la taille des données et le modèle d'accès), une recherche linéaire peut être tout aussi bonne ou meilleure. Surprise.

Ce ne sont donc pas les algorithmes en soi qui sont affectés, mais leur utilité et leur choix.