Análise de algoritmo de caso médio usando o método de incompatibilidade de Kolmogorov

Diz-se que o Método da Incompressibilidade simplifica a análise de algoritmos para o caso médio. Pelo que entendi, isso ocorre porque não há necessidade de calcular todas as combinações possíveis de entrada para esse algoritmo e derivar uma complexidade média. Em vez disso, uma única string incompressível é usada como entrada. Como uma sequência incompressível é típica, podemos assumir que essa entrada pode atuar como uma aproximação precisa do caso médio.

Estou perdido em relação a realmente aplicar o Método de Incompressibilidade a um algoritmo. Como um aparte, eu não sou um matemático, mas acho que essa teoria tem aplicações práticas na programação cotidiana.

Por fim, gostaria de aprender como deduzir o caso médio de qualquer algoritmo, seja trivial ou complexo. Alguém poderia me demonstrar como o método pode ser aplicado a um algoritmo simples? Por exemplo, dada uma sequência de entrada S, armazene todos os caracteres exclusivos em S e imprima cada um 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])
    }
}

Suponha uma pesquisa linear para verificar se a matriz contém um elemento.

O trecho de código acima é apenas para fins de argumento. Melhores algoritmos pelos quais a teoria pode ser demonstrada são aceitáveis, é claro.

Fiz essa pergunta no StackOverflow ( https://stackoverflow.com/q/24619383/3813812 ) em julho de 2014 e recebi alguns comentários úteis, mas não uma resposta definitiva. Como um dos comentadores apontou, esta pergunta é mais adequada para o Computer Science StackExchange, então pergunto aqui hoje.

Alguma literatura que revi inclui:

1. Introdução à complexidade de Kolmogorov e suas aplicações, de Ming Li e 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 alguns outros recursos aos quais não tenho links disponíveis.

Se meu entendimento da aplicabilidade da complexidade de Kolmogorov for impreciso ou o que eu pedir for impraticável, eu apreciaria uma declaração com relação ao fato.

A idéia do método de incompressibilidade é que uma entrada incompressível satisfaça certas propriedades que podem ser úteis na análise. No seu caso, a complexidade do algoritmo depende de quantos caracteres aparecem na string. Ao processar o$k$caractere, o "tempo de execução" (ou melhor, seu proxy, o número de comparações ao verificar a lista) é $\approx \alpha_k/2$ comparações em média, onde $\alpha_k$é o número de caracteres diferentes que foram vistos até agora. Para estimar$\alpha_k$, observe que podemos codificar o primeiro $k$ caracteres usando aproximadamente $8\alpha_k + k\log \alpha_k$ bits, e deduzimos que $8\alpha_k + k\log_2 \alpha_k \geq 8k$. Portanto, a menos que$k$ é muito pequeno, $\alpha_k$ tem que estar muito perto de $256$, e podemos deduzir que existem em média $128$comparações por personagem. Podemos usar a desigualdade para determinar quão grande$k$ precisa ser, e também o que acontece quando $k$ é pequeno.

O motivo pelo qual estamos tentando contar a complexidade exata no caso do seu algoritmo é que o tempo de execução do pior e do melhor caso é ambos $\Theta(n)$. Usamos a incompressibilidade para estimar$\alpha_k$, que também pode ser estimado diretamente usando métodos probabilísticos, mas o cálculo da incompressibilidade é provavelmente mais simples. Ainda assim, a incompressibilidade não evita a necessidade de analisar o algoritmo probabilisticamente - apenas torna a análise mais tratável em alguns casos.

Como um comentário adicional (mas um pouco mais longo que um comentário real) sobre a resposta aceita:

1. A Complexidade Kolmogorov (ou Complexidade Algorítmica ) lida com descrições ótimas de "strings" (no sentido geral de strings como sequências de símbolos )

2. Uma cadeia de caracteres é (suficientemente) incompressível ou (suficientemente) algorítmica se a sua descrição (algorítmica) (complexidade kolmogorov K ) não for menor que seu tamanho (literal) . Em outras palavras, a descrição ideal da string é a própria string .

3. O principal resultado da teoria é que a maioria das strings é (algorítmica) aleatória (ou típica) (que também está relacionada a outras áreas como os Teoremas de Goedel, através do trabalho de Chaitin)

4. A complexidade de Kolmogorov está relacionada à entropia probabilística (ou Shannon) ; na verdade, a entropia é um limite superior do KC. E isso relaciona a análise baseada na complexidade descritiva à análise baseada em probabilística. Eles podem ser intercambiáveis.

5. Às vezes, pode ser mais fácil usar a análise probabilística, outras complexidades descritivas (visões do mesmo, digamos)

Portanto, à luz do exposto, assumindo uma entrada aleatória algorítmica para um algoritmo, assume-se o seguinte:

1. A entrada é típica , portanto, a análise descreve o cenário de caso médio (ponto 3 acima)
2. O tamanho da entrada está relacionado, de certa maneira, à sua probabilidade (ponto 2 acima)
3. Pode-se passar da visão algorítmica para a visão probabilística (ponto 4 acima)