Cómo determinar si un algoritmo informático es complejo o no

La complejidad ciclomática es un buen comienzo.

Hay 2 versiones diferentes, pero cualquiera de las dos te ayudará.

Es una medida del número de rutas a través de una función.

Complejidad ciclomática – Wikipedia

Una guía “general” es “no vaya más allá de 10”. Pero obviamente esto se puede renunciar en ciertas circunstancias.

UNA

Switch (someVariable) {…}

Es mejor que un montón de sentencias if anidadas, por lo general. He visto valores en los bajos cientos que tenían sentido. Podría dividirse en varias funciones, pero esto probablemente no tiene sentido.

Pero su utilidad no termina ahí. También es una indicación de cuánto esfuerzo de prueba se necesita para cubrir cada ruta (nota: es solo una medida. Necesita otros para estimar adecuadamente el esfuerzo de prueba).

Cuando se aplica al código a nivel de función, funciona bien como una medida, cuando se mueve al nivel de componente, necesitará otras medidas, como entrada / salida de ventilador

Hay un artículo bastante bueno aquí.

Complejidad de software

Espero que esto ayude.

Hay muchos libros dedicados a este tema. Busque libros sobre “algoritmos y estructuras de datos”. La mayoría de ellos son libros de texto. Esta es un área importante de conocimiento cubierta en cualquier programa universitario de ciencias de la computación. Este conocimiento es una de las cosas que distingue a los graduados de un programa de CS de la mayoría de los programadores autodidactas.

La medida de complejidad utilizada con mayor frecuencia es el costo del tiempo de ejecución. Un algoritmo que se puede expresar en unas pocas líneas de código puede realizar muchos cálculos cuando se ejecuta. Existe un continuo de complejidad, desde algoritmos simples que se ejecutan en un número constante de operaciones, hasta algoritmos tan complejos que no se pueden ejecutar para todos los conjuntos de datos, excepto los más pequeños.

Si medimos el costo del tiempo de ejecución en un cronómetro, dependería de la computadora en la que realizamos la prueba (entre otros factores), y las comparaciones no serían posibles.

La mayoría de los tiempos de ejecución de los algoritmos son proporcionales a alguna función del tamaño de la entrada. Por ejemplo, lleva más tiempo leer, buscar u ordenar una lista de 10,000 nombres que 10 nombres.

Leer una lista de n nombres lleva un tiempo proporcional a n. No puede ir más rápido y aún leer todos los n nombres.

Buscar para ver si un nombre está en una lista de n nombres mirando cada nombre por turno toma tiempo proporcional a n. En promedio, encontrará el nombre, si está presente, en n / 2 comparaciones. Pero n / 2 sigue siendo proporcional a n. Si los nombres se presentan en una fila y se ordenan, hay una forma más rápida de buscar. Primero miraríamos el segundo nombre en la fila. Si el nombre que estamos buscando aparece alfabéticamente antes del segundo nombre, miraríamos a la mitad de la primera mitad de la lista, reduciendo la parte de la lista que tendríamos que buscar en cada paso. Resulta que el costo de tiempo de buscar de esta manera es proporcional al logaritmo de base 2 de n. Este es un resultado interesante. Significa que hay más de una forma de buscar una lista de nombres, y que algunas formas son más rápidas que otras.

Puede determinar la complejidad de un algoritmo ejecutando el algoritmo en entradas de diferentes tamaños y graficando el tiempo de ejecución. Pero es más probable que examine el comportamiento del algoritmo en su cabeza, probablemente comparándolo con otros algoritmos que ya haya visto. Por ejemplo, los algoritmos que dividen la entrada a la mitad en cada paso tienen una complejidad proporcional a log2 (n). Esto se escribe O (log n).

No hay forma de ajustar un libro de texto completo de algoritmos y estructuras de datos en una publicación de quora. Solo tendrás que obtener un título de CS.

En términos de cómo se describe un algoritmo:

  • ¿Puede describirlo con precisión en inglés (o cualquiera que sea su idioma nativo) para que alguien más pueda implementarlo sin errores?
  • ¿Se puede describir el algoritmo solo en Pseudocódigo?
  • ¿Se puede describir el algoritmo solo en términos de sus casos de prueba? Es decir, cualquier lenguaje natural o pseudocódigo no puede entenderse sin ambigüedad.

En términos de implementación:

  • La implementación es un conjunto lineal simple de instrucciones, sin bucles, aritmética simple, condicional simple y bucles simples.
  • ¿La implementación requiere cálculos más allá de las simples operaciones matemáticas o lógicas, o requiere múltiples bucles anidados o condicionales complejos? ¿La implementación requiere múltiples parámetros?
  • ¿La implementación requiere recursión (especialmente recursividad principal): ¿funciona la implementación con múltiples tipos de datos?