Explicando a relevância da complexidade assintótica de algoritmos para a prática de projetar algoritmos

Em algoritmos e complexidade, focamos na complexidade assintótica de algoritmos, ou seja, a quantidade de recursos que um algoritmo usa à medida que o tamanho da entrada chega ao infinito.

Na prática, o que é necessário é um algoritmo que funcione rapidamente em um número finito (embora possivelmente muito grande) de instâncias.

Um algoritmo que funciona bem na prática no número finito de instâncias em que estamos interessados ​​não precisa ter boa complexidade assintótica (o bom desempenho em um número finito de instâncias não implica nada em relação à complexidade assintótica). Da mesma forma, um algoritmo com boa complexidade assintótica pode não funcionar bem na prática no número finito de instâncias em que estamos interessados ​​(por exemplo, devido a constantes grandes).

Por que usamos complexidade assintótica? Como essas análises assintóticas se relacionam com o design de algoritmos na prática?

A questão interessante é: qual é a alternativa? O único outro método que conheço é o teste / benchmarking. Nós programamos os algoritmos, permitimos que eles executem (uma amostra representativa) do conjunto de entradas finitas e comparemos os resultados. Existem alguns problemas com isso.

• Os resultados não são gerais em termos de máquinas. Execute seu benchmark em outro computador e obterá resultados diferentes com certeza, quantitativamente e talvez até qualitativamente.
• Os resultados não são gerais em termos de linguagens de programação. Idiomas diferentes podem causar resultados muito diferentes.
• Os resultados não são gerais em termos de detalhes de implementação. Você literalmente compara programas , não algoritmos; pequenas mudanças na implementação podem causar enormes diferenças no desempenho.
• Se o pior caso for raro, uma amostra de entrada aleatória pode não conter uma instância incorreta. Isso é justo se você estiver preocupado com o desempenho médio dos casos, mas alguns ambientes exigem garantias dos piores casos.
• Na prática, os conjuntos de entradas mudam. Normalmente, as entradas aumentam ao longo do tempo. Se você não repetir sua referência a cada seis meses (sim, alguns dados crescem tão rápido), seus resultados serão inúteis em breve¹.

Dito isto, ignorar todos os tipos de efeitos e constantes na análise é típico, mas pode ser chamado de preguiçoso (com relação à prática). Serve para comparar idéias algorítmicas mais do que para identificar o desempenho de uma determinada implementação (mesmo com pseudocódigo). É sabido à comunidade que isso é grosseiro e que é necessário um olhar mais atento; por exemplo, o Quicksort é menos eficiente que a classificação de inserção para (muito) pequenas entradas. Para ser justo, análise mais precisa é geralmente difícil ².

Outra justificativa a posteriori para o ponto de vista abstrato e formal é que, nesse nível, as coisas costumam ser mais claras. Assim, décadas de estudo teórico trouxeram uma série de idéias algorítmicas e estruturas de dados que são úteis na prática. O algoritmo teoricamente ideal nem sempre é o que você deseja usar na prática - há outras considerações, mas o desempenho a ser feito; acho que os montes de Fibonacci - e esse rótulo pode até não ser único. É difícil para um programador típico preocupado em otimizar expressões aritméticas ter uma nova idéia nesse nível (para não dizer que isso não acontece); ela pode (e deve) realizar essas otimizações na idéia assimilada.

Existem ferramentas formais e teóricas para fechar a lacuna e praticar até certo ponto. Exemplos são

• considerando a hierarquia de memória (e outras E / S),
• analisar o caso médio (quando apropriado),
• analisar o número de declarações individuais (em vez de medidas abstratas de custo) e
• determinação de fatores constantes.

Por exemplo, Knuth é conhecido por contar literalmente o número de instruções diferentes (para uma determinada implementação em um determinado modelo), permitindo a comparação precisa de algoritmos. Essa abordagem é impossível em um nível abstrato e difícil de fazer em modelos mais complexos (pense em Java). Veja [4] para um exemplo moderno.

