Análisis de Algoritmos - [Parte 1] Introducción


Valeo08

Capullo perro no mucho
Noderador
Nodero
Noder
FAA1.png


Buenas noders, llorones y otras faunas habitantes en el nodo.

Hoy les vengo a hablar del mundo de la Algoritmia, lo que viene siendo el análisis y estudio de los algoritmos, su eficiencia y la teoría que les rodea.

A la hora de buscar el método para resolver un problema, es decir un algoritmo, es muy importante su diseño y el estudio de la eficiencia que este pueda
tener. Lo primero se refiere a la búsqueda de procedimientos que, con una secuencia finita de instrucciones lleguen a una solución que se adecúe al
dispositivo del que disponemos para trabajar. Lo segundo, hace que podamos dar una medida del coste (ya sea en tiempo o espacio) que consume el
algoritmo para llegar a la solución; de esta forma se pueden comparar y decidir cual es el más adecuado.

En la introducción, voy a centrarme en la medida de la eficiencia de los algoritmos, en las siguientes partes, explicaré las técnicas de diseño y los algoritmos
más frecuentes y conocidos para según qué tipo de problemas. (Ojo cuidao, esto de la eficiencia, se basa en gran medida en las matemáticas, pero el resumen
que haré no se va a adentrar demasiado en ello, puesto que sobaríais muy fuertemente, cosa que seguramente haréis puesto que esta parte es muy teórica).


1. La Eficiencia y la Complejidad

Una vez ya tenemos un algoritmo que funciona correctamente, es necesario definir criterios para medir su rendimiento o comportamiento. Normalmente, dichos
criterios se centran en su simplicidad o en el uso de recursos del computador. Se puede pensar que un algoritmo muy simple no tiene mucha eficiencia, pero hay
ventajas que pueden decantarnos por su uso, como pueden ser la fácil legibilidad del código y su mantenimiento, y por tanto la sencilla forma de medir su
eficiencia; esto hace que en determinados casos sean lo más conveniente.

Con respecto al uso de recursos, este se suele medir en función de: el tiempo que emplea en ejecutarse, y el espacio, es decir, la memoria que emplea para ello. Ambos
son los costes que representa resolver el problema mediante el algoritmos medido. Además, van a ser los parámetros que empleemos para comparar entre algoritmos.

El tiempo de ejecución es una medida que va a depender de muchos factores, demasiados, como son la calidad del código, la carga de trabajo del computador, la
eficiencia y rapidez del compilador, los datos que se maneje, la complejidad intrínseca del algoritmo, etc, por ello hay dos formas de dar esta medida:
  • Una medida teórica (o a priori), que consiste en obtener una función que acote (por arriba o abajo) el tiempo de ejecución para unos valores de entrada dados.
  • Una medida empírica o real (o a posteriori), consistente en medir el tiempo de ejecución para unos valores de entrada dados y un computador concreto.
Ambas medidas son importantes puesto que, si bien la primera nos da una estimación del comportamiento del algoritmo de forma independiente del ordenador en
donde será implementado y sin necesidad de ejecutarlo, la segunda representa las medidas reales del comportamiento del algoritmo. Estas medidas son funciones
temporales de los datos de entrada.

El tamaño de la entrada es el número de componentes sobre el que se ejecuta el algoritmo, por ejemplo, el tamaño de un vector a ordenar o el de unas matrices que
vayamos a multiplicar.

La unidad de tiempo a la que deben de hacer referencia estas medidas de eficiencia no puede ser expresada en segundos o en otra unidad de tiempo concreta,
pues no existe un ordenador estándar al que puedan hacer referencia. Denotaremos por T ( n ) el tiempo de ejecución de un algoritmo para una entrada de tamaño n,
y si nos centramos en el uso espacial, denotamos con E ( n ) la cantidad de memoria necesaria para un algoritmo dada una entrada de tamaño n.


2. Conteo de Operaciones

El análisis temporal (y el espacial) se hará únicamente con base al algoritmo escrito en pseudocódigo. Como el pseudocódigo no se puede ejecutar para medir la
cantidad de tiempo que consume, la complejidad temporal no se expresará en unidades de tiempo, sino en términos de la cantidad de operaciones que realiza para la
ejecución del algoritmo. El tiempo de ejecución de un algoritmo va a ser una función que mide el número de operaciones elementales (las que el ordenador realiza en
un tiempo acotado) que realiza para un tamaño de entrada dado.

Consideraremos operaciones elementales (contabilizándolas como 1 operación elemental en la medida teórica) las siguientes:
  • Operaciones aritméticas básicas.​
  • Asignaciones a variables de tipo predefinido.​
  • Saltos:​
    • Llamadas a funciones o procedimientos.​
    • Retorno desde funciones o procedimientos.​

  • Comparaciones lógicas.​
  • Accesos a estructuras indexadas básicas (vectores, matrices, arrays, etc).​
Dado un algoritmo, se pueden determinar qué tipos de operaciones utiliza y cuántas veces las ejecuta para una entrada específica.

