Complejidad asintótica de la clasificación mediante comparaciones k

8

La clasificación mediante comparaciones de 2 elementos tiene una complejidad asintótica en el peor de los casos de nlog2(n) (alcanzado por mergesort, heapsort, inserción binaria, ford-johnson al menos), lo cual es óptimo.

Si ordenamos usando comparaciones que ordenan k elementos como bloques de construcción, el límite inferior teórico de información es . Podemos alcanzar fácilmente n log k ( n )nlogk!(n)nlogk(n) con inserción k-aria.

Pregunta: ¿Dónde está la complejidad óptimo entre y n log k ! ( n )nlogk(n)nlogk!(n) ?

Los árbitros apropiados también serían apreciados.

Editar: porque no estaba claro:

Estoy interesado en la complejidad de , con k = O ( 1 ) . Tiene el comportamiento asintótico de α n log 2 ( n ) con α [ 1nk=O(1)αnlog2(n), y me gustaría tener más precisión sobreα.α[1log2(k),1log2(k!)]α

slan_21
fuente

Respuestas:

2

Primero, traigamos aquellos a lo que creo que es la forma correcta de mirar.


Θ(nlogk(n))=Θ(nlog2(n)log2(k))=Θ(nlog2(n)log2(k))

y

Θ(nlogk!(n))=Θ(nlog2(n)log2(k!))=Θ(nlog2(n)klog2(k))



Observe que una comparación -ary es suficiente parakk2 comparaciones simultáneas (binarias).

por 2k, k2Θ(k).

Por la red AKS , para2kO(n), k-ary las comparaciones son suficientes para ordenar.O(nlog2(n)k) k

Cuando nk, -ary comparación es suficiente para ordenar.1k 1O(nlog2(n)k)

Por lo tanto, para 2k, k-ary las comparaciones son suficientes para ordenar.O(nlog2(n)k) k


k -ary comparaciones son suficientes para un5 k-ary(4k2) comparación.

por 4k, comparaciones de k -ary son suficientes para una5k-ary(32k) comparación.

por 2kn, log32(nk)=log2(nk)log2(32).

por 2kn, k-ary las comparaciones son suficientes para ordenar.5log2(nk)log2(32) k

por 2n, Al menos una comparación -ary es necesaria para ordenar.k

Por lo tanto, para 2kn y nkO(1), la clasificación requiere exactamente k -ary comparaciones.Θ(1) k


Sospecho que uno podría refinar la segunda de mis dos
conclusiones para mostrar que se logra su límite inferior.


fuente
No es lo que tenía en mente, pero aún así es agradable. Estoy interesado en la complejidad de , con k = O ( 1 ) . Tiene el comportamiento asintótico de α n l o g 2 ( n ) con α [ 1nk=O(1)αnlog2(n), y me gustaría tener más precisión sobreα. Acerca de su punto de vista, no creo que llegue al límite inferior de esa manera, porque5 log 2 ( nα[1log2(k),1log2(k!)]αque no lo hará. 5log2(nk)log2(32)=O((nk)log2(5)log2(32))
slan_21
Iba a interpretarlo de esa manera antes de darme cuenta de que, por lo que puedo encontrar, la constante óptima no se conoce incluso para k=2.
Ahora me doy cuenta de que su uso de la base en el primer logaritmo que escriba podría abordar mi punto.2 Es el número óptimo de comparaciones binarias dividido por nlog2(n)sabe converger a ? 1
Sí, para el número óptimo de comparaciones dividido por n log 2 ( n ) converge a 1. Muchos algoritmos logran esto, el más fácil probablemente sea la inserción binaria (que necesita n i = 2log 2 ( i )n log 2 ( n ) comparaciones). k=2nlog2(n)i=2nlog2(i)nlog2(n)
slan_21