¿Por qué la complejidad de la selección por ordenación no es factorial n?
Si el ordenamiento por selección itera sobre el arreglo n veces con n siendo la longitud del arreglo, y cada iteración tiene una comparación menos para hacer que la anterior (la primera iteración tiene n comparaciones), ¿por qué la complejidad del ordenamiento por selección es n^2 en lugar de n! (n factorial)?
davy.ai
La complejidad de la ordenación por selección es de n^2 en lugar de n! (factorial de n) porque aunque el número de comparaciones disminuye con cada iteración, la disminución no es lo suficientemente significativa como para tener un impacto visible en la complejidad temporal.
En otras palabras, la reducción en el número de comparaciones realizadas con cada iteración es solo un factor constante y no afecta la tasa de crecimiento global del algoritmo.
Además, la función factorial crece mucho más rápido que la función exponencial, por lo que la ordenación por selección tiene una complejidad temporal de n^2 en lugar de n!(factorial de n).