La reglas generales para el cálculo de operaciones elementales (siempre considerando el peor caso), definen el número de operaciones elementales de cada estructura
básica del lenguaje. El número total de un algoritmo se calcula por inducción sobre ellas. Considerando que el tiempo de una operación elemental, por definición, es
de orden 1. Las reglas son (algunas reglas contienen tipos de sentencias en pseudocódigo):
  1. El tiempo de ejecución de una secuencia consecutiva de instrucciones se calcula sumando los tiempos de ejecución de cada una de las instrucciones.
  2. El tiempo de ejecución de la sentencia del tipo: “caso E sea v1:S1 | v2:S2 | ... | vn:Sn | otro S0 fcaso” (sentencia switch) es T = T(E) + max{T(S1),T(S2),...,T(Sn)}, donde T(E) incluye el tiempo de comparación con v1, v2 , ..., vn.
  3. El tiempo de ejecución de la sentencia “Si C entonces S1 otro S2 fsi” es T = T(C) + max{T(S1),T(S2)}.
  4. El tiempo de ejecución del bucle “mientras C hacer S fmientras” es T = T(C) + (nº iteraciones)*(T(S) + T(C)), tanto T(C) como T(S) pueden variar en cada iteración, y por tanto habrá que tenerlo en cuenta para su cálculo. Para calcular el tiempo de ejecución del resto de sentencias iterativas (PARA,REPETIR) basta expresarlas como un bucle MIENTRAS.
  5. El tiempo de ejecución de una llamada a un procedimiento o función F(P1, P2, ... , Pn) es 1 (por la llamada), más el tiempo de evaluación de los parámetros P1, P2, ... , Pn, más el tiempo que tarde en ejecutarse F, esto es, T = 1 + T(P1) + T(P2) + ... + T(Pn) + T(F).
  6. El tiempo de ejecución de las llamadas a procedimientos recursivos da lugar a ecuaciones en recurrencia (cosa que lo mismo es un poco más complicado y no voy a explicar).
En general, es posible realizar el estudio de la complejidad de un algoritmo sólo en base a un conjunto reducido de sentencias (se le denomina operación básica),
aquellas que caracterizan que el algoritmo sea lento o rápido en el sentido que nos interesa.
Resumiendo, el análisis de un algoritmo se puede hacer considerando sólo aquella operación que cumpla los siguientes criterios:
  • Debe estar relacionada con el tipo de problema que se resuelve.
  • Debe ejecutarse un número de veces cuyo modelo de crecimiento sea similar al del número total de operaciones que efectúa el algoritmo.
Si ninguna de las operaciones encontradas cumple los dos criterios, es posible declinar el primero. Si aun así no es posible encontrar una operación representativa,
se debe hacer un análisis global, contando todas las operaciones y utilizando las reglas que hemos visto antes (lo cual no mola).


3. Instancias

En la teoría de algoritmos es muy frecuente usar el término instancia para indicar un caso específico de un problema. Así, por ejemplo, si el problema es la multiplicación
de 2 enteros positivos una instancia es el par de números a multiplicar 7 y 8. Si ponemos un ejemplo para el caso del cálculo de la eficiencia de un algoritmo de ordenación
que tenga una complejidad lineal, una instancia podría ser el conjunto de enteros a ordenar {2, 4, 6, -1, 76, -53, 89, 291}, lo cual haría que su función de complejidad temporal
tuviera esta forma T ( 8 ).


4. Casos peor, mejor y medio

Se definen:
  • I ( n ) = { I1, I2, I3, ... , Ik } como el conjunto de instancias del problema de tamaño n.
  • O ( n ) = { O1, O2, O3, ... , Ok } como el conjunto formado por el número de operaciones que un algoritmo realiza para resolver cada instancia.
  • Oj es el nº operaciones ejecutadas para resolver la instancia Ij para 1 ≤ j ≤ k.
  • Se distinguen tres casos en el valor de la función complejidad temporal:
    • Caso Peor : T ( n ) = máx ( { O1, O2, O3, ... , Ok } ).
    • Caso Mejor : T ( n ) = mín ( { O1, O2, O3, ... , Ok } ).
    • Caso Medio : T ( n ) = Σi=1^k ( Oi · P(i) ), donde P(i) es la probabilidad de que ocurra la instancia Ii. (Lo del principio es un sumatorio desde i = 1 hasta k).
El mejor caso se presenta cuando para una entrada de tamaño n; el algoritmo ejecuta el mínimo número posible de operaciones, el peor caso cuando
hace el máximo número posible de operaciones. En el caso medio se consideran todos los casos posibles para calcular el promedio de las operaciones
que se hacen teniendo en cuenta la probabilidad de que ocurra cada instancia.

Los casos en la función complejidad espacial, se pueden definir análogamente, considerando en vez de O ( n ) el conjunto C ( n ) como el conjunto formado
por el número de celdas de memoria (unidad teórica para medir el espacio utilizado en memoria) utilizadas por el algoritmo para resolver cada instancia del problema.

Es importante mencionar que no todos los algoritmos presentan casos, y resulta interesante tener una herramienta para detectar cuándo se particionará el
análisis en casos; de momento, solo está la intuición a la hora de realizar el análisis del propio algoritmo.

El conteo visto se puede emplear para estimar la cantidad de recursos que un algoritmo consume; pero el objetivo no sólo es conocer dicha cantidad, sino,
más aún, poder comparar el comportamiento de distintos algoritmos, con el fin de decidir cuál de ellos utilizar bajo circunstancias específicas.



Espero llegados aquí, que no os hayáis dormido, porque meviacagarendiosyaeh.
En las próximas partes, me centraré en los distintos tipos de algoritmos para problemas varios así como su diseño.

Ya nos veremos.
 

Anon

🏴‍☠️
Owner
Staff
Moderador
Paladín de Nodo
Jinete de Nodo
Burgués de Nodo
Noderador
Nodero
Noder
Por favor este post merece todos los likes del foro, mil gracias por un post así de currado @Valeo08
 
  • Maravilloso
Reacciones : Valeo08

Dark

🔥root313🔥
Staff
Moderador
Paladín de Nodo
Jinete de Nodo
Burgués de Nodo
Noderador
Nodero
Noder Pro
Noder
Ver el archivo adjunto 5514

