Quelle est la complexité temporelle de std:: sort () dans la bibliothèque standard C++?
6 réponses
std::sort doit avoir moyen de cas linearithmic (n log n) le temps de la complexité. Tout algorithme peut être utilisé dans la mesure où cette exigence de complexité temporelle est respectée. Il n'est pas le cas le pire moment de la complexité exigence.
si vous voulez une fonction garantie de complexité de temps du pire cas, utilisez std::stable_sort , qui a la complexité de temps du pire cas quasilinéaire (n log^2 n).
la complexité est O(n log n) . Certaines implémentations courantes utilisent introsort pour autant que je sache:
http://en.wikipedia.org/wiki/Sort_ (C%2B%2B)
l'algorithme de tri spécifique n'est pas obligatoire et peut varier d'une implémentation à l'autre. La bibliothèque GNU Standard C++, par exemple, utilise un algorithme de tri hybride: introsort est effectué en premier, à une profondeur maximale donnée par 2×log2 n, où n est le nombre d'éléments, suivi d'un tri d'insertion sur le résultat.[1] quelle que soit la mise en œuvre, la complexité devrait être O(n log n) comparaisons sur la base de la moyenne. [2]
les garanties standard
de la norme C++11/14, std::sort est garanti d'avoir:
§25.4.1.1/3
la Complexité:
O(N log(N))(oùN == last - first) comparaisons.
l'autre algorithme de tri standard stable (à savoir std::stable_sort ) est garanti d'avoir:
25.4.1.2/3
complexité: il ne fait tout au plus
N log2(N)(oùN == last - first) comparaisons; si suffisamment de mémoire supplémentaire est disponible, il estN log(N).
pour std::forward_list::stable , à la place:
23.3.4.6/26
Complexité: Environ
N log(N)comparaisons, oùNestdistance(begin(), end()).
la même chose vaut pour std::list :
23.3.5.5/31
Complexité: Environ
N log(N)comparaisons, oùN == size().
algorithme de tri
la norme C++ ne spécifie pas l'algorithme de tri à appliquer dans l'un des cas ci-dessus. Ce serait souvent et inutile restriction de mise en œuvre.
si vous avez besoin de savoir que vous pourriez avoir la chance de chercher dans une spécification de compilateur spécifique. Par exemple, pour GNU GCC, vous commenceriez ici .
si vous voulez dire std::sort() :
extrait de la norme C++03, section 25.3. La garantie de performance:
template<class RandomAccessIterator>
void sort(RandomAccessIterator first, RandomAccessIterator last);
template<class RandomAccessIterator, class Compare> void sort(RandomAccessIterator first, RandomAccessIterator last,
Compare comp);
1 Effets: trie les éléments dans la gamme [Premier, Dernier].
2 Complexité: Environ N log N (où N == dernier - premier) comparaisons sur la base de la moyenne.
la norme c++ spécifie que le worst-case runtime de std::sort() est dans O(n log n) - où n est le nombre d'éléments triés (cf. C++11, Section 25.4.1.1).
la norme ne spécifie pas un algorithme de tri particulier.
ainsi, une implémentation conforme std::sort() est libre de choisir tout algorithme qui satisfait à l'exigence d'exécution ci-dessus.
Note que le C++ standard de révisions avant C++11 juste nécessaire que le moyenne runtime de std::sort() est dans O(n log n) .
Voir aussi la question stackoverflow quels algorithmes sont utilisés dans C++11 std:: sort dans différentes implémentations STL? pour se faire une idée des algorithmes de tri réels utilisés dans les implémentations STL du monde réel.