Esta pregunta se refiere al algoritmo de Fisher-Yates para devolver una combinación aleatoria de una matriz determinada. La página de Wikipedia dice que su complejidad es O (n), pero creo que es O (n log n).
En cada iteración i, se elige un número entero aleatorio entre 1 e i. Simplemente escribir el número entero en la memoria es O (log i), y dado que hay n iteraciones, el total es
O (log 1) + O (log 2) + ... + O (log n) = O (n log n)
que no es mejor el algoritmo ingenuo. ¿Me estoy perdiendo de algo?
Nota: El algoritmo ingenuo es asignar a cada elemento un número aleatorio en el intervalo (0,1), luego ordenar la matriz con respecto a los números asignados.
ds.algorithms
permutations
Tomer Vromen
fuente
fuente
El modelo estándar de cómputo supone que las operaciones aritméticas en enteros O (log n) pueden ejecutarse en tiempo constante, ya que esas operaciones generalmente se entregan en hardware. Entonces, en el algoritmo de Fisher-Yates, "escribir el entero i en la memoria" solo toma O (1) tiempo.
Por supuesto, es perfectamente significativo analizar el algoritmo en términos de operaciones de bits, pero el modelo de costo de bits es menos predictivo del comportamiento real. Incluso el bucle simple
for i = 1 to n: print(i)requiere operaciones de bit O (n log n).fuente
Esta es una respuesta a "[el algoritmo de Fisher-Yates] no es mejor que el algoritmo ingenuo. ¿Me estoy perdiendo algo aquí?" que hiciste en la pregunta.
En su algoritmo "ingenuo" que usa números reales: ¿cuántos bits de precisión usa? Si está contando la complejidad de los bits (como parece estar haciendo para Fisher-Yates), y el algoritmo usa k bits aleatorios para los números reales, entonces su tiempo de ejecución sería Ω (kn log n), ya que compara dos k- Los números reales de bit toman tiempo Ω (k). Pero k debe ser al menos Ω (log n) para evitar que dos elementos se asignen al mismo número real, lo que significa que el algoritmo tarda un tiempo Ω (n log 2 n), que es más lento que el shuffle de Fisher-Yates factor de log n.
Si solo cuenta el número de operaciones aritméticas y de comparación e ignora su complejidad de bits, entonces Fisher-Yates es Θ (n) y su algoritmo es Θ (n log n), que sigue siendo un factor de log n aparte.
fuente
No hay nada especial en los enteros para este problema.
Por ejemplo, las tablas hash (que almacenan cualquier tipo de valores) no tienen O (1) tiempo de acceso si la función hash debe leer el valor completo para calcular su hash. n elementos únicos requieren log n bits cada uno en promedio para representar, no importa cuán inteligente sea su representación, y cualquier función hash que lea toda su entrada, por lo tanto, tomará al menos tanto tiempo para computar. En la práctica, son más rápidos que los árboles rojo-negros, pero asintóticamente no son mejores.
La brouhaha a la que hace referencia randomwalker fue sobre un artículo de POPL 2008 ( http://portal.acm.org/citation.cfm?doid=1328438.1328460 ), discutido aquí: http://blog.computationalcomplexity.org/2009/05/shaving- logs-with-unit-cost.html
En esa publicación, Lance Fortnow describe cómo, como estudiante, se quejaba de que la clasificación realmente requiere n log ^ 2 n tiempo si debemos leer todos los log n bits de dos elementos para compararlos, lo que parece una objeción razonable.
fuente
En realidad, O (n log n) es un límite inferior para este problema en modelos donde la clasificación es O (n log n). Si todas las permutaciones son igualmente probables, entonces el algoritmo en función de flujos aleatorios a permutaciones debe ser sobreyectivo. ¡No hay! permutaciones por lo que en algo así como un modelo de árbol de decisión hay ramas de longitud al menos O (log n!) = O (n log n).
fuente
En TCS, consideramos, si no se establece lo contrario explícitamente, la complejidad en una máquina de Turing. Si bien esto está bien para fines teóricos, los resultados no son muy útiles en la práctica, ya que implementamos diferentes modelos de máquina (es decir, aproximaciones finitas) en hardware. Por lo tanto, es una pregunta factible preguntar por la complejidad de esos modelos. Por ejemplo, normalmente suponemos que las máquinas de registro (similares a las CPU reales) pueden realizar operaciones atómicas en dos registros en tiempo constante; esto es lo que podría haberse empleado aquí.
En resumen: usted piensa en términos de TM, los autores del artículo en términos de RM. Los dos tienen razón.
fuente