Buenas noders, llorones y otras faunas habitantes en el nodo.

Hoy les vengo a hablar del mundo de la Algoritmia, lo que viene siendo el análisis y estudio de los algoritmos, su eficiencia y la teoría que les rodea.

A la hora de buscar el método para resolver un problema, es decir un algoritmo, es muy importante su diseño y el estudio de la eficiencia que este pueda
tener. Lo primero se refiere a la búsqueda de procedimientos que, con una secuencia finita de instrucciones lleguen a una solución que se adecúe al
dispositivo del que disponemos para trabajar. Lo segundo, hace que podamos dar una medida del coste (ya sea en tiempo o espacio) que consume el
algoritmo para llegar a la solución; de esta forma se pueden comparar y decidir cual es el más adecuado.

En la introducción, voy a centrarme en la medida de la eficiencia de los algoritmos, en las siguientes partes, explicaré las técnicas de diseño y los algoritmos
más frecuentes y conocidos para según qué tipo de problemas. (Ojo cuidao, esto de la eficiencia, se basa en gran medida en las matemáticas, pero el resumen
que haré no se va a adentrar demasiado en ello, puesto que sobaríais muy fuertemente, cosa que seguramente haréis puesto que esta parte es muy teórica).


1. La Eficiencia y la Complejidad

Una vez ya tenemos un algoritmo que funciona correctamente, es necesario definir criterios para medir su rendimiento o comportamiento. Normalmente, dichos
criterios se centran en su simplicidad o en el uso de recursos del computador. Se puede pensar que un algoritmo muy simple no tiene mucha eficiencia, pero hay
ventajas que pueden decantarnos por su uso, como pueden ser la fácil legibilidad del código y su mantenimiento, y por tanto la sencilla forma de medir su
eficiencia; esto hace que en determinados casos sean lo más conveniente.

Con respecto al uso de recursos, este se suele medir en función de: el tiempo que emplea en ejecutarse, y el espacio, es decir, la memoria que emplea para ello. Ambos
son los costes que representa resolver el problema mediante el algoritmos medido. Además, van a ser los parámetros que empleemos para comparar entre algoritmos.

El tiempo de ejecución es una medida que va a depender de muchos factores, demasiados, como son la calidad del código, la carga de trabajo del computador, la
eficiencia y rapidez del compilador, los datos que se maneje, la complejidad intrínseca del algoritmo, etc, por ello hay dos formas de dar esta medida:
  • Una medida teórica (o a priori), que consiste en obtener una función que acote (por arriba o abajo) el tiempo de ejecución para unos valores de entrada dados.
  • Una medida empírica o real (o a posteriori), consistente en medir el tiempo de ejecución para unos valores de entrada dados y un computador concreto.
Ambas medidas son importantes puesto que, si bien la primera nos da una estimación del comportamiento del algoritmo de forma independiente del ordenador en
donde será implementado y sin necesidad de ejecutarlo, la segunda representa las medidas reales del comportamiento del algoritmo. Estas medidas son funciones
temporales de los datos de entrada.

El tamaño de la entrada es el número de componentes sobre el que se ejecuta el algoritmo, por ejemplo, el tamaño de un vector a ordenar o el de unas matrices que
vayamos a multiplicar.

La unidad de tiempo a la que deben de hacer referencia estas medidas de eficiencia no puede ser expresada en segundos o en otra unidad de tiempo concreta,
pues no existe un ordenador estándar al que puedan hacer referencia. Denotaremos por T ( n ) el tiempo de ejecución de un algoritmo para una entrada de tamaño n,
y si nos centramos en el uso espacial, denotamos con E ( n ) la cantidad de memoria necesaria para un algoritmo dada una entrada de tamaño n.


2. Conteo de Operaciones

El análisis temporal (y el espacial) se hará únicamente con base al algoritmo escrito en pseudocódigo. Como el pseudocódigo no se puede ejecutar para medir la
cantidad de tiempo que consume, la complejidad temporal no se expresará en unidades de tiempo, sino en términos de la cantidad de operaciones que realiza para la
ejecución del algoritmo. El tiempo de ejecución de un algoritmo va a ser una función que mide el número de operaciones elementales (las que el ordenador realiza en
un tiempo acotado) que realiza para un tamaño de entrada dado.

Consideraremos operaciones elementales (contabilizándolas como 1 operación elemental en la medida teórica) las siguientes:
  • Operaciones aritméticas básicas.​
  • Asignaciones a variables de tipo predefinido.​
  • Saltos:​
    • Llamadas a funciones o procedimientos.​
    • Retorno desde funciones o procedimientos.​

  • Comparaciones lógicas.​
  • Accesos a estructuras indexadas básicas (vectores, matrices, arrays, etc).​
Dado un algoritmo, se pueden determinar qué tipos de operaciones utiliza y cuántas veces las ejecuta para una entrada específica.

