Análisis de algoritmo de casos promedio utilizando el método de incompatibilidad Kolmogorov

Se dice que el Método de Incompresibilidad simplifica el análisis de algoritmos para el caso promedio. Por lo que entiendo, esto se debe a que no hay necesidad de calcular todas las combinaciones posibles de entrada para ese algoritmo y luego derivar una complejidad promedio. En cambio, se toma una sola cadena incompresible como entrada. Como una cadena incompresible es típica, podemos suponer que esta entrada puede actuar como una aproximación precisa del caso promedio.

Estoy perdido con respecto a la aplicación real del Método de Incompresibilidad a un algoritmo. Por otro lado, no soy matemático, pero creo que esta teoría tiene aplicaciones prácticas en la programación diaria.

En última instancia, me gustaría aprender cómo puedo deducir el caso promedio de cualquier algoritmo dado, ya sea trivial o complejo. ¿Podría alguien demostrarme cómo se puede aplicar el método a un algoritmo simple? Por ejemplo, dada una cadena de entrada S, almacene todos los caracteres únicos en S, luego imprima cada uno individualmente:

void uniqueChars(String s) {
    char[] chars = chars[ s.length() ]
    int free_idx = 0;

    for (int i = 0; i < s.length(); i++) {
       if (! s[i] in chars) {
          chars[free_idx] = s[i]
          free_idx++;
       }
    }

    for (int i = 0; i < chars.length(); i++) {
        print (chars[i])
    }
}

Suponga una búsqueda lineal para verificar si la matriz contiene un elemento.

El fragmento de código anterior es solo por el argumento. Los mejores algoritmos mediante los cuales se puede demostrar la teoría son aceptables, por supuesto.

Hice esta pregunta en StackOverflow ( https://stackoverflow.com/q/24619383/3813812 ) en julio de 2014, y he recibido algunos comentarios útiles, pero no una respuesta definitiva. Como señaló uno de los comentaristas, esta pregunta es más adecuada para Computer Science StackExchange, por lo que pregunto aquí hoy.

Algunas publicaciones que he revisado incluyen:

1. Una introducción a la complejidad de Kolmogorov y sus aplicaciones, por Ming Li y Paul MB Vitányi

2. https://www.cs.duke.edu/~reif/courses/complectures/Li/KC-Lecture1.pdf

3. http://www.detectingdesign.com/PDF%20Files/Kolmogorov%20Complexity%202.pdf

Entre algunos otros recursos a los que no tengo enlaces disponibles.

Si mi comprensión de la aplicabilidad de la complejidad de Kolmogorov es inexacta o lo que pido no es práctico, agradecería una declaración con respecto al hecho.

La idea del método de incompresibilidad es que una entrada incompresible satisface ciertas propiedades que pueden ser útiles en el análisis. En su caso, la complejidad del algoritmo depende de cuántos caracteres aparecen en la cadena. Al procesar el$k$El carácter, el "tiempo de ejecución" (o más bien su proxy, el número de comparaciones al verificar la lista) es $\approx \alpha_k/2$ comparaciones en promedio, donde $\alpha_k$es la cantidad de personajes diferentes que se han visto hasta ahora. Para estimar$\alpha_k$, tenga en cuenta que podemos codificar el primero $k$ personajes usando aproximadamente $8\alpha_k + k\log \alpha_k$ bits, y deducimos que $8\alpha_k + k\log_2 \alpha_k \geq 8k$. Por lo tanto, a menos que$k$ es muy pequeño, $\alpha_k$ tiene que estar muy cerca de $256$, y podemos deducir que hay en promedio $128$comparaciones por personaje. Podemos usar la desigualdad para determinar qué tan grande$k$ necesita ser, y también lo que sucede cuando $k$ es pequeño.

La razón por la que estamos tratando de contar la complejidad exacta en el caso de su algoritmo es que los tiempos de ejecución en el peor y el mejor caso son ambos $\Theta(n)$. Usamos incompresibilidad para estimar$\alpha_k$, que también puede estimarse directamente utilizando métodos probabilísticos, pero el cálculo de incompresibilidad es probablemente más simple. Aún así, la incompresibilidad no elimina la necesidad de analizar el algoritmo probabilísticamente, solo hace que el análisis sea más manejable en algunos casos.

Como otro comentario (pero un poco más largo que un comentario real) sobre la respuesta aceptada:

1. La complejidad de Kolmogorov (o complejidad algorítmica ) trata con descripciones óptimas de "cadenas" (en el sentido general de las cadenas como secuencias de símbolos )

2. Una cadena es (suficientemente) incompresible o (suficientemente) algorítmicamente aleatoria si su descripción (algorítmica) (kolmogorov comlplexity K ) no es menor que su tamaño (literal) . En otras palabras, la descripción óptima de la cadena es la cadena misma .

3. El principal resultado de la teoría es que la mayoría de las cadenas son (algorítmicamente) aleatorias (o típicas) (lo que también está relacionado con otras áreas como los Teoremas de Goedel, a través del trabajo de Chaitin)

4. La complejidad de Kolmogorov está relacionada con la entropía probabilística (o Shannon) , de hecho, la entropía es un límite superior en KC. Y esto relaciona el análisis basado en la complejidad descriptiva con el análisis basado en la probabilidad. Pueden ser intercambiables.

5. A veces puede ser más fácil usar análisis probabilisrtic, otras complejidad descriptiva (digamos puntos de vista de lo mismo)

Entonces, a la luz de lo anterior, suponiendo una entrada algorítmicamente aleatoria a un algoritmo, se supone lo siguiente:

1. La entrada es típica , por lo tanto, el análisis describe el escenario de caso promedio (punto 3 anterior)
2. El tamaño de entrada está relacionado de cierta manera con su probabilidad (punto 2 anterior)
3. Se puede pasar de la vista algorítmica a la vista probabilística (punto 4 anterior)