Assintoticamente algoritmo ótimo - Asymptotically optimal algorithm
Em ciência da computação , um algoritmo é dito ser assintoticamente ótimo se, grosso modo, para grandes entradas realiza na pior das hipóteses um fator constante (independente do tamanho da entrada) pior do que o melhor algoritmo possível. É um termo comumente encontradas em pesquisa de ciência da computação, como resultado do uso generalizado da notação big-O .
Mais formalmente, um algoritmo é assintoticamente ótima em relação a um determinado recurso se o problema tem sido comprovada para exigir Ω (f (n)) desse recurso, e o algoritmo tenha sido comprovada a usar apenas O (f (n)).
Estas provas requerem um pressuposto de um determinado modelo de computação , isto é, certas restrições às operações permissível com os dados de entrada.
Como um exemplo simples, sabe-se que todos os tipos de comparação exigem pelo menos Ω ( n log n ) comparações na média e piores casos. Mergesort e heapsort são os tipos de comparação que executam O ( N log n comparações), de modo que eles são assintoticamente óptima neste sentido.
Se os dados de entrada têm algumas a priori propriedades que podem ser exploradas na construção de algoritmos, além de comparações, em seguida, algoritmos assintoticamente mais rápidas podem ser possível. Por exemplo, se sabe-se que os objectos N são inteiros a partir do intervalo [1, N], em seguida, eles podem ser classificados O (n) de tempo, por exemplo, pela espécie balde .
Uma consequência de um algoritmo sendo assintoticamente ideal é que, para as entradas de grande o suficiente, não há nenhum algoritmo pode superar-lo por mais do que um factor constante. Por esta razão, os algoritmos asymptotically ideais são muitas vezes vistos como o "fim da linha" na pesquisa, a consecução de um resultado que não pode ser dramaticamente melhorados. Por outro lado, se um algoritmo não é assintoticamente ideal, isto implica que como a entrada cresce em tamanho, o algoritmo executa cada vez pior do que o melhor algoritmo possível.
Na prática é útil para encontrar algoritmos que apresentam melhor desempenho, mesmo se eles não gostam de qualquer vantagem assintótica. Novos algoritmos podem também apresentam vantagens tais como um melhor desempenho nas estimativas específicas, diminuição da utilização dos recursos, ou ser mais simples para descrever e aplicar. Assim assintoticamente algoritmos óptimas não são sempre o "fim da linha".
Embora assintoticamente algoritmos melhores são os resultados teóricos importantes, um algoritmo assintoticamente ideal não pode ser usado em um número de situações práticas:
- Ele só supera mais métodos comumente usados para N para além da gama de tamanhos de entrada práticos, tais como entradas com mais bits do que poderiam caber em qualquer sistema de armazenamento de computador.
- É muito complexo, de modo que a dificuldade de compreender e implementá-la corretamente supera seu potencial benefício na faixa de entrada de tamanhos sob consideração.
- As entradas encontradas na prática queda em casos especiais que têm algoritmos mais eficientes ou que algoritmos heurísticos com maus momentos pior caso pode, no entanto, resolver de forma eficiente.
- Em computadores modernos, otimizações de hardware, como cache de memória e processamento paralelo pode ser "quebrado" por um algoritmo assintoticamente ótima (assumindo que a análise não tinha tomado essas otimizações de hardware em conta). Neste caso, poderia haver algoritmos sub-óptima que fazem melhor uso desses recursos e superam um algoritmo optimal em dados realistas.
Um exemplo de um algoritmo assintoticamente óptima não utilizado na prática é Bernard Chazelle algoritmo de tempo linear 's para triangulação de um polígono simples . Outra é a matriz redimensionável estrutura de dados publicado em "Arrays redimensionáveis em Optimal Tempo e Espaço", que pode indexar em tempo constante, mas em muitas máquinas acarreta uma pena prática pesado em comparação com a indexação de matriz comum.
definições formais
Formalmente, suponha que temos um teorema limite inferior mostrando que um problema requer Ω (f ( n tempo)) para resolver para uma instância (entrada) de tamanho n (ver big-O notação para a definição de Ω). Em seguida, um algoritmo que resolve o problema em O (f ( n )) tempo é dito ser assintoticamente óptima. Isto também pode ser expresso utilizando limites: suponhamos que b ( n ) é um ligado no tempo de funcionamento mais baixa, e um determinado algoritmo leva o tempo t ( n ). Em seguida, o algoritmo é assintoticamente ótima se:
Note-se que este limite, se existir, é sempre pelo menos um, tal como t ( n ) ≥ b ( n ).
Embora geralmente aplicado a eficiência de tempo, um algoritmo pode ser dito para usar o espaço assintoticamente óptima, bits aleatórios, número de processadores, ou qualquer outro recurso vulgarmente medidos usando a notação big-O.
Às vezes suposições vagas ou implícitas pode torná-lo claro se um algoritmo é assintoticamente ideal. Por exemplo, um teorema limite inferior poderia supor um determinado máquina abstrata modelo, como no caso da ordenação por comparação, ou uma organização particular de memória. Ao violar estes pressupostos, um novo algoritmo poderia potencialmente asymptotically superar a dos algoritmos "asymptotically ótimas" limite inferior e.
Acelerar
A inexistência de um algoritmo assintoticamente ideal é chamado de aceleração. Teorema da aceleração de Blum mostra que existem problemas artificialmente construídos com aceleração. No entanto, é um problema em aberto se muitos dos algoritmos mais conhecidos hoje são assintoticamente ótima ou não. Por exemplo, há um O ( n α ( n )) algoritmo para encontrar árvore de extensão mínima , onde α ( N ) é o inverso muito lentamente crescente da função de Ackermann , mas o melhor conhecido limite inferior é o Ω trivial ( n ) . Se este algoritmo é assintoticamente ideal é desconhecida, e seria susceptível de ser saudado como um resultado significativo se fosse resolvido de qualquer maneira. Fundidor e Winograd (1982) mostrou que a multiplicação de matrizes tem uma forma fraca de velocidade-se entre uma classe restrita de algoritmos (identidades bilineares Strassen do tipo com lambda-cálculo).