implementaciones nth_element Complejidades

Question

¿Alguien sabe tanto los tiempos de ejecución esperados como los peores tiempos de ejecución para las diferentes implementaciones de std::nth_element? Yo uso este algoritmo casi todos los días.

Estoy especialmente interesado en las versiones de STL que se envían con los recientes compiladores de Microsoft, pero cualquier información sobre este tema es útil.

Please note that this is not a duplicate of this question. Entiendo qué algoritmos existen, pero estoy interesado en qué implementaciones usan qué algoritmos.

Para el fondo, existen algoritmos bien conocidos para hacer esto. Uno es el caso promedio de O (n) y el peor caso de O (n log n), uno es el peor caso de O (n) pero lento en la práctica (mediana de las medianas). También tenga en cuenta que there is talk of interesting implementation strategies to get worst-case O(n) running times that are fast in practice. El estándar dice que esto debe ser peor O (n) tiempo promedio.

Answer 1

El tiempo de ejecución esperado es O (N) El peor tiempo de ejecución para la mayoría de implementaciones es O (N * N) porque la mayoría de las implementaciones usan QuickSelect y es posible que QuickSelect se ejecute en particiones defectuosas. Eso es cierto para Microsoft VS2008, VS2010 & VS2012.

Ahora con el nuevo estándar ISO C++ 2011, la complejidad de std :: sort se ha reforzado, se garantiza que será O (N * log N) y no tiene un caso peor ya que se usa IntroSort de David Musser: - use QuickSort y si partes de la matriz experimentan partición defectuosa, cambie a heapsort.

Idealmente, exactamente igual debería aplicar std :: nth_element, pero el estándar ISO C++ 2011 no ha ajustado los requisitos de complejidad. Entonces std :: nth_element podría ser O (N * N) en el peor de los casos. Esto podría deberse a que en el documento original de David Musser (ver here) no mencionó qué algoritmo debería intercambiarse si QuickSelect falla.

En el peor de los casos, se podría usar la mediana de las medianas usando grupos de 5 (he visto un documento con los grupos recomendados de 7 pero no puedo encontrarlo). Por lo tanto, una implementación de calidad de std :: nth_element podría usar QuickSelect y cambiar a la mediana de las medianas si el particionamiento no funciona. Esto garantizaría el comportamiento O (N). QuickSelect puede mejorarse mediante el muestreo haciendo que el peor de los casos sea poco probable pero no imposible.

Answer 2

cppreference dice, primero ordena y luego encuentra el enésimo elemento, pero de esta manera el promedio debería ser O(n log n) (por algoritmos de clasificación basados ​​en la comparación), pero escribieron el promedio es O (n), parece incorrecto excepto usar ordenación como raíz ordenar, ... pero debido a que tiene una entrada basada en la comparación genérica, parece que es imposible usar la ordenación de radix o de cualquier otro tipo que no se base en la comparación. de todos modos, usar algoritmos de clasificación rápidos es mejor que usar el algoritmo de selección normal en la práctica (memoria y tiempo promedio).

Answer 3

La implementación en GCC 4.7 usa introspective selection por David Musser (aquí tiene su paper dando detalles sobre introsort e introselect). Según esos documentos, el tiempo de ejecución del peor de los casos es O (n).