La complejidad esencial es una medida numérica definida por Thomas J. McCabe, Sr., en su artículo de 1976, muy citado, mejor conocido por introducir la complejidad ciclomática . McCabe definió la complejidad esencial como la complejidad ciclomática del gráfico de flujo de control (CFG ) reducido después de reemplazar iterativamente (reducir) todas las estructuras de control de programación estructurada , es decir, aquellas que tienen un único punto de entrada y un único punto de salida (por ejemplo, bucles if-then-else y while) con declaraciones individuales de marcador de posición. [1] : 317 [2] : 80
El proceso de reducción de McCabe tiene como objetivo simular el reemplazo conceptual de las estructuras de control (y las declaraciones reales que contienen) con llamadas a subrutinas, de ahí el requisito de que las estructuras de control tengan una única entrada y un único punto de salida. [1] : 317 (Hoy en día, un proceso como este caería bajo el término general de refactorización ). Todos los programas estructurados evidentemente tienen una complejidad esencial de 1 según la definición de McCabe porque todos pueden reducirse iterativamente a una única llamada a una subrutina de nivel superior. [1] : 318 Como McCabe explica en su artículo, su métrica de complejidad esencial fue diseñada para proporcionar una medida de qué tan lejos de este ideal (de estar completamente estructurado) estaba un programa dado. [1] : 317 Por lo tanto, los números de complejidad esencial mayores que 1, que solo se pueden obtener para programas no estructurados, indican que están más lejos del ideal de programación estructurada. [1] : 317
Para evitar confusiones entre las distintas nociones de reducibilidad a programas estructurados, es importante señalar que el artículo de McCabe analiza brevemente y luego opera en el contexto de un artículo de 1973 de S. Rao Kosaraju , que ofreció un refinamiento (o visión alternativa) del teorema del programa estructurado . El artículo seminal de 1966 de Böhm y Jacopini mostró que todos los programas pueden [re]escribirse utilizando únicamente construcciones de programación estructurada (también conocidas como las estructuras D: secuencia, if-then-else y while-loop); sin embargo, al transformar un programa aleatorio en un programa estructurado, puede ser necesario introducir variables adicionales (y utilizarlas en las pruebas) y puede duplicarse algún código. [3]
En su artículo, Böhm y Jacopini conjeturaron, pero no probaron, que era necesario introducir tales variables adicionales para ciertos tipos de programas no estructurados con el fin de transformarlos en programas estructurados. [4] : 236 Un ejemplo de programa (que ahora conocemos) que requiere tales variables adicionales es un bucle con dos salidas condicionales dentro de él. Para abordar la conjetura de Böhm y Jacopini, Kosaraju definió una noción más restrictiva de reducción de programa que la equivalencia de Turing utilizada por Böhm y Jacopini. Esencialmente, la noción de reducción de Kosaraju impone, además del requisito obvio de que los dos programas deben calcular el mismo valor (o no terminar) dadas las mismas entradas, que los dos programas deben usar las mismas acciones primitivas y predicados, estos últimos entendidos como expresiones utilizadas en los condicionales. Debido a estas restricciones, la reducción de Kosaraju no permite la introducción de variables adicionales; La asignación de estas variables crearía nuevas acciones primitivas y la prueba de sus valores cambiaría los predicados utilizados en los condicionales. Utilizando esta noción más restrictiva de reducción, Kosaraju demostró la conjetura de Böhm y Jacopini, es decir, que un bucle con dos salidas no se puede transformar en un programa estructurado sin introducir variables adicionales , pero fue más allá y demostró que los programas que contienen cortes de varios niveles (de bucles) forman una jerarquía, de modo que siempre se puede encontrar un programa con cortes de varios niveles de profundidad n que no se puede reducir a un programa de cortes de varios niveles con una profundidad menor que n , de nuevo sin introducir variables adicionales. [4] [5]
McCabe señala en su artículo que, en vista de los resultados de Kosaraju, pretendía encontrar una forma de capturar las propiedades esenciales de los programas no estructurados en términos de sus gráficos de flujo de control. [1] : 315 Procede primero identificando los gráficos de flujo de control correspondientes a los programas no estructurados más pequeños (estos incluyen la ramificación en un bucle, la ramificación fuera de un bucle y sus contrapartes if-then-else) que usa para formular un teorema análogo al teorema de Kuratowski , y luego introduce su noción de complejidad esencial para dar una respuesta de escala ("medida de la estructuración de un programa" en sus palabras) en lugar de una respuesta de sí/no a la pregunta de si el gráfico de flujo de control de un programa está estructurado o no. [1] : 315 Finalmente, la noción de reducción utilizada por McCabe para reducir el CFG no es la misma que la noción de Kosaraju de reducir los diagramas de flujo. La reducción definida en el CFG no conoce ni se preocupa por las entradas del programa, es simplemente una transformación gráfica . [6]
Por ejemplo, el siguiente fragmento de programa en C tiene una complejidad esencial de 1, porque la declaración if interna y el for se pueden reducir, es decir, es un programa estructurado.
para ( i = 0 ; i < 3 ; i ++ ) { si ( a [ i ] == 0 ) b [ i ] += 2 ; } El siguiente fragmento de programa en C tiene una complejidad esencial de cuatro; su CFG es irreducible. El programa encuentra la primera fila de z que es toda cero y coloca ese índice en i; si no hay ninguno, coloca -1 en i.
para ( i = 0 ; i < m ; i ++ ) { para ( j = 0 ; j < n ; j ++ ) { si ( z [ i ][ j ] != 0 ) ir a distinto de cero ; } ir a encontrado ; distinto de cero : } i = -1 ; encontrado : La idea de la reducibilidad de CFG mediante colapsos sucesivos de subgrafos (en última instancia, a un solo nodo para CFG con buen comportamiento) también se utiliza en la optimización de compiladores modernos. Sin embargo, la noción de la programación estructurada de estructura de control de entrada única y salida única se reemplaza por la de bucle natural, que se define como un "bucle de entrada única y salida múltiple, con solo una única rama de regreso a la entrada desde dentro de él". Las áreas del CFG que no se pueden reducir a bucles naturales se denominan regiones impropias ; estas regiones terminan teniendo una definición bastante simple: componentes del CFG de múltiples entradas y fuertemente conectados. La región impropia más simple es, por lo tanto, un bucle con dos puntos de entrada. Las salidas múltiples no causan problemas de análisis en los compiladores modernos. Las regiones impropias (entradas múltiples en bucles) sí causan dificultades adicionales en la optimización del código. [7]