O que é um algoritmo eficiente?

Do ponto de vista do comportamento assintótico, o que é considerado um algoritmo "eficiente"? Qual é o padrão / motivo para desenhar a linha nesse ponto? Pessoalmente, eu pensaria que qualquer coisa que eu possa chamar ingenuamente de "sub-polinomial", tal que como n 1 + ϵ , seja eficiente e qualquer coisa que seja Ω ( n 2 ) seria "ineficiente". No entanto, ouvi dizer que qualquer coisa que seja de qualquer ordem polinomial é chamada de eficiente. Qual o raciocínio?$f(n) = o(n^2)$$n^{1+\epsilon}$$\Omega(n^2)$

Isso depende do contexto. Na ciência da computação teórica, geralmente todo algoritmo de tempo polinomial é considerado 'eficiente'. Em algoritmos de aproximação, por exemplo, um tempo de execução de seria considerado eficiente, mesmo que na prática não seja utilizável para qualquer valor razoável deϵ. Um algoritmo para SAT que é executado emn 2 100 seria uma inovação incrível.$n^{1/\epsilon^{1/\epsilon}}$$\epsilon$$n^{2^{100}}$

Em algoritmos clássicos, ou seja, algoritmos dos anos 80 e anteriores, tempos de execução abaixo ou mais (pense em multiplicação de matrizes, correspondência mínima de custos, fluxos, programação linear) são considerados eficientes. Eles ainda são considerados eficientes pela maioria das pessoas, eu diria. Obviamente, umalgoritmo n 2 não é considerado eficiente se um n log $n^3$$n^2$$n\log n$ algoritmo é conhecida, como por triagem por exemplo.

Atualmente, existe uma tendência para algoritmos sublineares ou algoritmos de streaming capazes de lidar com terabytes de dados. Tente usar a multiplicação de matrizes para calcular a classificação de todas as páginas no índice do Google. Isso não vai funcionar.

É claro que, embora certamente seja útil, o tempo de execução assintótico de um algoritmo não conta toda a história. Existem algoritmos com bom tempo de execução assintótico, mas constantes tão grandes que não podem ser usadas com eficácia. Sempre. Lipton os chama de algoritmos galácticos . Robert Sedgewick até afirma que os piores casos são "geralmente inúteis para previsão, geralmente inúteis para garantias" e "a análise do pior caso é inútil para prever desempenho" em sua palestra Colocando a ciência de volta na ciência da computação .

Meus 2 centavos do ponto de vista dos algoritmos distribuídos: Ao analisar redes de grande escala (P2P, redes sociais, etc.), um algoritmo distribuído é considerado eficiente se o tempo de execução for para alguma constante c > 0 e o algoritmo usa mensagens de O ( log n ) bits. Observe que o requisito de tamanho de mensagem geralmente recebe ainda mais importância do que o tempo de execução, especialmente para problemas "globais" que têm um limite inferior maior no tempo de execução, por exemplo, MST distribuído.$O(\log^c n)$$c>0$ $O(\log n)$

O raciocínio por trás disso é que, da perspectiva do comportamento assintótico, uma taxa de crescimento polinomial é trivialmente menor que uma taxa de crescimento super-polinomial. Na prática, um algoritmo de tempo polinomial é executado muito mais rápido que um algoritmo de tempo super-polinomial quando o tamanho da entrada aumenta.

Obviamente, ninguém diria que um algoritmo com complexidade polinomial de, por exemplo, é "eficiente", mas a maioria dos algoritmos raramente excede a complexidade de O ( n 5$O(n^{2000})$$O(n^5)$ .

$O(n^2)$

Em teoria, um algoritmo é considerado eficiente se o seu pior tempo de execução for limitado por um polinômio em seu comprimento de entrada. O raciocínio é que os polinômios têm boas propriedades de fechamento. Adicionar, multiplicar, compor polinômios são operações que produzem polinômios e são boas se você estiver reduzindo problemas entre si.

É claro que a diferença entre polinomial e exponencial fica muito grande à medida que o comprimento da entrada aumenta, portanto os algoritmos de tempo polinomial são muito melhores. Na prática, um algoritmo de tempo polinomial pode levar muito tempo antes do término, mas pode ser que seja um algoritmo ideal (o melhor possível); nesse caso, eu diria que é eficiente.

$n^3$$n^2$