La reglas generales para el cálculo de operaciones elementales (siempre considerando el peor caso), definen el número de operaciones elementales de cada estructura
básica del lenguaje. El número total de un algoritmo se calcula por inducción sobre ellas. Considerando que el tiempo de una operación elemental, por definición, es
de orden 1. Las reglas son (algunas reglas contienen tipos de sentencias en pseudocódigo):
  1. El tiempo de ejecución de una secuencia consecutiva de instrucciones se calcula sumando los tiempos de ejecución de cada una de las instrucciones.
  2. El tiempo de ejecución de la sentencia del tipo: “caso E sea v1:S1 | v2:S2 | ... | vn:Sn | otro S0 fcaso” (sentencia switch) es T = T(E) + max{T(S1),T(S2),...,T(Sn)}, donde T(E) incluye el tiempo de comparación con v1, v2 , ..., vn.
  3. El tiempo de ejecución de la sentencia “Si C entonces S1 otro S2 fsi” es T = T(C) + max{T(S1),T(S2)}.
  4. El tiempo de ejecución del bucle “mientras C hacer S fmientras” es T = T(C) + (nº iteraciones)*(T(S) + T(C)), tanto T(C) como T(S) pueden variar en cada iteración, y por tanto habrá que tenerlo en cuenta para su cálculo. Para calcular el tiempo de ejecución del resto de sentencias iterativas (PARA,REPETIR) basta expresarlas como un bucle MIENTRAS.
  5. El tiempo de ejecución de una llamada a un procedimiento o función F(P1, P2, ... , Pn) es 1 (por la llamada), más el tiempo de evaluación de los parámetros P1, P2, ... , Pn, más el tiempo que tarde en ejecutarse F, esto es, T = 1 + T(P1) + T(P2) + ... + T(Pn) + T(F).
  6. El tiempo de ejecución de las llamadas a procedimientos recursivos da lugar a ecuaciones en recurrencia (cosa que lo mismo es un poco más complicado y no voy a explicar).
En general, es posible realizar el estudio de la complejidad de un algoritmo sólo en base a un conjunto reducido de sentencias (se le denomina operación básica),
aquellas que caracterizan que el algoritmo sea lento o rápido en el sentido que nos interesa.
Resumiendo, el análisis de un algoritmo se puede hacer considerando sólo aquella operación que cumpla los siguientes criterios:
  • Debe estar relacionada con el tipo de problema que se resuelve.
  • Debe ejecutarse un número de veces cuyo modelo de crecimiento sea similar al del número total de operaciones que efectúa el algoritmo.
Si ninguna de las operaciones encontradas cumple los dos criterios, es posible declinar el primero. Si aun así no es posible encontrar una operación representativa,
se debe hacer un análisis global, contando todas las operaciones y utilizando las reglas que hemos visto antes (lo cual no mola).


3. Instancias

En la teoría de algoritmos es muy frecuente usar el término instancia para indicar un caso específico de un problema. Así, por ejemplo, si el problema es la multiplicación
de 2 enteros positivos una instancia es el par de números a multiplicar 7 y 8. Si ponemos un ejemplo para el caso del cálculo de la eficiencia de un algoritmo de ordenación
que tenga una complejidad lineal, una instancia podría ser el conjunto de enteros a ordenar {2, 4, 6, -1, 76, -53, 89, 291}, lo cual haría que su función de complejidad temporal
tuviera esta forma T ( 8 ).


4. Casos peor, mejor y medio

Se definen:
  • I ( n ) = { I1, I2, I3, ... , Ik } como el conjunto de instancias del problema de tamaño n.
  • O ( n ) = { O1, O2, O3, ... , Ok } como el conjunto formado por el número de operaciones que un algoritmo realiza para resolver cada instancia.
  • Oj es el nº operaciones ejecutadas para resolver la instancia Ij para 1 ≤ j ≤ k.
  • Se distinguen tres casos en el valor de la función complejidad temporal:
    • Caso Peor : T ( n ) = máx ( { O1, O2, O3, ... , Ok } ).
    • Caso Mejor : T ( n ) = mín ( { O1, O2, O3, ... , Ok } ).
    • Caso Medio : T ( n ) = Σi=1^k ( Oi · P(i) ), donde P(i) es la probabilidad de que ocurra la instancia Ii. (Lo del principio es un sumatorio desde i = 1 hasta k).
El mejor caso se presenta cuando para una entrada de tamaño n; el algoritmo ejecuta el mínimo número posible de operaciones, el peor caso cuando
hace el máximo número posible de operaciones. En el caso medio se consideran todos los casos posibles para calcular el promedio de las operaciones
que se hacen teniendo en cuenta la probabilidad de que ocurra cada instancia.

Los casos en la función complejidad espacial, se pueden definir análogamente, considerando en vez de O ( n ) el conjunto C ( n ) como el conjunto formado
por el número de celdas de memoria (unidad teórica para medir el espacio utilizado en memoria) utilizadas por el algoritmo para resolver cada instancia del problema.

Es importante mencionar que no todos los algoritmos presentan casos, y resulta interesante tener una herramienta para detectar cuándo se particionará el
análisis en casos; de momento, solo está la intuición a la hora de realizar el análisis del propio algoritmo.

El conteo visto se puede emplear para estimar la cantidad de recursos que un algoritmo consume; pero el objetivo no sólo es conocer dicha cantidad, sino,
más aún, poder comparar el comportamiento de distintos algoritmos, con el fin de decidir cuál de ellos utilizar bajo circunstancias específicas.



Espero llegados aquí, que no os hayáis dormido, porque meviacagarendiosyaeh.
En las próximas partes, me centraré en los distintos tipos de algoritmos para problemas varios así como su diseño.

Ya nos veremos.
Hermano, no he entendido nada de nada, pero parece esto lo típico de las películas que empiezan a soltar palabras informáticas tipo: debemos hackear el firewall para acceder al muro digital y cambiar los algoritmos de la seguridad.
Me encanta leer cosas así, aunque no entienda ni pija.

10/10
 
  • Hahaha
  • Like
Reacciones : destapeman y LinceAzul

wannacry

tenia ganas pero no las conexiones
Burgués de Nodo
Noderador
Nodero
Noder
De los posts mas currados del foro tio, 10/10!
 

Nando

Miembro muy activo
Noder
Literalmente he dado este año esto en la Uni y lo explicas aquí mejor JAJAJJA
Buen post!!!!
 

