Lors du calcul de la dépendance d'exécution à l'entrée, quels calculs sont pris en compte? Par exemple, je pense avoir appris que l'indexation des tableaux ainsi que les instructions d'affectation ne sont pas comptées, pourquoi?
8
Lors du calcul de la dépendance d'exécution à l'entrée, quels calculs sont pris en compte? Par exemple, je pense avoir appris que l'indexation des tableaux ainsi que les instructions d'affectation ne sont pas comptées, pourquoi?
Lors des calculs de complexité, nous utilisons généralement le modèle RAM . Dans ce modèle, nous supposons que l'indexation de tableau est O (1). L'instruction d'affectation revient à attribuer une valeur à un tableau de variables ins variable . C'est juste pour plus de commodité. Il simplifie l'analyse de l'algorithme. Dans le monde réel, l'indexation des tableaux prend O (log I) où I est le nombre de choses indexées.
Nous considérons généralement les choses qui dépendent de la taille de l'entrée, par exemple les boucles. Même s'il y a une opération O (1) dans la boucle et qu'elle est exécutée n fois, l'algorithme s'exécute pendant la durée O (n).
Mais le fonctionnement O (1) en dehors de la boucle ne prend qu'un temps constant et O (n) + O (1) = O (n).
Lisez à propos de l'algorithme de tri radix de CLRS.
L'objectif ultime est le "temps d'exécution en secondes" ou plus généralement (sans tenir compte des fonctionnalités modernes du CPU) "le nombre de cycles d'horloge". En fin de compte, c'est difficile à analyser, et c'est aussi spécifique à la machine ou au moins au jeu d'instructions. Par conséquent, cela n'est généralement pas fait.
Le niveau d'abstraction suivant consiste à compter précisément toutes les opérations (d'un pseudo-code de type assembleur), en conservant les coûts d'opération individuels (en cycles d'horloge) comme paramètres. Notez qu'une telle analyse se trouve entre autres dans "The Art of Computer Programming" de Knuth, donc il y a certainement une place pour ce type d'approche, même si elle est difficile et tend à être plus difficile en présence d'une hiérarchie de mémoire.
Enfin et surtout - et certainement la plus importante - l'analyse des opérations dominantes ignorant les facteurs constants et les constrictions disparaissant asymptotiquement ("O -analysis "). Le raisonnement est que le runtime doit se comporter asymptotiquement comme le nombre d'opérations les plus fréquemment exécutées, parfois un certain facteur en fonction de l'implémentation réelle et de la machine. Ce type d'analyse donne des résultats généraux qui s'appliquent à toutes les machines (couvertes par modèle RAM) et est plus facile à réaliser que ci-dessus, mais peut manquer de spécificité.
Laissant de côté les cadres «classiques», de nombreux algorithmes sont dominés par le coût de la mémoire et / ou de la communication, donc dans ce cas, le nombre et le volume des accès mémoire resp. les transmissions réseau sont raisonnables (et peut-être suffisantes).
En outre, gardez à l'esprit que nous ne sommes souvent pas très intéressés par les performances absolues d'un algorithme mais par leur comparaison avec d'autres. Cela peut également éclairer le choix du paramètre analysé.
Donc, vous voyez, il n'y a pas de réponse définitive. Selon les objectifs de l'analyse en question, différentes réponses peuvent être apportées.
Voir aussi ma réponse ici pour quelques réflexions, et la réponse de Sebastian sur Quicksort pour un exemple.
la source