Je suis en train de lire le livre de Nicolai Josuttis sur les algorithmes C++STL. Pour de nombreux algorithmes tels que stable_sort(), il mentionne que la complexité de l'algorithme est de n * log(n) si la mémoire disponible est suffisante, sinon elle est de n * log(n) * log(n). Ma question est la suivante : comment l'utilisation de la mémoire affecte-t-elle la complexité ? Et comment la STL détecte-t-elle une telle situation ?
Réponse
Trop de publicités?
En regardant la STL de gcc, vous trouverez inplace_merge en stl_algo.h . Il s'agit d'une implémentation traditionnelle du tri par fusion, avec O(N), utilisant un tampon de la même taille que l'entrée. Ce tampon est alloué par _Temporary_buffer , de stl_tempbuf.h . Ceci invoque get_temporary_buffer qui invoque finalement new. Si cette dernière lève une exception, l'exception est attrapée, et le tampon est NULL - ce qui est le cas "pas assez de mémoire". Dans ce cas, la fusion fonctionne avec __merge_without_buffer qui est O(N lg N). Comme la profondeur de récursion du tri par fusion est O(lg N), on obtient O(N lg N) dans le cas du tri par fusion "traditionnel" (avec tampon), et O(N lg N lg N) dans la version sans tampon.
