O que são complexidade essencial e acidental?

Vamos reduzir o escopo da resposta à complexidade essencial e acidental no domínio da engenharia de software, porque é isso que a tag “Ciência da computação” implica.

O que é uma complexidade de um software?

Mesmo que a complexidade do termo possa ser interpretada amplamente em geral, no contexto da engenharia / programação de software, ele é referido principalmente como combinação das duas propriedades a seguir:

  1. Capacidade de entender e manter um pedaço de código ou parte do sistema de software após a criação.
  2. Complexidade do algoritmo Big-O [1] – é a capacidade de um algoritmo escalar enquanto o tamanho da entrada está aumentando. Ele se aplica principalmente ao tempo de processamento, mas também é usado para o espaço usado (por exemplo, na memória ou no disco) por um algoritmo.

Expectativa de complexidade

Muitas vezes, ao analisar rapidamente o código complexo, um profissional experiente pode dizer se a complexidade que está observando é essencial ou acidental. Em palavras simples, sem conhecer detalhes exatos da implementação, ele pode estimar se o mesmo problema pode ser resolvido com um pedaço de código menos complexo ou não.

Causas típicas:

  1. Quando um desenvolvedor não está familiarizado com toda a gama de recursos da estrutura ou tecnologia usada, ele geralmente tende a usar uma técnica e a reutilizá-la para todos os fins, mesmo que haja alternativas melhores (síndrome do martelo e da unha [2]). Provavelmente o mais problemático é o desconhecimento de algoritmos e estruturas de dados conhecidos. Por exemplo, muitos desenvolvedores de Java / c # usam demais a estrutura de dados da Lista, mesmo que um iterador, Stack ou Array possa ser suficiente. Um engenheiro experiente notará rapidamente que não há operações de remoção; portanto, a lista é obviamente muito grande.
  2. Um desenvolvedor tende a generalizar demais uma tarefa . Um amigo meu pediu a um programador que escrevesse um programa para imprimir os nomes dos 10 principais clientes mais rentáveis. O programador criou um aplicativo com interface do usuário complexa, oferecendo inúmeras possibilidades de consulta de dados do cliente. Nós programadores geralmente esquecemos de fazer o mínimo necessário, tentando prever possíveis requisitos futuros.
  3. Uma vez escrito e funcionando, um pedaço de código pode ser otimizado e simplificado para reduzir a complexidade. No entanto, muitos programadores tendem a não tocar em um sistema em execução devido à falta de tempo e testes . A situação fica ainda pior quando os bugs são corrigidos sob pressão de tempo e sem a realização de testes. Os desenvolvedores tentam fazer alterações com o menor impacto possível, sem revisitar e otimizar todo o código. Como resultado, a complexidade cresce desnecessariamente ao longo do tempo.

Notas de rodapé

[1] Guia para iniciantes da notação Big O

[2] Lei do instrumento – Wikipedia

Os termos Complexidade essencial e Complexidade acidental são cunhados por Ben Moseley e Peter Marks em seu artigo Out of the Tarpit [1]. Seu significado nas palavras Essencial e Acidental é retirado de No Silver Bullet, de Fred Brook [2].

Para resumir, os termos são definidos da seguinte maneira:

  • Complexidade essencial é a complexidade inerente ao problema. É uma complexidade relacionada ao problema e não pode ser removida.
  • Complexidade acidental é complexidade não relacionada ao problema. Ben Mosely e Peter Marks descrevem isso como um “acidente”. É complexidade por culpa do desenvolvedor e simplesmente está lá.

O que é complexidade de software?

Moseley, Marks e Brooks não definem muito bem a complexidade. Eles parecem concordar apenas que complexidade é algo que dificulta o entendimento do software e o programa correto.

Para a definição de complexidade, eu realmente gosto da definição dada por Rich Hickey em Simple Made Easy [3]. Complexidade é basicamente emaranhado de componentes, idéias etc. A meu ver, as definições de complexidade essencial e acidental se tornam:

  • Complexidade essencial é o entrelaçamento / combinação de componentes / idéias no software necessário para resolver o problema em questão. Não pode ser evitado.
  • Complexidade acidental é o entrelaçamento de componentes / idéias que não é necessário para resolver o problema. Essa complexidade é acidental porque alguém provavelmente não pensou muito antes de amarrar as coisas desnecessariamente. Como resultado, o software é mais difícil de entender do que deveria ser.

Notas de rodapé

[1] http://shaffner.us/cs/papers/tar…

[2] http://worrydream.com/refs/Brook…

[3] Simples e Fácil

Complexidade acidental são complicações das quais você pode se livrar com um design melhor. Complexidade essencial são complicações com as quais você está preso.

Se bem me lembro, Fred Brooks cunhou essa terminologia no The Mythical Man-Month.

Mais uma vez, se bem me lembro (depois de ler o livro há 20 anos), a complexidade essencial é a complexidade inerente ao problema, enquanto a complexidade acidental é a complexidade introduzida como parte da solução.