16

Em relação a complexidade de algoritmos, observei que existem diversas citações sobre complexidade ciclomática. O que é complexidade ciclomática? Em qual situação é importante analisar essa complexidade?

4
  • 2
    Veja na wikipedia ou na wikipedia em inglês. Commented 29/03/2017 às 17:01
  • @VictorStafusa minha avó dizia que o wikipedia qualquer pessoa pode colocar qualquer coisa. Pensando nisso, eu prefiro saber daqui dos auto qualificados usuários do nosso SOpt; É quase que óbvio que a maioria das perguntas não só sobre terminologia tem lá no wikipedia, porque tem que ter aqui então? A tag é inútil?
    – viana
    Commented 29/03/2017 às 17:06
  • 1
    Não é nada disso. É verdade que qualquer um pode editar na wikipedia, mas isso não a desmerece, ainda assim o conteúdo de lá é normalmente (mas nem sempre) muito bom (assim como ocorre aqui). Ocorre que não tenho tempo para te dar uma resposta completa e detalhada (quem tiver, que siga em frente e escreva uma), mas a wikipedia já te dá um caminho e se você (ou outra pessoa) tiver com pressa para saber, dá para dar uma olhada lá. Além disso, isso também serve para definir um ponto de referência, qualquer resposta por aqui que seja inferior ao que está lá deveria ser melhorada. Commented 29/03/2017 às 17:10
  • @VictorStafusa isso é fato, as vezes as respostas aceitas aqui são bem inferiores. Mas a minha intenção é que fique registrado também aqui no SO, para também futuras referências.
    – viana
    Commented 29/03/2017 às 17:29

2 Respostas 2

18

É uma medida de complexidade de um algoritmo onde é considerado os caminhos independentes que o algoritmo pode tomar. Quanto maior a complexidade ciclomática mais difícil de acompanhar o código, de dar manutenção, testar e fazer cobertura total.

A complexidade ciclomática aumenta sempre que existe um branch, mas algumas formas de branch podem gerar caminhos mais difíceis de acompanhar do que outros. Quanto mais linear, mais fácil é acompanhar o código.

Uma saída da função não deixa de ser um branch e conta para aumentar a complexidade ciclomática, portanto não existe função de CC 0.

Por isso usar vários return ou eventualmente o uso do goto pode aumentar ou diminuir a complexidade ciclomática dependendo de como forem usados, ainda que possa prejudicar outro aspecto.

Funções grandes tendem a ter maior complexidade ciclomática. É muito raro conseguir fazer algo grande sem branches.

A análise passa for representar o fluxo de execução através de um grafo. Um exemplo pego da Wikipedia:

Complexidade ciclomática

Esse código tem CC 3 já que existem 2 branches típicos (um laço e um condicional) e 1 ponto de saída.

O desenvolvedor médio só precisa saber que deve manter a complexidade baixa simplificando os caminhos possíveis. Isso facilita muito seu trabalho e diminui a quantidade de problemas que podem ocorrer. Questões mais matemáticas são úteis para cientistas da computação ou engenheiros que precisam trabalhar com desenvolvimento mais formal ou rotinas muito otimizadas.

Um ponto a se considerar é que quebrar uma função em várias pode diminuir a CC desta função, mas não diminui a CC do algoritmo como um todo. Pode até aumentar. Algumas pessoas podem dizer que pelo menos fica mais fácil testar, e isso até é verdade para o teste individualizado que tem pouco valor, você ainda precisa testar todas situações e isso tem que considerar os resultados produzidos pelas funções auxiliares.

Problemas como um todo tem um limite do que dá para reduzir a CC. O que o desenvolvedor pode fazer é diminuir onde há CC em exagero, o desnecessário.

Em qual situação é importante analisar essa complexidade?

Em qualquer situação que não seja um código trivial e talvez descartável seria bom pensar sobre isso e ver se pode simplificar algo.

Existem ferramentas para medir a complexidade ciclomática do seu código em diversas linguagens, algumas até sugerem uma refatoração que pode simplificar. Então você não precisa perder tempo fazendo manualmente.

Um exemplo que mostra até concretamente como ela faz a conta.

Estudo original.

Outras métricas

Reforço que ela sozinha não é uma boa indicação de qualidade de código. Você pode diminuir a CC e o código ficar pior. Você pode optar pelo polimorfismo e passar ter decisões intrínsecas e a execução passar ter mais diferenças de execução.

