Dadas entradas , construimos una red de clasificación aleatoria con puertas seleccionando iterativamente dos variables con y agregando una puerta de comparación que las intercambia si .x 0 , … , x n - 1 m x i , x j i < j x i > x j
Pregunta 1 : Para fijo , ¿qué tan grande debe ser para que la red se ordene correctamente con probabilidad ?m > 1
Tenemos al menos el límite inferior ya que una entrada que está correctamente ordenada, excepto que cada par consecutivo se intercambia tomará tiempo para cada par para ser elegido como comparador. ¿Es ese también el límite superior, posiblemente con más factores ?Θ ( n 2 log n 2 ) log n
Pregunta 2 : ¿Existe una distribución de compuertas de comparación que logre , quizás eligiendo comparadores cercanos con mayor probabilidad?
fuente
Respuestas:
Aquí hay algunos datos empíricos para la pregunta 2, basados en la idea de DW aplicada al ordenamiento bitónico. Para variables, elija con probabilidad proporcional a , luego seleccione uniformemente al azar para obtener un comparador . Esto coincide con la distribución de los comparadores en orden bitónico si es una potencia de 2, y se aproxima de otra manera.j - i = 2 k lg n - k i ( i , j ) nnorte j - i = 2k lgn - k yo ( i , j ) norte
Para una secuencia infinita dada de compuertas extraídas de esta distribución, podemos aproximar el número de compuertas requeridas para obtener una red de clasificación clasificando muchas secuencias de bits aleatorias. Aquí está esa estimación para tomando la media de más de secuencias de compuerta con secuencias de bits utilizadas para aproximar el conteo: parece coincidir con , la misma complejidad que la ordenación bitónica. Si es así, no comemos un factor adicional debido al problema del colector de cupones de cruzar cada puerta.100 6.400 Θ ( n log 2 n ) log nn<200 100 6400 Θ(nlog2n) logn
Para enfatizar: estoy usando solo secuencias de bits para aproximar el número esperado de puertas, no . Las puertas medias requeridas aumentan con ese número: para si uso secuencias , y , las estimaciones son , y . Por lo tanto, es posible que las últimas secuencias aumenten la complejidad asintótica, aunque intuitivamente se siente poco probable.6400 2n n=199 6400 64000 640000 14270±1069 14353±1013 14539±965
Editar : Aquí hay una gráfica similar hasta , pero usando el número exacto de puertas (calculado a través de una combinación de muestreo y Z3). He cambiado de potencia de dos a arbitraria con probabilidad proporcional a . todavía parece plausible.n=80 d=j−i d∈[1,n2] logn−logdd Θ(nlog2n)
fuente