Por que estudar a teoria da complexidade?

Question

Eu sou um amador no estudo dos algoritmos. Por um tempo eu tive uma pergunta em chamas, por que estudamos a teoria da complexidade na ciência da computação? A razão pela qual eu faço é porque os algoritmos com melhor complexidade assintótico nem sempre são mais rápidos para fins práticos, na verdade eles podem ser absurdamente mais devagar. Por que não desenvolver uma teoria que melhor se adapte às necessidades práticas da pesquisa e da indústria científica?

Como exemplo, sabe-se que o desenvolvimento de um algoritmo para determinar um jogo de xadrez perfeito pode ser feito em $ O (1) $ , como o número de Jogos de xadrez em uma grade de 8 × 8 são limitados de cima. No entanto, ouvi que esse algoritmo levaria mais do que a idade do universo para terminar. Isso implora a pergunta, por que a teoria da complexidade? Parece-me que o campo é fundamentalmente falho, e os cientistas da computação devem estar usando uma melhor abordagem para o estudo dos algoritmos.

(Nota: Minhas sinceras desculpas aos pesquisadores no campo. ☻)

Answer 1

Esta não é uma pergunta simples, e você não deve esperar uma resposta simples. Há uma gama de perguntas semelhantes neste espaço: por que estudamos o tempo de execução assintótico? Por que usamos a análise de tempo de execução assintótica para analisar algoritmos? Por que estudamos a teoria da complexidade? Cada um desses tem várias respostas; Não há apenas uma única razão pela qual fazemos, e pessoas diferentes podem ter diferentes razões.

A análise de tempo de execução assintótica tem vantagens e desvantagens. Você identificou com precisão uma das desvantagens: Um bom tempo de funcionamento assintótico não garante bom tempo de execução na prática. Mas se você se concentrar apenas em uma única vantagem ou desvantagem, você não vai conseguir a imagem completa dos pontos fortes e fraquezas desse estilo de análise. Algumas das vantagens são que a análise é relativamente tratável, não é específica para uma arquitetura específica, fornece informações úteis sobre escalabilidade e pelo menos parte do tempo que tem poder preditivo útil na identificação de gargalos algorítmicos. Por exemplo, a diferença entre uma $ O (n ^ 2) $ algoritmo de tempo e uma $ o (n \ log n ) $ Algoritmo de tempo muitas vezes pode ser significativo, mesmo que estamos ignorando os fatores constantes. Algumas das desvantagens são que os fatores constantes podem ser importantes, efeitos de hierarquia de cache e memória podem ser muito importantes ainda são ignorados pela análise de tempo de execução assintótica, e (como qualquer métrica) otimizando exclusivamente para o tempo de funcionamento assintótico pode levar a resultados absurdos de pouco prático Utilitário (ver algoritmos galácticos e a lei de Goodhart ).

Eu acho que também é útil examinar a alternativa. Encorajo-vos a explorar a alternativa à análise de tempo de execução assintómica e trabalhar através do que você proporia em seu lugar. Se você não tentar criar uma proposta concreta, é fácil supor que não pode ser tão difícil encontrar algo melhor ... mas quando você for forçado a se comprometer com algo específico, você pode descobrir que é mais desafiador do que você previu. Por exemplo, encorajo-vos a se familiarizar com a análise de Knuts do algoritmo de tempo de execução em Mix Série Taocp. Lá ele faz análise de tempo de corrida concreta, sem assintótica, levando em conta os fatores constantes. Se você se forçar a trabalhar através dos detalhes, descobrirá rapidamente as desvantagens disso: é super-tedioso, muito específico para uma arquitetura de computador em particular, e muitas vezes não muito mais esclarecedor.

Poderíamos discutir igualmente cada um dos outros tópicos - por que ou por que não estudar a teoria da complexidade - e descobriria que eles também têm nuances.

Eu também quero destacar para você que a comunidade teoria e algoritmos é uma ampla, com uma gama de diferentes estilos de trabalho. Você parece reunir tudo junto em uma pilha, mas há um espectro de trabalho: alguns deles são super-teóricos e distantes da prática, alguns deles é altamente prático e motivado por problemas concretos e podem ter impacto imediato, e Há uma variedade de trabalho em vários pontos entre esses extremos. Eu acho que é importante entender que há algum trabalho na comunidade teoria que é de grande relevância prática ou teve grande impacto, assim como há trabalho muito mais teórico e não motivado pelo impacto a curto prazo.

Desde que você pediu estruturas teóricas que estão focadas na reunião das necessidades do setor, você também pode estar interessado no Palavra ram modelo, cache-algoritmos de cache e o Memória externa paralela modelo.

Eu encorajo fortemente você a ler os seguintes recursos, pois eles estão intimamente relacionados à sua pergunta: Por que o tempo polinomial é chamado " eficiente "? , Explicando a relevância da complexidade assintótica de algoritmos para a prática de projetar algoritmos , Justificação Para negligenciar fatores constantes em Big O .