complexité d'aller du début à la fin et à travers un vecteur

Question

J'essaie de me familiariser avec l'évaluation de la complexité des algorithmes. En général, je pense que c'est une bonne pratique/élégante, mais dans le spécifique j'ai besoin d'exprimer la complexité du temps de mon code C++.

J'ai un petit doute. Supposons que j'ai un algorithme qui lit juste les données depuis le début d'un std::vector jusqu'à la fin; alors il fait la même chose de la fin au début (il en est de même pour 2 cycles pour les index "De 0 à N" suivi de "De N à 0"). Je me suis dit que la complexité pour ce genre de choses est O (2N): est-ce correct?

Une fois que j'ai atteint le début, supposons que je veux recommencer à lire toutes les données du début à la fin (passant au total 3 fois le vecteur): est la complexité O (3N)? C'est peut-être un doute stupide, mais j'aimerais quand même avoir une opinion sur mon processus de réflexion.

Answer 1

notation Big-O signifie simplement:

f (n) = O (g (n)) si et seulement si f (n)/g (n) ne pousse pas à l'infini comme n augmente

Ce que vous devez faire est de compter le nombre d'opérations que vous réalisez, ce qui est f (n), puis trouver une fonction g (n) qui augmente au moins aussi vite que f.

Dans votre exemple d'aller dans un sens puis retour, le nombre d'opérations est f (n) = 2n parce que chaque élément est lu deux fois, donc, vous pouvez choisir g (n) = n. Puisque f (n)/g (n) = 2n/n = 2 ne croît évidemment pas à l'infini (c'est une constante), vous avez un O (n) algorithme.

Il est aussi un O (2n) algorithme, bien sûr: depuis la "croissance à l'infini" propriété ne change pas lorsque vous multipliez g (n) par une constante, une O (g (n) est également par définition un algorithme O (Cg (n)) pour toute constante C.

Et il est aussi un O (n²) algorithme, car 2n/n² = 2/n décroît vers zéro. La notation Big-O ne fournit qu'une limite supérieure de la complexité.

Answer 2

O (N), O (2N) et O (3N) sont équivalents. Multiplier un facteur constant à la fonction à l'intérieur du 0() won't change its complexity comme "linéaire".

Il est vrai cependant que chaque balayage se produira N lit dans les deux directions, à savoir son rendement 2N ∈ O (N) lit lors de la numérisation, du début à la fin au début, et 3N ∈ O (N) lit lorsque numérisation du début à la fin pour commencer à la fin.

Answer 3

Il est important d'avoir une idée pratique de la notation Big-O. Je vais essayer de le dire ...

Comme vous le dites, votre algorithme est intuitivement "O (2N)", mais imaginez quelqu'un d'autre écrit un algorithme qui ne répète qu'une fois (donc clairement O (N)) mais dépense deux fois plus de temps pour traiter chaque noeud, ou cent fois plus longtemps. Vous pouvez voir que O (2N) n'est que faiblement suggestif de quelque chose de plus lent qu'un algorithme O (N): ne sachant pas quelles sont les opérations, O (N) pourrait être seulement plus rapide, disons 50,1% du temps. Big-O n'a de sens que si N devient énorme: si vos opérations ont une longueur de 1000: 1, alors la différence entre un algorithme O (N) et O (NlogN) devient seulement dominante quand N dépasse 1000 carrés (c'est-à-dire 1000000). Ainsi, la notation Big-O est utilisée pour raisonner sur le coût des opérations sur de grands ensembles, dans lesquels des facteurs linéaires comme 2x ou 10x ne sont tout simplement pas considérés comme pertinents, et ils sont ignorés.