A continuación, supongamos que estamos trabajando con una máquina Turing de cinta infinita.
Al explicar la noción de la complejidad del tiempo a alguien, y por qué se mide en relación con el tamaño de entrada de una instancia, me topé con la siguiente afirmación:
[..] Por ejemplo, es natural que necesite más pasos para multiplicar dos enteros con 100000 bits que, por ejemplo, multiplicar dos enteros con 3 bits.
El reclamo es convincente, pero de alguna manera saluda con la mano. En todos los algoritmos que encontré, cuanto mayor es el tamaño de entrada, más pasos necesita. En palabras más precisas, la complejidad del tiempo es una función monótonamente creciente del tamaño de entrada.
¿Es el caso que la complejidad del tiempo es siempre una función creciente en el tamaño de entrada? Si es así, ¿por qué es así? ¿Hay alguna prueba de eso más allá de agitar las manos?
Respuestas:
No. Considere una máquina de Turing que se detiene después de pasos cuando el tamaño de entrada n es par, y se detiene después de n 2 pasos cuando n es impar.n n n2 n
Si te refieres a la complejidad de un problema , la respuesta sigue siendo no. La complejidad de la prueba de primalidad es mucho menor para números pares que para números impares.
fuente
Probablemente los algoritmos sublineales sean de su interés, que no leen toda la entrada. Ver por ejemplo http://www.dcs.warwick.ac.uk/~czumaj/PUBLICATIONS/DRAFTS/Sublinear-time-Survey-BEATCS.pdf .
fuente
Dicho esto, los tiempos de ejecución promedio pueden contener componentes oscilantes, por ejemplo Mergesort .
fuente