Por que estudar a teoria da complexidade?
Sou um amador no estudo de algoritmos. Por um tempo, tive uma pergunta candente: por que estudamos a teoria da complexidade na ciência da computação? A razão de eu perguntar é porque algoritmos com melhor complexidade assintótica nem sempre são mais rápidos para fins práticos; na verdade, eles podem ser absurdamente mais lentos. Por que não desenvolver uma teoria que melhor se adapte às necessidades práticas da pesquisa científica e da indústria?
Como exemplo, sabe-se que o desenvolvimento de um algoritmo para determinar um jogo de xadrez perfeito pode ser feito em $O(1)$, já que o número de jogos de xadrez legais em uma grade 8 × 8 é limitado a partir de cima. No entanto, ouvi dizer que esse algoritmo levaria mais tempo do que a idade do universo para terminar. Isso levanta a questão: por que a teoria da complexidade? Parece-me que o campo é fundamentalmente falho e os cientistas da computação deveriam estar usando uma abordagem melhor para o estudo de algoritmos.
(Nota: Minhas sinceras desculpas aos pesquisadores da área. ☻)
Respostas
Esta não é uma pergunta simples, e você não deve esperar uma resposta simples. Há uma série de questões semelhantes neste espaço: por que estudamos o tempo de corrida assintótico? por que usamos análise de tempo de execução assintótica para analisar algoritmos? por que estudamos a teoria da complexidade? Cada um deles tem várias respostas; não há apenas um único motivo pelo qual fazemos isso, e diferentes pessoas podem ter diferentes motivos.
A análise assintótica do tempo de execução tem vantagens e desvantagens. Você identificou com precisão uma das desvantagens: um bom tempo de execução assintótico não garante um bom tempo de execução na prática. Mas se você se concentrar em apenas uma única vantagem ou desvantagem, não obterá o quadro completo dos pontos fortes e fracos desse estilo de análise. Algumas das vantagens são que a análise é relativamente tratável, não é específica para uma arquitetura particular, fornece informações úteis sobre escalabilidade e, pelo menos algumas vezes, tem poder preditivo útil na identificação de gargalos algorítmicos. Por exemplo, a diferença entre um$O(n^2)$ algoritmo de tempo e um $O(n \log n)$O algoritmo de tempo pode muitas vezes ser significativo, mesmo se estivermos ignorando os fatores constantes. Algumas das desvantagens são que fatores constantes podem ser importantes, efeitos de hierarquia de cache e memória podem ser muito importantes, mas são ignorados pela análise de tempo de execução assintótica e (como qualquer métrica) otimizar apenas para tempo de execução assintótico pode levar a resultados absurdos de pouco prático utilitário (ver algoritmos galácticos e a lei de Goodhart ).
Acho que também é útil examinar a alternativa. Eu o encorajo a explorar a alternativa para a análise assintótica do tempo de execução e trabalhar com o que você proporá em seu lugar. Se você não tentar apresentar uma proposta concreta, é fácil presumir que não pode ser tão difícil encontrar algo melhor ... mas quando você é forçado a se comprometer com algo específico, você pode descobrir que é mais desafiador do que você esperava. Por exemplo, encorajo você a se familiarizar com a análise de Knuth sobre o tempo de execução do algoritmo no MIX em sua série TAOCP. Lá ele faz análises de tempo de execução concretas, sem assintóticas, levando em consideração os fatores constantes. Se você se forçar a trabalhar nos detalhes disso, descobrirá rapidamente as desvantagens disso: é tedioso, muito específico para uma arquitetura de computador em particular e, freqüentemente, não é muito mais esclarecedor.
Poderíamos discutir da mesma forma cada um dos outros tópicos - por exemplo, por que ou não estudar a teoria da complexidade - e você descobriria que eles também têm nuances.
Também quero destacar para você que a comunidade de teoria e algoritmos é ampla, com uma variedade de estilos de trabalho diferentes. Você parece estar amontoando tudo em uma pilha, mas há um espectro de trabalho: alguns deles são superteóricos e muito distantes da prática, outros são altamente práticos e motivados por problemas concretos e podem ter impacto imediato, e há uma gama de trabalho em vários pontos entre esses extremos. Acho que é importante entender que há alguns trabalhos na comunidade teórica que são de grande relevância prática ou tiveram grande impacto, assim como há trabalhos muito mais teóricos e não motivados por impacto de curto prazo.
Como você solicitou estruturas teóricas voltadas para atender às necessidades da indústria, você também pode se interessar pelo modelo Word RAM , algoritmos esquecidos do cache e o modelo de memória externa paralela .
Recomendo fortemente que você leia os seguintes recursos, pois eles estão intimamente relacionados à sua pergunta: Por que o tempo polinomial é chamado de "eficiente"? , Explicando a relevância da complexidade assintótica de algoritmos para a prática de algoritmos de concepção , Justificação por negligenciar fatores constantes na Big O .