Sempre haverá uma lacuna entre teoria e prática. No momento, estamos trabalhando em uma ferramenta³ com o objetivo de combinar o melhor dos dois mundos para fazer previsões sólidas de custos algorítmicos e tempo de execução (em média), mas até agora não fomos capazes de eliminar os cenários em que um algoritmo é mais alto custos, mas menor tempo de execução (em algumas máquinas) do que um equivalente (embora possamos detectar isso e dar suporte à descoberta do motivo).

Eu recomendo que os profissionais usem a teoria para filtrar o espaço dos algoritmos antes de executar benchmarks:

if ( input size forever bounded? ) {
  benchmark available implementations, choose best
  schedule new benchmarks for when machine changes
}
else {
  benchmark implementations of all asymptotically good algorithms
  choose the best
  schedule new benchmarks for when machine changes or inputs grow significantly
}

1. Pode haver mudanças malucas no desempenho absoluto e relativo quando o número de falhas de cache aumenta, o que normalmente acontece quando as entradas aumentam, mas a máquina permanece a mesma.
2. Como em, os principais pesquisadores no campo não são capazes de fazê-lo.
3. Encontre a ferramenta aqui . Um exemplo de uso foi publicado no Dual Pivot Quicksort Engineering Java 7, usando MaLiJAn por S. Wild et al. (2012) [ pré-impressão ]
4. Análise Média de Casos do Quicksort Dual Pivot do Java 7 por S. Wild e M. Nebel (2012) - [ pré-impressão ]

Suponho que essa questão surge do ensino de um curso que inclui análise assintótica. Existem várias respostas possíveis para explicar por que esse material é ensinado nas aulas introdutórias:

• A análise assintótica é uma abstração matemática que se rende à análise. Como (sem dúvida) matemáticos, queremos ser capazes de analisar algoritmos, e eles só podem domar sua complexidade usando análise assintótica.

• A avaliação do desempenho assintótico de um algoritmo aponta alguns princípios úteis na prática: por exemplo, concentre-se na parte do código que leva a maior parte do tempo e desconte qualquer parte do código que leva uma parte do tempo assintoticamente desprezível .

• Algumas das técnicas de análise assintótica são úteis. Estou me referindo aqui principalmente ao chamado "teorema mestre", que em muitas circunstâncias é uma boa descrição da realidade.

• Há também uma razão histórica: quando as pessoas começaram a analisar algoritmos, pensaram seriamente que a complexidade assintótica reflete o uso prático. No entanto, eventualmente eles se mostraram errados. O mesmo aconteceu com P como a classe de problemas eficientemente solucionáveis, e NP como a classe de problemas intratáveis, ambos enganosos na prática.

Pessoalmente, acho que a análise assintótica é uma parte razoável do currículo. Partes mais questionáveis ​​incluem a teoria formal da linguagem e a teoria da complexidade (qualquer coisa que tenha a ver com uma máquina de Turing). Algumas pessoas argumentam que, embora esses assuntos não sejam úteis para o potencial programador em si, eles instilam nela um certo pensamento mental necessário para ser um bom praticante. Outros argumentam que a teoria às vezes influencia a prática, e esses casos raros são suficientes para justificar o ensino desses assuntos bastante misteriosos ao público em geral da ciência da computação. Eu preferiria que eles aprendessem história ou literatura, ou qualquer outro assunto em que realmente estejam interessados; ambos são tão relevantes para suas perspectivas de trabalho futuro e mais importantes para eles quanto os seres humanos.

Há dois motivos sérios para usar a análise assintótica dos tempos de execução:

• $n$

• para permitir a rastreabilidade matemática. Casos em que é possível encontrar expressões exatas para a contagem de operações são excepcionais. O estudo de assintóticos abre mais possibilidades (como aproximações assintóticas de funções complicadas são úteis).

E existem muitos outros (como independência da máquina, significado, comparabilidade ...).

