En el sentido más formal, el tamaño de la entrada se mide en referencia a una implementación del algoritmo de la máquina de Turing, y es la cantidad de símbolos alfabéticos necesarios para codificar la entrada.
Esto es, por supuesto, bastante abstracto, y es muy difícil trabajar con él en la práctica, o al menos muy molesto. Necesitaríamos considerar cómo vamos a especificar delimitadores, etc., etc. Lo que sucede normalmente en la práctica es que buscamos una medición proxy del tamaño de la entrada, algo más conveniente y accesible, pero que no causa ningún problema matemático en nuestro análisis.
Usando su ejemplo "abcde", normalmente sería el caso de que el alfabeto que usamos para la entrada sea pequeño, por lo que incluso usando la medición proxy de caracteres, sabemos que incluso en una máquina de Turing, podemos, si nos molestamos, especifique una codificación de entrada que convierta "abcde" en alguna forma codificada que tenga una longitud máxima de 5 × c para alguna c constante . Esta expansión por una constante típicamente no haría ninguna diferencia en nuestro análisis asintótico, ya que descartamos habitualmente factores constantes.55×c c
En un caso diferente, a menudo medimos el tamaño de un gráfico de entrada por el número de vértices . Claramente, si queremos especificar gráficos arbitrariamente grandes, el tamaño de la entrada codificada no es simplemente n , ¿qué pasó con los bordes, por ejemplo? Lo que sí sabemos es que podemos usar un esquema de codificación razonable que represente el gráfico en N = c ⋅ n 2 log n bits. Esto es un poco más una expansión que una constante, pero en muchos casos interesantes, solo estamos tratando con una granularidad de polinomios, y los polinomios se componen muy bien de muchas maneras, en particular, por ejemplo, si determinamos que nuestro tiempo de ejecución es O ( p (nnN=c⋅n2logn donde p es un polinomio, entonces sabemos que hay algún polinomio p ′ tal que O ( p ( n ) ) = O ( p ′ ( N ) ) , entonces cuando volvemos a la medida formal de la entrada , todavía estamos en tiempo polinómico.O(p(n))pp′O(p(n))=O(p′(N))
Un lugar donde esto podría caerse es cuando trabajas con números. Como un número con magnitud puede codificarse en n = O ( log m ) bits, si nuestro tiempo de ejecución fuera O ( m ) , esto sería O ( 2 n ) - exponencial en el tamaño de entrada real - lo que haría que la magnitud m una mala elección para un proxy para el tamaño de entrada si quisiéramos hablar sobre la membresía en P, por ejemplo (cuando se trata de Strongly- N P -complete y Weakly- N Pmn=O(logm)O(m)O(2n)mPNPNP-completo, recuerda esto). Por otro lado, si todo lo que nos interesara fuera la capacidad de decisión, entonces sería una medida proxy bastante buena.
Entonces, aunque no hay una regla establecida para elegir una medida de proxy para el tamaño de entrada, el requisito es que la expansión o contracción del tamaño de proxy en comparación con el tamaño de entrada debe ser compatible con lo que está tratando de probar. Como regla general, los cambios constantes en los factores casi nunca importan, los pequeños factores polinomiales normalmente están bien y funcionan para la mayoría de la teoría básica que ves, los factores polinomiales grandes aún pueden funcionar para la teoría, pero pueden ser una desagradable sorpresa en la práctica, y las cantidades exponenciales de cambio son normalmente demasiado extremas.
Depende de su modelo de cálculo y también, lamentablemente, a veces del algoritmo mismo.
Sin embargo, muchos algoritmos no se miden con respecto al tamaño de entrada "real". Luego, debe observar cuidadosamente a qué se refiere la declaración del análisis.
fuente