Tout comme le titre, et BTW, c'est juste par curiosité et ce n'est pas une question de devoirs. Cela peut sembler anodin pour les personnes de CS majeur. Le problème est que je voudrais trouver les indices de valeur maximale dans un tableau. Fondamentalement, j'ai deux approches.
scannez et trouvez le maximum, puis scannez deux fois pour obtenir le vecteur d'indices
scannez et trouvez le maximum, le long de ce tableau d'index de construction de scan et abandonnez s'il y en a un meilleur.
Puis-je maintenant comment évaluer ces deux approches en termes de performances (principalement la complexité temporelle je suppose)? C'est dur pour moi car je n'ai même aucune idée de ce que devrait être le pire des cas pour la seconde approche! Ce n'est pas un problème difficile perse. Mais je veux juste savoir comment aborder ce problème ou comment dois-je rechercher ce type de problème sur Google pour obtenir la réponse.
3 Réponses :
Pour votre première méthode, vous pouvez définir une condition pour ajouter l'index au tableau. Chaque fois que le maximum change, vous devez effacer le tableau. Vous n'avez pas besoin de répéter deux fois.
Pour la deuxième méthode, la mise en œuvre est plus simple. Vous trouvez juste max la première fois. Ensuite, vous trouvez les indices qui correspondent à la deuxième fois.
En terme de complexité:
scannez et trouvez le maximum,
puis scannez deux fois pour obtenir le vecteur des indices
Le premier scan est O (n) .
Le deuxième scan est O (n) + k insertions (avec k, le nombre de valeur max)
vector :: push_back a une complexité amortie de O (1) .
donc un total O (2 * n + k) qui pourrait être simplifié en O (n) comme k <= n
scannez et trouvez le maximum,
le long de ce scan, construisez un tableau d'indices et abandonnez-le s'il y en a un meilleur.
Le scan est O (n) .
Le nombre d'insertions est plus compliqué à calculer.
Le nombre de clear (et le nombre d'éléments effacés) est également plus compliqué à calculer. (La complexité de clear serait inférieure ou égale au nombre d'éléments supprimés)
Mais les deux ont une limite supérieure à n , donc la complexité est inférieure ou égale à O (3 * n) = O (n) mais également supérieure à égale à < code> O (n) (Scan) donc c'est aussi O (n) .
Donc, pour les deux méthodes, la complexité est la même: O (n) .
Pour le timing des performances, comme toujours, vous devez mesurer.
et si je n'utilise pas clear , je viens d'en initialiser un nouveau? Cela fait-il la borne supérieure 2 * n?
@Lihaonan: O (n) == O (2 * n) donc ça va. Tant que O (a * MyClear (b)) <= O (a * b) tout va bien.
Comme indiqué dans une réponse précédente, la complexité est O (n) dans les deux cas, et des mesures sont nécessaires pour comparer les performances.
Cependant, je voudrais ajouter deux points:
La première est que la comparaison des performances peut dépendre du compilateur, de la manière dont l'optimisation est effectuée.
Le deuxième point est plus critique: les performances peuvent dépendre du tableau d'entrée.
Par exemple, considérons le cas du coin: 1,1,1, .., 1, 2 , c'est-à-dire un grand nombre de 1 suivi d'un < code> 2 . Avec votre deuxième approche, vous allez créer un énorme tableau temporaire d'indices, pour fournir à la fin un tableau d'un élément. Il est possible à la fin de redéfinir la taille de la mémoire allouée à ce tableau. Cependant, je n'aime pas l'idée de créer un énorme vecteur temporaire inutile, indépendamment du souci de performance temporelle. Notez qu'un tel tableau pourrait souffrir de plusieurs réallocations, ce qui aurait un impact sur les performances de temps.
C'est pourquoi dans le cas général, sans aucune connaissance sur l'entrée, je préférerais votre première approche, deux scans. La situation peut être différente si vous souhaitez implémenter une fonction dédiée à un type de données spécifique.
Faire deux ou trois opérations dans une boucle, ou faire deux ou trois boucles en effectuant une opération chacune a la même complexité de temps.