Complexidade ciclomática
Complexidade ciclomática (ou complexidade condicional) é uma métrica de software usada para indicar a complexidade de um programa de computador. Desenvolvida por Thomas J. McCabe em 1976, ela mede a quantidade de caminhos de execução independentes a partir de um código fonte.
Essa complexidade é computada através do grafo de fluxo de controle do programa: os nós do grafo correspondem a grupos indivisíveis de comandos, e uma aresta direcionada conecta dois nós se o segundo comando pode ser executado imediatamente após o primeiro. A complexidade ciclomática também pode ser aplicada a funções, módulos, métodos ou classes individuais de um programa.
Uma estratégia de teste de software formulada por McCabe é testar cada caminho independente de um programa, de forma que a quantidade de casos de teste será a complexidade ciclomática do programa.[1]
Descrição
![](http://upload.wikimedia.org/wikipedia/commons/thumb/2/2b/Control_flow_graph_of_function_with_loop_and_an_if_statement_without_loop_back.svg/220px-Control_flow_graph_of_function_with_loop_and_an_if_statement_without_loop_back.svg.png)
A complexidade ciclomática de uma seção do código fonte é a quantidade de caminhos independentes pelo código. Por exemplo, se o código fonte não contém estruturas de controle senão sequenciais a complexidade é 1, já que há somente um caminho válido através do código. Se o código possui somente uma estrutura de seleção contendo somente uma condição, então há dois caminhos possíveis, aquele quando a condição é avaliada em verdadeiro, e aquele quando a condição é avaliada em falso.
Matematicamente, a complexidade ciclomática de um programa estruturado é definida com referência ao grafo direcionado que contém os blocos básicos do programa, com uma aresta entre dois blocos se o controle pode passar do primeiro para o segundo imediatamente, sem blocos intermediários. A complexidade então é definida como:[2]
Em que:
- – complexidade ciclomática
- – quantidade de setas
- – quantidade de nós
- – quantidade de componentes conectados
![](http://upload.wikimedia.org/wikipedia/commons/thumb/3/30/Control_flow_graph_of_function_with_loop_and_an_if_statement.svg/220px-Control_flow_graph_of_function_with_loop_and_an_if_statement.svg.png)
Uma formulação alternativa é usar um grafo em que o ponto de saída é conectado ao ponto de entrada. Nesse caso, o grafo é dito fortemente conectado, e a complexidade ciclomática do programa é equivalente ao número ciclomático do grafo, definido como:[2]
Isso pode ser visto como o cálculo da quantidade de ciclos independentes que existem no grafo, isto é, os ciclos que não contém outros ciclos embarcados. Notar que, tendo em vista que o ponto de saída é conectado ao ponto de entrada, há pelo menos um ciclo para cada ponto de saída.
Para um programa único, ou subrotina ou método, P é sempre igual a 1. Entretanto, a complexidade ciclomática pode ser aplicada a diversos programas ou subprogramas simultaneamente, de forma que P será a quantidade de programas em questão. Pode-se demonstrar que a complexidade ciclomática de qualquer programa estruturado com somente um ponto de entrada e um ponto de saída é igual a quantidade de pontos de decisão – como condicionais de estruturas de seleção ou uma iteração dos laços das estruturas de repetição – mais um.[2][3]
A complexidade ciclomática também pode ser estendida para programas com múltiplas saídas, definida como:[3][4]
Em que:
- – quantidade de pontos de decisão do programa
- – quantidade de pontos de saída
Referências
- ↑ A J Sojev. «Basis Path Testing»
- ↑ a b c McCabe (1976). «A Complexity Measure» (PDF). IEEE Transactions on Software Engineering: 308–320. Consultado em 21 de março de 2010. Arquivado do original (PDF) em 29 de dezembro de 2009
- ↑ a b Belzer, Kent, Holzman and Williams (1992). Encyclopedia of Computer Science and Technology. [S.l.]: CRC Press. pp. 367–368 !CS1 manut: Nomes múltiplos: lista de autores (link)
- ↑ Harrison (Outubro de 1984). «Applying Mccabe's complexity measure to multiple-exit programs». J Wiley & Sons. Software: Practice and Experience
Ver também
- Complexidade
- Programa de computador
- Estrutura de controle
- Qualidade de software
Leitura adicional
- Thomas J. McCabe (Dezembro de 1976). «A Complexity Measure» (PDF). IEEE Transactions on Software Engineering Vol. 2, Nº 4, p. 308 (em inglês). IEEE