Complejidad computacional de conteo de símbolos.

Question

Considere la función de conteo $ \ \ {x \ \ \ \ \ mathbb n $ que cuenta el número de ocurrencias del símbolo $ x $ .

Estoy confundido acerca de la complejidad (asintótica) de la computación de esta función, donde la salida debe representarse en un sistema no unario (por ejemplo, binario) . Mi intuición sugiere firmemente que esto debe ser lineal, es decir, $ o (n) $ donde $ n $ es el número de ocurrencias del símbolo $ x $ en la entrada.

En cuanto a mi comprensión, hay múltiples interpretaciones de computación, por ejemplo,

• Máquinas de una sola banda, para las cuales mi mejor idea tiene tiempo de ejecución $ \ omega (n ^ 2 \ log n) $ creo (la clase $ \ log n $ proviene de la suposición de que la función de sucesor binario tiene $ \ omega (n) $ tiempo de ejecución, donde $ n $ es la duración de una representación binaria de un número natural, y el $ n ^ 2 $ proviene de la suposición de que la máquina de Turing tiene que viajar sobre todos los $ x $ 's para llegar a su cuenta actual),
• Máquinas multi-bandas, para las que creo que tengo una idea de tiempo de ejecución $ \ omega (n \ log n) $ ,
• Máquinas de acceso aleatorio, que no conozco en absoluto.

Así que mi pregunta es la siguiente.

¿Cuál es la complejidad computacional de la función de conteo en los diversos modelos de computación? ¿Es lineal en cualquiera de ellos?

Si es relevante, pregunto desde el punto de vista de la álgebra abstracta, donde estoy tratando de evaluar la complejidad computacional del problema de la palabra en algún grupo específico.

Answer 1

Las máquinas de [P> Turing son un modelo agradable con varias ventajas, principalmente su simplicidad, pero no son la primera opción al analizar algoritmos. Los algoritmos se analizan generalmente implícitamente en el modelo de la máquina RAM, y en algunos casos, en el modelo bss .

Aquí hay algunos comentarios sobre la complejidad computacional del conteo en varios modelos:

Máquina de Turing de una sola cinta: Estos solo se consideran, ya que es relativamente fácil probar los límites más bajos en ellos. Son incluso menos realistas un modelo de cálculo que las máquinas de Turing de múltiples cintas.

Máquina de Turing de múltiples cintas: Es un ejemplo estándar en complejidad amortizada que un contador cada vez mayor se puede implementar utilizando $ o (1) $ Operaciones de bit amortizadas. Esto se debe a que la mitad del tiempo, solo un bit cambia, un cuarto de la época, solo dos bits, y así sucesivamente, para un número total de bits modificados que es $ 1/2 + 2 / 4 + 3/8 + \ CDOTS= 2 $ . La complejidad de la máquina de Turing es lineal en eso, y por lo tanto, el conteo se puede implementar en $ o (n) $ .

Ram Machine: Una máquina RAM consiste en finamente muchos registros y una memoria de acceso aleatorio. Los registros son $ o (\ log n) $ -bits long, donde $ n $ es el tamaño de la entrada. Las operaciones razonables en los registros toman tiempo constante. En particular, aumentar un contador que puede contar hasta $ \ mathit {poly} (n) $ toma $ O (1 ) $ peor caso En particular, su función se ejecutará en $ o (n) $ .

Machine BSS: tiene que tener cuidado al realizar la aritmética en grandes cantidades. En la máquina RAM, la aritmética solo toma tiempo constante si la magnitud de los operandos es $ \ mathit {poly} (n) $ . Una máquina BSS permite el acceso a registros especiales que almacenan los valores en algún campo, dicen los números reales. Puede realizar una aritmética y comparaciones de tiempo constante, pero no funciona como el piso. Tampoco se le permite usar tales valores para la indexación. (Si no te limitas lo suficiente, pronto se resolverá sentado en el tiempo polinomial). Puede pensar en una máquina BSS como complacientes a las operaciones de punto flotante, que en la práctica toman un tiempo constante, mientras que ignora la precisión finita involucrada en ellas. .