Significado de la complejidad promedio cuando se utiliza la notación Big-O

Question

Al responder a this question, comenzó un debate sobre la complejidad de QuickSort. Lo que recuerdo de mi época universitaria es que QuickSort es O(n^2) en el peor de los casos, O(n log(n)) en el caso promedio y O(n log(n)) (pero con un límite más estricto) en el mejor de los casos.

Lo que necesito es una explicación matemática correcta del significado de average complexity para explicar claramente de qué se trata a alguien que cree que la notación de grandes O solo se puede usar para el peor de los casos.

Lo que recuerdo si para definir la complejidad promedio debe considerar la complejidad del algoritmo para todas las entradas posibles, cuente cuántos casos degenerados y normales. Si la cantidad de casos degenerados divididos por n tiende a 0 cuando n crece, entonces puede hablarse de la complejidad promedio de la función general para los casos normales.

¿Es correcta esta definición o la definición de complejidad promedio es diferente? Y si es correcto, ¿alguien puede decirlo con más rigor que yo?

Answer 1

Si usted está buscando una definición formal, entonces:

complejidad media es el tiempo de ejecución expected para una entrada al azar.

Answer 2

Análisis medio caso hace lo siguiente:

Adoptar todas las entradas de una longitud fija (por ejemplo n), sumar todos los tiempos de funcionamiento de todas las instancias de esta longitud, y construir la media.

El problema es que probablemente tendrá que enumerar todas las entradas de longitud n para llegar a una complejidad promedio.

Answer 3

Creo que su definición es correcta, pero sus conclusiones son incorrectas.

No es necesariamente cierto que si la proporción de casos "malos" tiende a 0, entonces la complejidad promedio es igual a la complejidad de los casos "normales".

Por ejemplo, supongamos que 1/(n^2) casos son "malos" y el resto "normal", y los "malos" casos toman exactamente (n^4) operaciones, mientras que los casos "normales" toman exactamente n operaciones.

A continuación, el número medio de operaciones requeridas es igual a:

(n^4/n^2) + n(n^2-1)/(n^2) 

Esta función es O (n^2), pero no O (n).

En la práctica, sin embargo, puede encontrar que el tiempo es polinomial en todos los casos, y la proporción de casos "malos" se reduce exponencialmente. Ahí es cuando ignorarías los casos malos al calcular un promedio.

Answer 4

Tienes razón.

Big O (gran Theta etc.) se utiliza para medir funciones. Cuando escribes f = O (g) no importa lo que f y g signifiquen. Podrían ser la complejidad media de tiempo, peor complejidad del tiempo, las complejidades espaciales, denotan distribución de los primos etc.

peor de los casos la complejidad es una función que toma tamaño n, y le dice lo que es el número máximo de pasos de un algoritmo entrada dada de tamaño n.

La complejidad de caso medio es una función que toma el tamaño n, y le dice cuál es el número de pasos esperado de un algoritmo con una entrada de tamaño n.

Como ve el peor de los casos y la complejidad del caso promedio son funciones, por lo que puede utilizar grandes O para expresar su crecimiento.

Answer 5

Vamos a referirnos Big O Notation in Wikipedia:

Vamos fyg dos funciones definidas en algún subconjunto de los números reales. Uno escribe f(x)=O(g(x)) as x --> infinity si ...

Entonces, ¿qué la premisa de los estados definición es que la función f debe tomar un número como una entrada y producir una serie como una salida. ¿De qué número de entrada estamos hablando? Se supone que es una cantidad de elementos en la secuencia que se debe ordenar. ¿De qué número de salida podríamos estar hablando? Podría ser una cantidad de operaciones realizadas para ordenar la secuencia. Pero detente. ¿Qué es una función? Function in Wikipedia:

Una función es una relación entre un conjunto de entradas y un conjunto de salidas permisibles con la propiedad de que cada entrada está relacionada con exactamente un de salida.

estamos produciendo exacly uno salida con nuestra defition antes? No, nosotros no. Para un tamaño dado de una secuencia, podemos obtener una gran variación de la cantidad de operaciones. Por lo tanto, para garantizar que la definición sea aplicable a nuestro caso, debemos reducir un conjunto de posibles resultados (número de operaciones) a un solo valor. Puede ser un máximo ("el peor de los casos"), un mínimo ("el mejor de los casos") o un promedio.

La conclusión es que hablar sobre el mejor/peor/caso promedio es matemáticamente correcto y el uso de notación O grande sin los que en contexto de complejidad de clasificación es un poco descuidado.

Por otro lado, podríamos ser más precisos y usar una gran notación Theta en lugar de una notación O grande.