Preguntas etiquetadas con sorting

12
¿Podemos ordenar sin permutaciones?

Es bien sabido que la clasificación de permutaciones por transposición está en , ya que el número mínimo de transposiciones requeridas para clasificar π ∈ S n es exactamente i n v ( π ) = { ( i , j ) ∈ [ n ] × [ n ] : i < j  y  π ( i ) > π ( j ) }PP\sf{P}π∈Snπ∈Sn\pi \in...

12
encontrar los elementos k más pequeños en la matriz en O (k)

Esta es una pregunta interesante que he encontrado en la web. Dada una matriz que contiene n números (sin información sobre ellos), debemos preprocesar la matriz en tiempo lineal para que podamos devolver los k elementos más pequeños en el tiempo O (k), cuando se nos da un número 1 <= k <=...

12
Está ordenando

En la preimpresión reciente https://arxiv.org/abs/1801.00776 , se afirma que números reales se pueden ordenar en el tiempo O ( n √nnn y espacio lineal. El artículo parece razonable, aunque no soy un experto en algoritmos de clasificación.O(nlogn−−−−√),O(nlog⁡n),O(n \sqrt{\log n}), Si es...

12
Ordenar secuencias de "k-tonic"

Espero que alguien sepa algo sobre esto, así que no tengo que leer la literatura ... Considere una secuencia de números . Piense en la secuencia como n - 1 intervalos [ x 1 , x 2 ] , [ x 2 , x 3 ] , … , [ x n - 1 , x n ] . Claramente, la secuencia original es bitónica si algún punto en la línea...

10
Ordenando con un promedio de

¿Existe un algoritmo de clasificación basado en la comparación que utiliza un promedio de l g ( n ! ) + O ( n )lg(n!)+o(n)\mathrm{lg}(n!)+o(n) comparaciones? La existencia de un algoritmo de comparación l g ( n ! ) + O ( n ) en el peor de los casos lg(n!)+o(n)\mathrm{lg}(n!)+o(n)es un problema...

9
¿Complejidad de tipo ciego?

Todos sabemos que la complejidad mínima de un algoritmo de clasificación basado en la comparación es la comparación de . Estoy tratando de hacer una clasificación a ciegas , es decir, dado un número salida de un circuito (con puertas booleanas, aritméticas y de "comparación") que ordena una lista...

8
Complejidad de clasificación

No es difícil mostrar que ordenar una matriz de números es difícil para . Si la entrada es una matriz de 1s y 0s, entonces es esencialmente la función C o u n t (dados n bits, genera el número de 1s en binario) ya que C o u n t está completo para T C 0 y es posible para convertir números unarios en...

8
¿Qué ventaja tiene heapsort sobre smoothsort?

Wikipedia afirma que las ventajas de smoothsort sobre heapsort es que a veces se acerca más al tiempo O (n). Ahora me preguntaba ¿qué ventaja tiene la ordenación dinámica sobre la ordenación suave? O para reformular esta pregunta, ¿la ordenación suave siempre es una mejor opción que la ordenación...