Complexité de STL max_element

Question

Donc selon le lien ici: http://www.cplusplus.com/reference/algorithm/max_element/, la fonction max_element est O (n), apparemment pour tous les conteneurs STL. Est-ce correct? Ne devrait-il pas être O (log n) pour un ensemble (implémenté comme un arbre binaire)? Sur une note quelque peu liée, j'ai toujours utilisé cplusplus.com pour des questions qui sont plus faciles à répondre, mais je serais curieux de savoir ce que les autres pensent du site.

Answer 1

C'est linéaire car il touche tous les éléments.

Il est inutile de même l'utiliser sur un ensemble ou un autre conteneur commandé en utilisant le même comparateur car vous pouvez simplement utiliser .rbegin() en temps constant.

Si vous n'utilisez pas la même fonction de comparaison, il n'y a aucune garantie que les ordres coïncideront, donc, encore une fois, il doit toucher chaque élément et doit être au moins linéaire.

Bien que les algorithmes puissent être spécialisés pour différentes catégories d'itérateurs, il n'existe aucun moyen de les spécialiser en fonction de l'ordre de la plage d'itération.

La plupart des algorithmes destinés à des plages non ordonnées (max_element inclus), quelques-unes ont besoin les plages à commander (par exemple set_union, set_intersection) certains exigent d'autres propriétés de la gamme (par exemple push_heap, pop_heap).

Answer 2

Il s'agit d'un algorithme STL, donc il ne sait rien sur le conteneur. Donc, cette recherche linéaire est la meilleure qu'elle peut faire sur un couple sur les itérateurs en avant.

Answer 3

La fonction max_element est O (n) pour tous les conteneurs STL.

Ceci est incorrect car max_element s'applique aux itérateurs, pas aux conteneurs. Si vous lui donnez des itérateurs à partir d'un ensemble, il n'a aucun moyen de savoir qu'ils proviennent d'un ensemble et les traversera donc tous afin de rechercher le maximum. Ainsi, la phrase correcte est:

La fonction max_element est O (n) pour tous les itérateurs avant

D'ailleurs, si vous savez que vous manipulez un ensemble, vous avez déjà accès à des méthodes vous donne l'élément max plus rapidement que O (n), alors pourquoi utiliser max_element?

Answer 4

Les algorithmes STL ne savent pas de quel conteneur vous avez pris les itérateurs, qu'ils aient été commandés ou non et quelles contraintes d'ordre ont été utilisées. C'est un algorithme linéaire qui vérifie tous les éléments de la gamme tout en gardant la trace de la valeur maximale vue jusqu'ici.

Notez que même si vous pouvez utiliser des techniques de métaprogrammation pour détecter quel type de conteneur dans lequel les itérateurs obtenus à partir qui ne sont pas une garantie que vous pouvez simplement passer au dernier élément pour obtenir le maximum:

int values[] = { 1, 2, 3, 4, 5 }; 
std::set<int, greater<int> > the_set(values, values+5); 
std::max_element(the_set.begin(), the_set.end()); //?? 

Même si les itérateurs viennent d'un ensemble, ce n'est pas le dernier, mais le premier élément celui qui détient le maximum. Avec des types de données plus complexes, l'ensemble peut être commandé avec une autre clé qui peut ne pas être liée aux valeurs min/max.