Abaskal

Peep? :((
Noder
Gracias a este post y a muchos mas de este foro me estan haciendo entrar en el mundo de la programacion y toda esa vaina, y os doy las gracias por ello xd
 

KTaneR

Activo muy miembro
Burgués de Nodo
Noderador
Nodero
Noder
Es justo lo que me esperaba pero muy guapo, muy bien explicado!
 
Última edición:

ABDEL HADI

Miembro muy activo
Noderador
Nodero
Noder
Ver el archivo adjunto 5514

Buenas noders, llorones y otras faunas habitantes en el nodo.

Hoy les vengo a hablar del mundo de la Algoritmia, lo que viene siendo el análisis y estudio de los algoritmos, su eficiencia y la teoría que les rodea.

A la hora de buscar el método para resolver un problema, es decir un algoritmo, es muy importante su diseño y el estudio de la eficiencia que este pueda
tener. Lo primero se refiere a la búsqueda de procedimientos que, con una secuencia finita de instrucciones lleguen a una solución que se adecúe al
dispositivo del que disponemos para trabajar. Lo segundo, hace que podamos dar una medida del coste (ya sea en tiempo o espacio) que consume el
algoritmo para llegar a la solución; de esta forma se pueden comparar y decidir cual es el más adecuado.

En la introducción, voy a centrarme en la medida de la eficiencia de los algoritmos, en las siguientes partes, explicaré las técnicas de diseño y los algoritmos
más frecuentes y conocidos para según qué tipo de problemas. (Ojo cuidao, esto de la eficiencia, se basa en gran medida en las matemáticas, pero el resumen
que haré no se va a adentrar demasiado en ello, puesto que sobaríais muy fuertemente, cosa que seguramente haréis puesto que esta parte es muy teórica).


1. La Eficiencia y la Complejidad

Una vez ya tenemos un algoritmo que funciona correctamente, es necesario definir criterios para medir su rendimiento o comportamiento. Normalmente, dichos
criterios se centran en su simplicidad o en el uso de recursos del computador. Se puede pensar que un algoritmo muy simple no tiene mucha eficiencia, pero hay
ventajas que pueden decantarnos por su uso, como pueden ser la fácil legibilidad del código y su mantenimiento, y por tanto la sencilla forma de medir su
eficiencia; esto hace que en determinados casos sean lo más conveniente.

Con respecto al uso de recursos, este se suele medir en función de: el tiempo que emplea en ejecutarse, y el espacio, es decir, la memoria que emplea para ello. Ambos
son los costes que representa resolver el problema mediante el algoritmos medido. Además, van a ser los parámetros que empleemos para comparar entre algoritmos.

El tiempo de ejecución es una medida que va a depender de muchos factores, demasiados, como son la calidad del código, la carga de trabajo del computador, la
eficiencia y rapidez del compilador, los datos que se maneje, la complejidad intrínseca del algoritmo, etc, por ello hay dos formas de dar esta medida:
  • Una medida teórica (o a priori), que consiste en obtener una función que acote (por arriba o abajo) el tiempo de ejecución para unos valores de entrada dados.
  • Una medida empírica o real (o a posteriori), consistente en medir el tiempo de ejecución para unos valores de entrada dados y un computador concreto.
Ambas medidas son importantes puesto que, si bien la primera nos da una estimación del comportamiento del algoritmo de forma independiente del ordenador en
donde será implementado y sin necesidad de ejecutarlo, la segunda representa las medidas reales del comportamiento del algoritmo. Estas medidas son funciones
temporales de los datos de entrada.

El tamaño de la entrada es el número de componentes sobre el que se ejecuta el algoritmo, por ejemplo, el tamaño de un vector a ordenar o el de unas matrices que
vayamos a multiplicar.

La unidad de tiempo a la que deben de hacer referencia estas medidas de eficiencia no puede ser expresada en segundos o en otra unidad de tiempo concreta,
pues no existe un ordenador estándar al que puedan hacer referencia. Denotaremos por T ( n ) el tiempo de ejecución de un algoritmo para una entrada de tamaño n,
y si nos centramos en el uso espacial, denotamos con E ( n ) la cantidad de memoria necesaria para un algoritmo dada una entrada de tamaño n.


2. Conteo de Operaciones

El análisis temporal (y el espacial) se hará únicamente con base al algoritmo escrito en pseudocódigo. Como el pseudocódigo no se puede ejecutar para medir la
cantidad de tiempo que consume, la complejidad temporal no se expresará en unidades de tiempo, sino en términos de la cantidad de operaciones que realiza para la
ejecución del algoritmo. El tiempo de ejecución de un algoritmo va a ser una función que mide el número de operaciones elementales (las que el ordenador realiza en
un tiempo acotado) que realiza para un tamaño de entrada dado.

Consideraremos operaciones elementales (contabilizándolas como 1 operación elemental en la medida teórica) las siguientes:
  • Operaciones aritméticas básicas.​
  • Asignaciones a variables de tipo predefinido.​
  • Saltos:​
    • Llamadas a funciones o procedimientos.​
    • Retorno desde funciones o procedimientos.​

  • Comparaciones lógicas.​
  • Accesos a estructuras indexadas básicas (vectores, matrices, arrays, etc).​
Dado un algoritmo, se pueden determinar qué tipos de operaciones utiliza y cuántas veces las ejecuta para una entrada específica.

La reglas generales para el cálculo de operaciones elementales (siempre considerando el peor caso), definen el número de operaciones elementales de cada estructura
básica del lenguaje. El número total de un algoritmo se calcula por inducción sobre ellas. Considerando que el tiempo de una operación elemental, por definición, es
de orden 1. Las reglas son (algunas reglas contienen tipos de sentencias en pseudocódigo):
  1. El tiempo de ejecución de una secuencia consecutiva de instrucciones se calcula sumando los tiempos de ejecución de cada una de las instrucciones.
  2. El tiempo de ejecución de la sentencia del tipo: “caso E sea v1:S1 | v2:S2 | ... | vn:Sn | otro S0 fcaso” (sentencia switch) es T = T(E) + max{T(S1),T(S2),...,T(Sn)}, donde T(E) incluye el tiempo de comparación con v1, v2 , ..., vn.
  3. El tiempo de ejecución de la sentencia “Si C entonces S1 otro S2 fsi” es T = T(C) + max{T(S1),T(S2)}.
  4. El tiempo de ejecución del bucle “mientras C hacer S fmientras” es T = T(C) + (nº iteraciones)*(T(S) + T(C)), tanto T(C) como T(S) pueden variar en cada iteración, y por tanto habrá que tenerlo en cuenta para su cálculo. Para calcular el tiempo de ejecución del resto de sentencias iterativas (PARA,REPETIR) basta expresarlas como un bucle MIENTRAS.
  5. El tiempo de ejecución de una llamada a un procedimiento o función F(P1, P2, ... , Pn) es 1 (por la llamada), más el tiempo de evaluación de los parámetros P1, P2, ... , Pn, más el tiempo que tarde en ejecutarse F, esto es, T = 1 + T(P1) + T(P2) + ... + T(Pn) + T(F).
  6. El tiempo de ejecución de las llamadas a procedimientos recursivos da lugar a ecuaciones en recurrencia (cosa que lo mismo es un poco más complicado y no voy a explicar).
En general, es posible realizar el estudio de la complejidad de un algoritmo sólo en base a un conjunto reducido de sentencias (se le denomina operación básica),
aquellas que caracterizan que el algoritmo sea lento o rápido en el sentido que nos interesa.
Resumiendo, el análisis de un algoritmo se puede hacer considerando sólo aquella operación que cumpla los siguientes criterios:
  • Debe estar relacionada con el tipo de problema que se resuelve.
  • Debe ejecutarse un número de veces cuyo modelo de crecimiento sea similar al del número total de operaciones que efectúa el algoritmo.
Si ninguna de las operaciones encontradas cumple los dos criterios, es posible declinar el primero. Si aun así no es posible encontrar una operación representativa,
se debe hacer un análisis global, contando todas las operaciones y utilizando las reglas que hemos visto antes (lo cual no mola).


3. Instancias

En la teoría de algoritmos es muy frecuente usar el término instancia para indicar un caso específico de un problema. Así, por ejemplo, si el problema es la multiplicación
de 2 enteros positivos una instancia es el par de números a multiplicar 7 y 8. Si ponemos un ejemplo para el caso del cálculo de la eficiencia de un algoritmo de ordenación
que tenga una complejidad lineal, una instancia podría ser el conjunto de enteros a ordenar {2, 4, 6, -1, 76, -53, 89, 291}, lo cual haría que su función de complejidad temporal
tuviera esta forma T ( 8 ).


4. Casos peor, mejor y medio

Se definen:
  • I ( n ) = { I1, I2, I3, ... , Ik } como el conjunto de instancias del problema de tamaño n.
  • O ( n ) = { O1, O2, O3, ... , Ok } como el conjunto formado por el número de operaciones que un algoritmo realiza para resolver cada instancia.
  • Oj es el nº operaciones ejecutadas para resolver la instancia Ij para 1 ≤ j ≤ k.
  • Se distinguen tres casos en el valor de la función complejidad temporal:
    • Caso Peor : T ( n ) = máx ( { O1, O2, O3, ... , Ok } ).
    • Caso Mejor : T ( n ) = mín ( { O1, O2, O3, ... , Ok } ).
    • Caso Medio : T ( n ) = Σi=1^k ( Oi · P(i) ), donde P(i) es la probabilidad de que ocurra la instancia Ii. (Lo del principio es un sumatorio desde i = 1 hasta k).
El mejor caso se presenta cuando para una entrada de tamaño n; el algoritmo ejecuta el mínimo número posible de operaciones, el peor caso cuando
hace el máximo número posible de operaciones. En el caso medio se consideran todos los casos posibles para calcular el promedio de las operaciones
que se hacen teniendo en cuenta la probabilidad de que ocurra cada instancia.

Los casos en la función complejidad espacial, se pueden definir análogamente, considerando en vez de O ( n ) el conjunto C ( n ) como el conjunto formado
por el número de celdas de memoria (unidad teórica para medir el espacio utilizado en memoria) utilizadas por el algoritmo para resolver cada instancia del problema.

Es importante mencionar que no todos los algoritmos presentan casos, y resulta interesante tener una herramienta para detectar cuándo se particionará el
análisis en casos; de momento, solo está la intuición a la hora de realizar el análisis del propio algoritmo.

El conteo visto se puede emplear para estimar la cantidad de recursos que un algoritmo consume; pero el objetivo no sólo es conocer dicha cantidad, sino,
más aún, poder comparar el comportamiento de distintos algoritmos, con el fin de decidir cuál de ellos utilizar bajo circunstancias específicas.



Espero llegados aquí, que no os hayáis dormido, porque meviacagarendiosyaeh.
En las próximas partes, me centraré en los distintos tipos de algoritmos para problemas varios así como su diseño.

Ya nos veremos.
No entiendo nada pero tiene pinta de ser la polla
 

AB270

Miembro muy activo
Nodero
Noder
Eeeh esto lo he doy yo y esta muy bien explicado! Tome mi like
 

Rodkaiser

Més que un nodero
Noderador
Nodero
Noder
De locos. Lo guardo para el curso que viene, que me va a hacer falta. Gracias por currártelo tanto
 

Thegjv

Moder fav <3
Noderador
Nodero
Noder
Ver el archivo adjunto 9995

Buenas noders, llorones y otras faunas habitantes en el nodo.

Hoy les vengo a hablar del mundo de la Algoritmia, lo que viene siendo el análisis y estudio de los algoritmos, su eficiencia y la teoría que les rodea.

A la hora de buscar el método para resolver un problema, es decir un algoritmo, es muy importante su diseño y el estudio de la eficiencia que este pueda
tener. Lo primero se refiere a la búsqueda de procedimientos que, con una secuencia finita de instrucciones lleguen a una solución que se adecúe al
dispositivo del que disponemos para trabajar. Lo segundo, hace que podamos dar una medida del coste (ya sea en tiempo o espacio) que consume el
algoritmo para llegar a la solución; de esta forma se pueden comparar y decidir cual es el más adecuado.

En la introducción, voy a centrarme en la medida de la eficiencia de los algoritmos, en las siguientes partes, explicaré las técnicas de diseño y los algoritmos
más frecuentes y conocidos para según qué tipo de problemas. (Ojo cuidao, esto de la eficiencia, se basa en gran medida en las matemáticas, pero el resumen
que haré no se va a adentrar demasiado en ello, puesto que sobaríais muy fuertemente, cosa que seguramente haréis puesto que esta parte es muy teórica).


1. La Eficiencia y la Complejidad

Una vez ya tenemos un algoritmo que funciona correctamente, es necesario definir criterios para medir su rendimiento o comportamiento. Normalmente, dichos
criterios se centran en su simplicidad o en el uso de recursos del computador. Se puede pensar que un algoritmo muy simple no tiene mucha eficiencia, pero hay
ventajas que pueden decantarnos por su uso, como pueden ser la fácil legibilidad del código y su mantenimiento, y por tanto la sencilla forma de medir su
eficiencia; esto hace que en determinados casos sean lo más conveniente.

Con respecto al uso de recursos, este se suele medir en función de: el tiempo que emplea en ejecutarse, y el espacio, es decir, la memoria que emplea para ello. Ambos
son los costes que representa resolver el problema mediante el algoritmos medido. Además, van a ser los parámetros que empleemos para comparar entre algoritmos.

El tiempo de ejecución es una medida que va a depender de muchos factores, demasiados, como son la calidad del código, la carga de trabajo del computador, la
eficiencia y rapidez del compilador, los datos que se maneje, la complejidad intrínseca del algoritmo, etc, por ello hay dos formas de dar esta medida:
  • Una medida teórica (o a priori), que consiste en obtener una función que acote (por arriba o abajo) el tiempo de ejecución para unos valores de entrada dados.
  • Una medida empírica o real (o a posteriori), consistente en medir el tiempo de ejecución para unos valores de entrada dados y un computador concreto.
Ambas medidas son importantes puesto que, si bien la primera nos da una estimación del comportamiento del algoritmo de forma independiente del ordenador en
donde será implementado y sin necesidad de ejecutarlo, la segunda representa las medidas reales del comportamiento del algoritmo. Estas medidas son funciones
temporales de los datos de entrada.

El tamaño de la entrada es el número de componentes sobre el que se ejecuta el algoritmo, por ejemplo, el tamaño de un vector a ordenar o el de unas matrices que
vayamos a multiplicar.

La unidad de tiempo a la que deben de hacer referencia estas medidas de eficiencia no puede ser expresada en segundos o en otra unidad de tiempo concreta,
pues no existe un ordenador estándar al que puedan hacer referencia. Denotaremos por T ( n ) el tiempo de ejecución de un algoritmo para una entrada de tamaño n,
y si nos centramos en el uso espacial, denotamos con E ( n ) la cantidad de memoria necesaria para un algoritmo dada una entrada de tamaño n.


2. Conteo de Operaciones

El análisis temporal (y el espacial) se hará únicamente con base al algoritmo escrito en pseudocódigo. Como el pseudocódigo no se puede ejecutar para medir la
cantidad de tiempo que consume, la complejidad temporal no se expresará en unidades de tiempo, sino en términos de la cantidad de operaciones que realiza para la
ejecución del algoritmo. El tiempo de ejecución de un algoritmo va a ser una función que mide el número de operaciones elementales (las que el ordenador realiza en
un tiempo acotado) que realiza para un tamaño de entrada dado.

Consideraremos operaciones elementales (contabilizándolas como 1 operación elemental en la medida teórica) las siguientes:
  • Operaciones aritméticas básicas.​
  • Asignaciones a variables de tipo predefinido.​
  • Saltos:​
    • Llamadas a funciones o procedimientos.​
    • Retorno desde funciones o procedimientos.​

  • Comparaciones lógicas.​
  • Accesos a estructuras indexadas básicas (vectores, matrices, arrays, etc).​
Dado un algoritmo, se pueden determinar qué tipos de operaciones utiliza y cuántas veces las ejecuta para una entrada específica.

La reglas generales para el cálculo de operaciones elementales (siempre considerando el peor caso), definen el número de operaciones elementales de cada estructura
básica del lenguaje. El número total de un algoritmo se calcula por inducción sobre ellas. Considerando que el tiempo de una operación elemental, por definición, es
de orden 1. Las reglas son (algunas reglas contienen tipos de sentencias en pseudocódigo):
  1. El tiempo de ejecución de una secuencia consecutiva de instrucciones se calcula sumando los tiempos de ejecución de cada una de las instrucciones.
  2. El tiempo de ejecución de la sentencia del tipo: “caso E sea v1:S1 | v2:S2 | ... | vn:Sn | otro S0 fcaso” (sentencia switch) es T = T(E) + max{T(S1),T(S2),...,T(Sn)}, donde T(E) incluye el tiempo de comparación con v1, v2 , ..., vn.
  3. El tiempo de ejecución de la sentencia “Si C entonces S1 otro S2 fsi” es T = T(C) + max{T(S1),T(S2)}.
  4. El tiempo de ejecución del bucle “mientras C hacer S fmientras” es T = T(C) + (nº iteraciones)*(T(S) + T(C)), tanto T(C) como T(S) pueden variar en cada iteración, y por tanto habrá que tenerlo en cuenta para su cálculo. Para calcular el tiempo de ejecución del resto de sentencias iterativas (PARA,REPETIR) basta expresarlas como un bucle MIENTRAS.
  5. El tiempo de ejecución de una llamada a un procedimiento o función F(P1, P2, ... , Pn) es 1 (por la llamada), más el tiempo de evaluación de los parámetros P1, P2, ... , Pn, más el tiempo que tarde en ejecutarse F, esto es, T = 1 + T(P1) + T(P2) + ... + T(Pn) + T(F).
  6. El tiempo de ejecución de las llamadas a procedimientos recursivos da lugar a ecuaciones en recurrencia (cosa que lo mismo es un poco más complicado y no voy a explicar).
En general, es posible realizar el estudio de la complejidad de un algoritmo sólo en base a un conjunto reducido de sentencias (se le denomina operación básica),
aquellas que caracterizan que el algoritmo sea lento o rápido en el sentido que nos interesa.
Resumiendo, el análisis de un algoritmo se puede hacer considerando sólo aquella operación que cumpla los siguientes criterios:
  • Debe estar relacionada con el tipo de problema que se resuelve.
  • Debe ejecutarse un número de veces cuyo modelo de crecimiento sea similar al del número total de operaciones que efectúa el algoritmo.
Si ninguna de las operaciones encontradas cumple los dos criterios, es posible declinar el primero. Si aun así no es posible encontrar una operación representativa,
se debe hacer un análisis global, contando todas las operaciones y utilizando las reglas que hemos visto antes (lo cual no mola).


3. Instancias

En la teoría de algoritmos es muy frecuente usar el término instancia para indicar un caso específico de un problema. Así, por ejemplo, si el problema es la multiplicación
de 2 enteros positivos una instancia es el par de números a multiplicar 7 y 8. Si ponemos un ejemplo para el caso del cálculo de la eficiencia de un algoritmo de ordenación
que tenga una complejidad lineal, una instancia podría ser el conjunto de enteros a ordenar {2, 4, 6, -1, 76, -53, 89, 291}, lo cual haría que su función de complejidad temporal
tuviera esta forma T ( 8 ).


4. Casos peor, mejor y medio

Se definen:
  • I ( n ) = { I1, I2, I3, ... , Ik } como el conjunto de instancias del problema de tamaño n.
  • O ( n ) = { O1, O2, O3, ... , Ok } como el conjunto formado por el número de operaciones que un algoritmo realiza para resolver cada instancia.
  • Oj es el nº operaciones ejecutadas para resolver la instancia Ij para 1 ≤ j ≤ k.
  • Se distinguen tres casos en el valor de la función complejidad temporal:
    • Caso Peor : T ( n ) = máx ( { O1, O2, O3, ... , Ok } ).
    • Caso Mejor : T ( n ) = mín ( { O1, O2, O3, ... , Ok } ).
    • Caso Medio : T ( n ) = Σi=1^k ( Oi · P(i) ), donde P(i) es la probabilidad de que ocurra la instancia Ii. (Lo del principio es un sumatorio desde i = 1 hasta k).
El mejor caso se presenta cuando para una entrada de tamaño n; el algoritmo ejecuta el mínimo número posible de operaciones, el peor caso cuando
hace el máximo número posible de operaciones. En el caso medio se consideran todos los casos posibles para calcular el promedio de las operaciones
que se hacen teniendo en cuenta la probabilidad de que ocurra cada instancia.

Los casos en la función complejidad espacial, se pueden definir análogamente, considerando en vez de O ( n ) el conjunto C ( n ) como el conjunto formado
por el número de celdas de memoria (unidad teórica para medir el espacio utilizado en memoria) utilizadas por el algoritmo para resolver cada instancia del problema.

Es importante mencionar que no todos los algoritmos presentan casos, y resulta interesante tener una herramienta para detectar cuándo se particionará el
análisis en casos; de momento, solo está la intuición a la hora de realizar el análisis del propio algoritmo.

El conteo visto se puede emplear para estimar la cantidad de recursos que un algoritmo consume; pero el objetivo no sólo es conocer dicha cantidad, sino,
más aún, poder comparar el comportamiento de distintos algoritmos, con el fin de decidir cuál de ellos utilizar bajo circunstancias específicas.



Espero llegados aquí, que no os hayáis dormido, porque meviacagarendiosyaeh.
En las próximas partes, me centraré en los distintos tipos de algoritmos para problemas varios así como su diseño.

Ya nos veremos.
Has vuelto a hacer de las tuyas ❤️
 
  • Like
Reacciones : Dark

Dark

🔥root313🔥
Staff
Moderador
Paladín de Nodo
Jinete de Nodo
Burgués de Nodo
Noderador
Nodero
Noder Pro
Noder
UP, esperando la 2da parte @Valeo08