¿Por qué está ordenando una cadena O (n log n)?

Question

Duplicar posible:
Plain English explanation of Big O

En la respuesta a un rompecabezas de programación que dijo ordenar una serie toma O (n log n) tiempo. ¿Cómo se deriva eso?

¿Alguien tiene un buen enlace de referencia para los recursos de Big O?

Gracias

Answer 1

Una definición y algunos ejemplos de Big O se pueden encontrar mediante el uso de un motor de búsqueda, por ejemplo, aquí:

• http://en.wikipedia.org/wiki/Big_O_notation

Una explicación de los algoritmos de clasificación basados ​​en elementos que comparan, junto con una explicación para el límite inferior del número de comparaciones requeridas, se puede encontrar aquí:

• http://en.wikipedia.org/wiki/Comparison_sort

Answer 2

¿Por qué está ordenando una cadena O (n log n)?

La clasificación de los caracteres en una cadena no es necesariamente O (n log n).

• O (n log n) es la óptimo valor para un comparison sort. También es la complejidad de la implementación de clasificación predeterminada de muchos idiomas. Sin embargo, es ciertamente posible hacerlo peor que esto. La complejidad de ordenar los caracteres en una cadena depende del algoritmo específico que elija para resolver esta tarea.
• También es posible hacerlo mejor que O (n log n) en algunos casos utilizando un algoritmo de ordenación que no es una clasificación de comparación. Por ejemplo, si sabe que tiene una cadena ASCII con un máximo de 127 caracteres distintos, puede usar un counting sort que es O (n). Un tipo de conteo también sería factible para cadenas Unicode donde todos los caracteres están en el Basic Multilingual Plane.