Uma eficiência mínima possível pode ser comprovada?

Dado um problema, é possível provar qual seria a melhor eficiência de pior algoritmo de um algoritmo para resolver esse problema?

Por exemplo, vamos dar o problema de classificar uma matriz.

Muitos dos algoritmos de classificação mais simples têm uma eficiência de pior caso de $O(n^2)$como Classificação rápida e Classificação de bolha. No entanto, existem outros algoritmos, como Timsort e Smoothsort, que possuem , o que é mais eficiente.$O(n \log n)$

Nenhum outro algoritmo (que eu saiba) conseguiu classificar uma matriz com mais eficiência que . É possível provar que não existe outro algoritmo que seja mais eficiente?$\Theta(n\log n)$

Se existe uma maneira de provar os algoritmos de classificação, se existe um algoritmo mais eficiente, isso também se aplica a outros problemas?

Certamente, existem maneiras de mostrar que certos algoritmos devem levar um certo tempo ou determinadas estruturas de dados requerem uma certa quantidade de espaço. Uma maneira comum é usar a teoria da informação.

Uma matriz não classificada é uma permutação da matriz classificada. tem$n!$possíveis permutações. O trabalho de classificar, no sentido teórico da informação, é descobrir exatamente qual permutação é essa.

Para transmitir um número entre $1$ e $m$ requer transmissão $\log_2 m$bits de informação. Para transmitir uma permutação de$n$ elementos, portanto, requer $\log_2 n!$bits de informação. Pela aproximação de Stirling, isso acaba sendo$n \log_2 n + O(\hbox{low order})$ bits.

Uma operação de comparação binária descobre um pouco de informação. Daqui resulta que qualquer algoritmo de classificação que use apenas uma operação de comparação binária deve executar pelo menos$n \log_2 n + o(n \log n)$comparações. Se assumirmos que uma comparação leva uma quantidade constante de tempo, isso significa que a classificação deve levar pelo menos$\Omega(n \log n)$ Tempo.

Uma classificação radical poderia superar isso descobrindo mais de um bit de informações por consulta.

Um argumento semelhante mostra que a pesquisa binária é ideal. Você está tentando encontrar um número entre$1$ e $n$, o que significa descobrir $\log_2 n$bits de informação. Se sua operação de consulta retornar um pouco de informação, você precisará de pelo menos$\log_2 n$ consultas para encontrar um elemento.

É uma história semelhante com o uso do espaço. Suponha que você precise armazenar uma permutação na memória. Por um argumento idêntico, isso requer pelo menos$n \log_2 n + o(n \log n)$pedaços de armazenamento. Desde que você precisa$\log_2 n$ bits para armazenar um número inteiro entre $1$ e $n$, você basicamente não pode fazer nada melhor do que armazenar $n$ inteiros.

A classificação, de fato, foi comprovada levar pelo menos$O(n \log n)$tempo se a classificação for baseada em comparações. Para números inteiros de tamanho fixo, existem métodos mais rápidos (classificação de raiz).

No entanto, a classificação é um dos raros problemas em que isso foi feito. Em geral, não conhecemos limites inferiores para a complexidade de tempo da maioria dos problemas. Por exemplo, se sabemos que$O(2^n)$ foi um limite inferior para $NP$problemas completos, saberíamos que $P \neq NP$. Mas nenhum resultado foi provado, então$P$ vs $NP$ permanece um mistério.

Para problemas em geral, não existe um algoritmo capaz de representar um problema e retornar um limite inferior à sua complexidade de tempo. Isso ocorre porque o conjunto de tais complexidades seria um conjunto de índices: isto é, representa uma propriedade das linguagens (problemas), não dos algoritmos. Há um resultado chamado Teorema de Rice, que diz que esses conjuntos são indecidíveis.

Em geral, isso é possível, mas é crucial que você especifique o modelo de computação ao fazê-lo. Um exemplo clássico bem conhecido é o$\Omega(n \log n)$vinculado à classificação no modelo de árvore de decisão. Para contornar o limite inferior de classificação comprovado no modelo de árvore de decisão, você não deve realizar comparações.

Outro exemplo é o modelo da sonda celular . Além dos exemplos na Wikipedia, você pode ver, por exemplo, Fredman-Saks (STOC'89) . Este é um modelo forte; se você deseja ultrapassar um limite com um algoritmo, não deve acessar a memória.