Algo me chamou atenção estudando o assunto e não ficou tão claro se a complexidade de algoritmo é sobre a quantidade caminhos possíveis ou a quantidade de decisões a serem consideradas. Vi materiais divergentes sobre isso, quando ficava ambíguo por usar termos que ninguém sabe exatamente o que é aquilo, a fórmula é boa mas você não sabe o que é cada elemento da fórmula.

Se a CC considera apenas os blocos de código diferentes de acordo com o que vê escrito então acho uma medida menos importante.

Se considera a quantidade de decisões diferentes para decidir se tomará um caminho me parece mais importante.

Nem sei se isso está oficialmente correto, mas se estiver errado eu prefiro ficar com o "errado" porque ele faz mais sentido, é mais lógico, é que as pessoas podem pensar: "se tem um if então há um branch e a CC sobe 1". Não poderia ser bem assim.

Em condições normais no mínimo 1 sobe mesmo, mas se o if for true ou false já determinado pelo código sem depender da execução ele deveria subir 0.

Usando a mesma lógica, se você tiver uma condição mais complexa ali no if ou até mesmo em expressão fora dele, a complexidade pode subir mais, e pode até mesmo se tornar exponencial. Só o fato de usar um operador de concatenação de comparações como o and ou or já faz um simples if ter dois branches, então um if com 30 ands faz a CC ir para perto de 1 bilhão. Por que isso acontece? Por que no fundo cada subcondição é uma decisão separada, é como se fosse um if novo, mas está tudo concatenado.

E aí um laço poderia variar de acordo com a quantidade de interações possíveis. Mas isso está mais para complexidade de algoritmo.

Isso pode não ser CC, mas é mais importante para seu código. Inclusive porque é muito estranho você ter 10 ifs cujo bloco de execução faz a mesma coisa e se você coloca tudo junto em um único if a complexidade mudar.

Mais recentemente ouvi falar em Complexidade cognitiva. Não vi muito material tão confiável sobre isso (vi esse), mas tem softwares medindo esse tipo de coisa e considera tudo isso que eu falei. Me parece uma medida mais adequada, ainda que eu não esteja falando que é a mesma coisa.

É óbvio que uma medida que diz que a complexidade é de 1 bilhão ajuda pouco se ela não pode ser reduzida.

Conclusão

Não estou dizendo que a complexidade cognitiva é melhor porque me parece que ela tenha seus defeitos também. Todas são úteis para dar uma indicador, mas precisa entender a limitação de cada uma. Só ter a consciência que existem diversas medidas e elas devem ser observadas quando está codificando e não fazer tudo no estilo "bumba meu boi" já é um avanço que todo programador deve seguir.

Coloquei no GitHub para referência futura.

6

Complexidade ciclomática ilustrada:

Código Hadouken

Pensa em como nesse caso iria ficar o grafo que o @Maniero exemplificou ali acima. :-)

7
  • 4
    Até foi interessante colocar isso, porque há o mito que se você tiver vários ifs não aninhados, ou se colocar tudo isso com &&, porque no fundo é uma coisa só, diminui a complexidade ciclomática, mas não diminui nada, a quantidade de branches é a mesma. Só fica mais legível. Mesmo mais legível, com um único if (na verdade precisa de dois) a CC desse código continuaria sendo 13 (fiz de cabeça rapidinho, posso ter errado). OU seja, isso é curioso, mas não ilustra bem a CC.
    – Maniero
    Commented 31/03/2017 às 12:23
  • Concordo! É que eu não achei uma imagem onde além dos ifs haviam também elseifs, elses e cases (na verdade, acho que quem fizer um desenho desses vai ser internado depois, essas coisas afetam a sanidade), que aí sim faria com que a CC fosse alterada. De qualquer forma, é uma imagem, como você disse, curiosa, e divertida para o tópico. :-)
    – taq
    Commented 1/04/2017 às 13:27
  • Para complementar, 13 (se for, não conferi) já é um número meio estranho (pelo menos IMHO) ... aqui tem uns exemplos de métricas: stackoverflow.com/questions/1364946/…
    – taq
    Commented 1/04/2017 às 13:44
  • Como eu disse, posso ter feito alguma conta errada, mas porque 13 seria estranho?
    – Maniero
    Commented 1/04/2017 às 13:48
  • Aqui tem tem artigo bem legal onde definem 10 como o valor bom (eu ainda acho menos que isso aceitável ...) e 15 como um "tomara que valha a pena se você sabe o que está fazendo": mccabe.com/pdf/mccabe-nist235r.pdf De qualquer forma, em termos de legibilidade, manutenção e eficiência de código eu prefiro números menores.
    – taq
    Commented 1/04/2017 às 13:59

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .