¡Simplifiquemos las complejidades del algoritmo!

Ha pasado un tiempo desde que comencé a pensar en volver a lo básico y repasar los conceptos básicos de la informática. Y pensé, antes de saltar al grupo de temas de peso pesado como estructuras de datos, sistemas operativos, OOP, bases de datos y diseño de sistemas (en serio, la lista es interminable), probablemente debería retomar el tema que todos no queremos. toque: algoritmo Análisis de complejidad.

¡Sí! El concepto que se pasa por alto la mayor parte del tiempo, porque la mayoría de nosotros los desarrolladores estamos pensando, "Hmm, ¡probablemente no necesitaré saber eso mientras codifico!".

Bueno, no estoy seguro de si alguna vez sintió la necesidad de comprender cómo funciona realmente el análisis de algoritmos. Pero si lo hizo, aquí está mi intento de explicarlo de la manera más lúcida posible. Espero que ayude a alguien como yo.

De todos modos, ¿qué es el análisis de algoritmos y por qué lo necesitamos? ?

Antes de sumergirnos en el análisis de complejidad de algoritmos, primero tengamos una breve idea de qué es el análisis de algoritmos. El análisis de algoritmos se ocupa de comparar algoritmos en función del número de recursos informáticos que utiliza cada algoritmo.

Lo que queremos lograr con esta práctica es poder tomar una decisión informada sobre qué algoritmo es el ganador en términos de hacer un uso eficiente de los recursos (tiempo o memoria, según el caso de uso). ¿Esto tiene sentido?

Pongamos un ejemplo. Supongamos que tenemos una función product () que multiplica todos los elementos de una matriz, excepto el elemento en el índice actual, y devuelve la nueva matriz. Si paso [1,2,3,4,5] como entrada, debería obtener [120, 60, 40, 30, 24] como resultado.

La función anterior hace uso de dos bucles for anidados para calcular el resultado deseado. En la primera pasada, toma el elemento en la posición actual. En la segunda pasada, multiplica ese elemento con cada elemento de la matriz, excepto cuando el elemento del primer ciclo coincide con el elemento actual del segundo ciclo. En ese caso, simplemente lo multiplica por 1 para mantener el producto sin modificar.

¿Eres capaz de seguir? ¡Excelente!

Es un enfoque simple que funciona bien, pero ¿podemos mejorarlo un poco? ¿Podemos modificarlo de tal manera que no tengamos que hacer dos usos de los bucles anidados? ¿Quizás almacenar el resultado en cada pasada y hacer uso de eso?

Consideremos el siguiente método. En esta versión modificada, el principio aplicado es que para cada elemento, calcule el producto de los valores de la derecha, calcule los productos de los valores de la izquierda y simplemente multiplique esos dos valores. Bastante dulce, ¿no?

Aquí, en lugar de hacer uso de bucles anidados para calcular valores en cada ejecución, usamos dos bucles no anidados, lo que reduce la complejidad general en un factor de O (n) (lo veremos más adelante).

Podemos inferir con seguridad que el último algoritmo funciona mejor que el primero. ¿Hasta aquí todo bien? ¡Perfecto!

En este punto, también podemos echar un vistazo rápido a los diferentes tipos de análisis de algoritmos que existen. No es necesario que entremos en los detalles del nivel de minutos, solo necesitamos tener una comprensión básica de la jerga técnica.

Dependiendo de cuándo se analiza un algoritmo, es decir, antes de la implementación o después de la implementación, el análisis del algoritmo se puede dividir en dos etapas:

  • Análisis a priori : como sugiere el nombre, a priori (antes), hacemos análisis (espacio y tiempo) de un algoritmo antes de ejecutarlo en un sistema específico. Entonces, fundamentalmente, este es un análisis teórico de un algoritmo. La eficiencia de un algoritmo se mide asumiendo que todos los demás factores, por ejemplo, la velocidad del procesador, son constantes y no tienen ningún efecto sobre la implementación.
  • Análisis Apostiari: el análisis Apostiari de un algoritmo se realiza solo después de ejecutarlo en un sistema físico. El algoritmo seleccionado se implementa utilizando un lenguaje de programación que se ejecuta en una máquina de computadora de destino. Depende directamente de las configuraciones del sistema y los cambios de un sistema a otro.

En la industria, rara vez realizamos análisis Apostiari, ya que el software generalmente está hecho para usuarios anónimos que pueden ejecutarlo en diferentes sistemas.

Dado que la complejidad del tiempo y el espacio puede variar de un sistema a otro, el análisis a priori es el método más práctico para encontrar las complejidades de los algoritmos. Esto se debe a que solo miramos las variaciones asintóticas (veremos eso más adelante) del algoritmo, lo que da la complejidad en función del tamaño de entrada en lugar de las configuraciones del sistema.

Ahora que tenemos una comprensión básica de qué es el análisis de algoritmos, podemos avanzar a nuestro tema principal: la complejidad del algoritmo. Nos centraremos en el análisis a priori , teniendo en cuenta el alcance de esta publicación, así que comencemos.

Sumérjase en la complejidad con el análisis asintótico

El análisis de complejidad de algoritmos es una herramienta que nos permite explicar cómo se comporta un algoritmo a medida que la entrada crece.

Entonces, si desea ejecutar un algoritmo con un conjunto de datos de tamaño n , por ejemplo, podemos definir la complejidad como una función numérica f (n) - tiempo versus el tamaño de entrada n .

Ahora debe preguntarse, ¿no es posible que un algoritmo tome diferentes cantidades de tiempo en las mismas entradas, dependiendo de factores como la velocidad del procesador, el conjunto de instrucciones, la velocidad del disco y la marca del compilador? Si es así, entonces date una palmada en la espalda, ¿¡porque tienes toda la razón !?

Aquí es donde entra en juego el Análisis Asintótico . Aquí, el concepto es evaluar el rendimiento de un algoritmo en términos de tamaño de entrada (sin medir el tiempo real que tarda en ejecutarse). Entonces, básicamente, calculamos cómo aumenta el tiempo (o espacio) que toma un algoritmo a medida que hacemos que el tamaño de entrada sea infinitamente grande.

El análisis de complejidad se realiza en dos parámetros:

  1. Time: Time complexity gives an indication as to how long an algorithm takes to complete with respect to the input size. The resource which we are concerned about in this case is CPU (and wall-clock time).
  2. Space: Space complexity is similar, but is an indication as to how much memory is “required” to execute the algorithm with respect to the input size. Here, we dealing with system RAM as a resource.

Are you still with me? Good! Now, there are different notations which we use for analyzing complexity through asymptotic analysis. We will go through all of them one by one and understand the fundamentals behind each.

The Big oh (Big O)

The very first and most popular notation used for complexity analysis is BigO notation. The reason for this is that it gives the worst case analysis of an algorithm. The nerd universe is mostly concerned about how badly an algorithm can behave, and how it can be made to perform better. BigO provides us exactly that.

Let’s get into the mathematical side of it to understand things at their core.

Let’s consider an algorithm which can be described by a function f(n). So, to define the BigO of f(n), we need to find a function, let’s say, g(n), which bounds it. Meaning, after a certain value, n0, the value of g(n) would always exceed f(n).

We can write it as,

f(n) ≤ C g(n)

where n≥n0; C> 0; n0≥1

If above conditions are fulfilled, we can say that g(n) is the BigO of f(n), or

f(n) = O (g(n))

Can we apply the same to analyze an algorithm? This basically means that in worst case scenario of running an algorithm, the value should not pass beyond a certain point, which is g(n) in this case. Hence, g(n) is the BigO of f(n).

Let’s go through some commonly used bigO notations and their complexity and understand them a little better.

  • O(1): Describes an algorithm that will always execute in the same time (or space) regardless of the size of the input data set.
function firstItem(arr){ return arr[0];}

The above function firstItem(), will always take the same time to execute, as it returns the first item from an array, irrespective of its size. The running time of this function is independent of input size, and so it has a constant complexity of O(1).

Relating it to the above explanation, even in the worst case scenario of this algorithm (assuming input to be extremely large), the running time would remain constant and not go beyond a certain value. So, its BigO complexity is constant, that is O(1).

  • O(N): Describes an algorithm whose performance will grow linearly and in direct proportion to the size of the input data set. Take a look at the example below. We have a function called matchValue() which returns true whenever a matching case is found in the array. Here, since we have to iterate over the whole of the array, the running time is directly proportional to the size of the array.
function matchValue(arr, k){ for(var i = 0; i < arr.length; i++){ if(arr[i]==k){ return true; } else{ return false; } } }

This also demonstrates how Big O favors the worst-case performance scenario. A matching case could be found during any iteration of the for loop and the function would return early. But Big O notation will always assume the upper limit (worst-case) where the algorithm will perform the maximum number of iterations.

  • O(N²): This represents an algorithm whose performance is directly proportional to the square of the size of the input data set. This is common with algorithms that involve nested iterations over the data set. Deeper nested iterations will result in O(N³), O(N⁴), etc.
function containsDuplicates(arr){ for (var outer = 0; outer < arr.length; outer++){ for (var inner = 0; inner < arr.length; inner++){ if (outer == inner) continue; if (arr[outer] == arr[inner]) return true; } } return false;}
  • O(2^N): Denotes an algorithm whose growth doubles with each addition to the input data set. The growth curve of an O(2^N) function is exponential — starting off very shallow, then rising meteorically. An example of an O(2^N) function is the recursive calculation of Fibonacci numbers:
function recursiveFibonacci(number){ if (number <= 1) return number; return recursiveFibonacci(number - 2) + recursiveFibonacci(number - 1);}

Are you getting the hang of this? Perfect. If not, feel free to fire up your queries in the comments below. :)

Moving on, now that we have a better understanding of the BigO notation, let us get to the next type of asymptotic analysis which is, the Big Omega(Ω).

The Big Omega (Ω)?

The Big Omega(Ω) provides us with the best case scenario of running an algorithm. Meaning, it would give us the minimum amount of resources (time or space) an algorithm would take to run.

Let’s dive into the mathematics of it to analyze it graphically.

We have an algorithm which can be described by a function f(n). So, to define the BigΩ of f(n), we need to find a function, let’s say, g(n), which is tightest to the lower bound of f(n). Meaning, after a certain value, n0, the value of f(n) would always exceed g(n).

We can write it as,

f(n)≥ C g(n)

where n≥n0; C> 0; n0≥1

If above conditions are fulfilled, we can say that g(n) is the BigΩ of f(n), or

f(n) = Ω (g(n))

Can we infer that Ω(…) is complementary to O(…)? Moving on to the last section of this post…

The Big Theta (θ)?

The Big Theta(θ) is a sort of a combination of both BigO and BigΩ. It gives us the average case scenario of running an algorithm. Meaning, it would give us the mean of the best and worst case. Let’s analyse it mathematically.

Considering an algorithm which can be described by a function f(n). The Bigθ of f(n) would be a function, let’s say, g(n), which bounds it the tightest by both lower and upper bound, such that,

C₁g(n) ≤ f(n)≤ C₂ g(n)

whereC₁, C₂ >0, n≥ n0,

n0 ≥ 1

Meaning, after a certain value, n0, the value of C₁g(n) would always be less than f(n), and value of C₂ g(n) would always exceed f(n).

Now that we have a better understanding of the different types of asymptotic complexities, let’s have an example to get a clearer idea of how all this works practically.

Consider an array, of size, say, n, and we want to do a linear search to find an element x in it. Suppose the array looks something like this in the memory.

Going by the concept of linear search, if x=9, then that would be the best case scenario for the following case (as we don’t have to iterate over the whole array). And from what we have just learned, the complexity for this can be written as Ω(1). Makes sense?

Similarly, if x were equal to 14, that would be the worst case scenario, and the complexity would have been O(n).

What would be the average case complexity for this?

θ(n/2) => 1/2 θ(n) => θ(n) (As we ignore constants while calculating asymptotic complexities).

So, there you go folks. A fundamental insight into algorithmic complexities. Did it go well with you? Leave your advice, questions, suggestions in the comments below. Thanks for reading!❤️

References:-

  • A nice write-up by Dionysis “dionyziz” Zindros: //discrete.gr/complexity/
  • A good series on algorithm & data structures: //interactivepython.org/runestone/static/pythonds/AlgorithmAnalysis/WhatIsAlgorithmAnalysis.html