Je ne comprends pas comment compter les opérations primitives dans un algorithme.Comptage des opérations primitives?
La ligne est barrée d'une croix dans « 2 pour l'écriture, 4 lectures, 3 opérateurs »
Je veux dire, la diapositive essaie de l'expliquer, mais je ne comprends toujours pas ici comment il obtient 9n à la fin de celui-ci. Est-ce possible si vous pouvez m'expliquer cela d'une manière idiote s'il vous plait?
9 est expliqué que 4 lectures (i, a[i], x, y), 3 opérateurs (+, + et +) ... mais 2 ne font pas écrit de sens.
Si je devais compter à ce niveau de granularité, il serait cinq lectures (i deux fois - une fois pour trouver a[i] à gauche pour écrire, une fois pour trouver a[i] sur le côté droit de lire) et une écriture (juste mentionné a[i]). Je voudrais également ajouter deux opérations d'indexation (qui sont essentiellement des opérations d'addition glorifiées) pour les deux [i].
Ensuite, il y a la boucle, qui est i = 1; while(i <= n) .... i = i + 1; end while, donc une affectation avant la boucle, une comparaison et une lecture en haut de la boucle et une affectation, une lecture et une addition à la fin de la boucle (éventuellement un supplémentaire pour charger la constante, mais la diapositive originale les a ignorés, ce qui est un choix valide, je suppose).
Et "n pour créer le tableau" ... Je ne crois pas que cela fonctionne comme ça. L'annulation d'un tableau correspond à la longueur du tableau; mais juste l'allocation n'a pas réellement accès à la mémoire allouée. Qu'un tableau à un octet soit beaucoup plus rapide à zéro (ou initialiser) qu'un million d'octets est un fait, mais le premier est alloué aussi rapidement que le dernier, tant qu'il y a de la mémoire disponible pour le faire (et tant qu'aucune tâche de conciergerie ne doit être effectuée pour le faire). 2*n sonne comme un non-sens ici.
Cependant, rien de tout cela n'est réellement utile. Si vous mesurez la complexité d'un algorithme, vous ne le faites jamais de cette manière - une opération est de la même complexité que sept ou un million. La chose qui compte est de savoir comment le nombre d'opérations augmente quand un paramètre externe (normalement, la taille des données, généralement symbolisée par n) change. Cet extrait est de complexité O(n), parce que la complexité se développe à la même vitesse que le n se développe. Si vous avez imbriqué deux boucles, il est noté O(n^2), ce qui signifie que le taux d'échelles de complexité est quadratique: l'algorithme s'exécute quatre fois plus longtemps ou prend quatre fois la mémoire si les données ne font que doubler. Que le contenu de la boucle prenne une opération ou un million, ou qu'ils prennent une milliseconde ou une heure, n'a aucun impact sur la complexité algorithmique. Le seulement chose importante dans la diapositive pour calculer la complexité du temps est la boucle.
Eh bien, en quelque sorte. Selon ce que sont les données manipulées, l'intérieur pourrait avoir un impact sur la complexité algorithmique de l'ensemble. Par exemple, la multiplication n'est pas réellement une seule opération; il a sa propre complexité. Mais il est généralement trivial et ignorable, car nous opérons normalement sur des nombres à précision fixe; ce qui fait de la multiplication une complexité prévisible et fixe. Si vous pouvez avoir des nombres de précision arbitraires, une paire de nombres à deux chiffres prend beaucoup moins à multiplier qu'une paire de nombres à 1000 chiffres, et si vous les avez, vous devez en tenir compte. Et évidemment, si vous appelez une fonction à l'intérieur de votre boucle qui contient une boucle, cela a certainement un impact sur la complexité.
Un autre problème ici est que la définition d'une opération primitive est arbitraire. Je l'ai déjà fait allusion: charger une constante peut être considéré comme une opération primitive, mais ce n'est pas le cas ici. Si c'est le cas, x = 1 serait également deux opérations, pas un comme les diaporamas. En effet, dans l'assemblage 8086, vous devez écrire mov ax, 1; mov offset x, ax (charger un 1 dans un registre, stocker un registre en mémoire) (j'ai peut-être raté la syntaxe, ça fait longtemps). Cependant, x = x + 1, une fois optimisé, n'est qu'une instruction dans de nombreux microprocesseurs. Mais si vous essayez d'optimiser un morceau de code critique dans l'assemblage ou les microinstructions, vous ne pouvez pas regrouper toutes les opérations ensemble. Chaque opération prend une longueur spécifique, et généralement la multiplication prendra plus que l'addition. Chaque cycle compte. Heureusement, la plupart d'entre nous n'ont jamais besoin de travailler à un niveau aussi bas. TL: DR: Personne ne compte les opérations en pseudo-code.