Conforme observado na resposta de Raphael, o cálculo exato do pior tempo de execução pode ser muito difícil. A computação exata também pode ser desnecessária, pois o modelo de RAM já introduz aproximações. Por exemplo, todas as operações levam tempo igual? Implementações específicas (hardware, otimizações) podem acelerar um algoritmo por fatores constantes. Queremos entender a eficácia de um algoritmo independente desses fatores. Essa é uma grande motivação para o uso da análise assintótica.

Porque os assintóticos são "simples" (bem, mais simples do que fazer a análise exata para casos finitos, enfim).

Compare, por exemplo, a enciclopédica "The Art of Computer Programming", de Knuth, que faz uma análise detalhada de todos os algoritmos importantes (e muitos não tão importantes) com a análise de regra geral que é suficiente para obter uma estimativa assintótica ( ou apenas um limite), conforme praticado na maioria dos livros de "algoritmos".

Você certamente está certo. Se o problema for importante o suficiente, uma análise no estilo Knuth (ou talvez um pouco menos detalhada) pode ser justificada. Em muitos casos, basta uma dica da complexidade assintótica (talvez média com dispersão) ajustada aos dados experimentais. Na maioria dos casos , para fazer uma classificação aproximada dos algoritmos concorrentes, como uma primeira rodada de eliminação de ervas daninhas comparando assintóticos pode ser suficientemente preciso. E se não houver candidatos, obter as más notícias do custo exato em pequenos detalhes é apenas masoquismo.

Aqui, por análise assintótica, presumo que entendemos o comportamento do algoritmo à medida que o tamanho da entrada vai para o infinito.

A razão pela qual usamos a análise assintótica é porque é útil na previsão do comportamento dos algoritmos na prática . As previsões nos permitem tomar decisões, por exemplo, quando temos algoritmos diferentes para um problema, qual deles devemos usar? (Ser útil não significa que está sempre correto.)

A mesma pergunta pode ser feita sobre qualquer modelo simplificado do mundo real. Por que usamos modelos matemáticos simplificados do mundo real?

Pense em física. A física newtoniana clássica não é tão boa quanto a física relativista na previsão do mundo real. Mas é um modelo suficientemente bom para a construção de carros, arranha-céus, submarinos, aviões, pontes, etc. Há casos em que não é bom o suficiente, por exemplo, se queremos construir um satélite ou enviar uma sonda espacial para Plutão ou prever o movimento de objetos celestes maciços como estrelas e planetas ou objetos de velocidade muito alta como elétrons. É importante saber quais são os limites de um modelo.

1. Normalmente, é uma aproximação suficientemente boa do mundo real. Na prática, vemos frequentemente que um algoritmo com melhor análise assintótica funciona melhor na prática. Raramente é o caso de um algoritmo ter melhor comportamento assintótico. Portanto, se as entradas podem ser grandes o suficiente, normalmente podemos confiar na análise assintótica como primeira previsão do comportamento dos algoritmos. Não é assim se sabemos que as entradas serão pequenas. Dependendo do desempenho que desejamos, podemos precisar fazer uma análise mais cuidadosa, por exemplo, se tivermos informações sobre a distribuição das entradas fornecidas pelo algoritmo, podemos fazer uma análise mais cuidadosa para alcançar os objetivos que temos (por exemplo, rápido na 99) % de insumos). O ponto é que, como primeiro passo, a análise assintótica é um bom ponto de partida. Na prática, também devemos fazer testes de desempenho, mas tenha em mente que também tem seus próprios problemas.

2. $A$$A$$A$tem melhor complexidade assintótica. O que nenhum deles é melhor que o outro em todas as entradas? Então fica mais complicado e depende do que nos interessa. Preocupamo-nos com entradas grandes ou pequenas? Se nos preocupamos com entradas grandes, não é comum que um algoritmo tenha melhor complexidade assintótica, mas se comporte pior nas entradas grandes que importamos. Se nos preocupamos mais com pequenos insumos, a análise assintótica pode não ser tão útil. Devemos comparar o tempo de execução dos algoritmos nas entradas que importamos. Na prática, para tarefas complicadas com requisitos complicados, a análise assintótica pode não ser tão útil. Para problemas básicos simples que os livros didáticos de algoritmo cobrem, é bastante útil.

Em resumo, a complexidade assintótica é relativamente fácil de calcular a aproximação da complexidade real dos algoritmos para tarefas básicas simples (problemas em um livro de algoritmos). À medida que construímos programas mais complicados, os requisitos de desempenho mudam e se tornam mais complicados, e a análise assintótica pode não ser tão útil.

É bom comparar a análise assintótica com outras abordagens para prever o desempenho dos algoritmos e compará-los. Uma abordagem comum são os testes de desempenho contra entradas aleatórias ou de referência. É comum quando o cálculo da complexidade assintótica é difícil ou inviável, por exemplo, quando estamos usando heurísticas, como, por exemplo, a solução SAT. Outro caso é quando os requisitos são mais complicados, por exemplo, quando o desempenho de um programa depende de fatores externos e nosso objetivo pode ser algo que termine sob alguns limites de tempo fixos (por exemplo, pense em atualizar a interface mostrada ao usuário) em 99% dos entradas.

Mas lembre-se de que a análise de desempenho também apresenta seus problemas. Ele não fornece aos donatários matemáticos o desempenho com menos desempenho; na verdade, executamos o teste de desempenho em todas as entradas que serão fornecidas ao algoritmo (geralmente inviável em termos computacionais) (e geralmente não é possível decidir que algumas entradas nunca serão fornecidas). Se testar em contra uma amostra aleatória ou uma referência estamos implicitamente assumindo alguma regularidade sobre o desempenho dos algoritmos, ou seja, o algoritmo irá realizar semelhante em outras entradas que não faziam parte do teste de desempenho.

O segundo problema dos testes de desempenho é que eles dependem do ambiente de teste. Ou seja, o desempenho de um programa não é determinado apenas pelas entradas, mas por fatores externos (por exemplo, tipo de máquina, sistema operacional, eficiência do algoritmo codificado, utilização da CPU, tempos de acesso à memória etc.), alguns dos quais podem variar entre diferentes execuções de o teste na mesma máquina. Novamente, aqui estamos assumindo que os ambientes específicos em que o teste de desempenho é realizado são semelhantes ao ambiente real, a menos que façamos os testes de desempenho em todos os ambientes nos quais podemos executar o programa (e como podemos prever em quais máquinas alguém pode executar uma classificação algoritmo ativado em 10 anos?).

$\Theta(n \lg n)$$\Theta(n^2)$$\Theta(\lg n)$$O(n)$

$O(n^2)$$O(n \log n)$$O(n^2)$ para terminar em comparação com o quicksort.

agora imagine essa espera repetida no código quantas vezes o código for chamado. como quantificamos / justificamos matematicamente essa aparente superioridade do algoritmo quicksort? (ou seja, o nome é realmente justificado ou é apenas um slogan de marketing?) por meio de medições de complexidade assintótica. fica-se olhando subjetivamente para as animações, sentindo que o tipo de bolhas é de alguma forma um algoritmo mais fraco e a análise da complexidade assintótica pode provar isso quantitativamente. mas observe que a análise de complexidade assintótica é apenas uma ferramenta no conjunto de ferramentas para analisar algoritmos e nem sempre é a última.

e vale a pena examinar também o código lado a lado. O bubblesort parece ser conceitualmente mais simples e não usa recursão. O quicksort não é tão imediatamente compreendido, especialmente pelo princípio de pivô "mediana de 3". O bubblesort pode ser implementado apenas em loops sem uma sub-rotina, enquanto o quicksort normalmente pode ter pelo menos uma sub-rotina. isso mostra o padrão de que mais sofisticação de código às vezes pode melhorar a complexidade assintótica à custa da simplicidade do código. Às vezes, há um tradeoff extremo semelhante ao conceito de retornos marginais decrescentes (orig da economia), em que grandes quantidades de complexidade de código [exigindo documentos inteiros cheios de moedas e provas para justificar] compram apenas pequenas melhorias na complexidade assintótica. isso aparece como um exemplo esp commultiplicação de matrizes e pode até ser representado graficamente .