Estos hechos han dado lugar al desarrollo de dos direcciones en el estudio de los algoritmos: el diseño (determinar los procedimientos adecuados para resolver el problema con el agente de cómputo de que disponemos) y la teoría de la complejidad algorítmica (estudio de la eficiencia, costo en tiempo y recursos con que el agente de cómputo ejecuta un algoritmo que resuelve el problema).
En principio, dado un problema puede determinarse un algoritmo que lo resuelva, si este puede ser formulado de manera lógica, tal que el agente de cómputo sea capaz de comprenderlo y controlar su ejecución paso a paso. Un algoritmo responde a la ecuación ALGORITMO = LOGICA + CONTROL. ésta es una idea importante, según la cual la tarea fundamental del programador es formular lógica y apropiadamente el problema para que la solución sea buscada mediante un algoritmo.
¿Cómo debe el programador formular el problema? Esta es realmente una tarea de gran complejidad, siendo necesario realizar investigaciones teóricas y experimentales que permitan desarrollar metodologías y formalismos para enfrentar con éxito problemas de gran importancia práctica.
I.2 Los alfabetos, las palabras, los lenguajes:
La información se transmite por los canales mediante palabras (sucesión finita de elementos de un alfabeto:conjunto finito no vacío de símbolos). El número de símbolos de la información se llama longitud de la información.
Ejemplo 1: Como alfabeto podemos tener el sistema decimal D, sistema binario B, los alfabetos de los distintos idiomas en que nos comunicamos.
D = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; B = {0, 1}
Palabras representadas mediante los elementos de los alfabetos D y B:
wD = 21654, wB = 0101.
Dado un alfabeto A = {a1, a2,…, an}, denotemos por W(A) el conjunto de todas las palabras formadas con los elementos de A. W(A) es un conjunto infinito numerable, es decir existe una biyeccion entre W(A) y el conjunto de los números naturales (N).
Sea w una palabra no vacía (las palabras vacías son asociadas con el cero), tal que w€W(A), numeremos la posición de cada carácter (símbolo) de w comenzando por la derecha, 0, 1, 2,…; entonces si el carácter ar de w se encuentra en la posición s le asignamos un peso igual a r x ks, por k tomamos el numero de elementos del alfabeto (por ejemplo para el alfabeto D, k = 10; para B, k = 2), r expresa el cardinal del símbolo del alfabeto. Entonces a w le corresponde un número natural que es igual a la suma de los pesos de los caracteres que lo componen. Esta correspondencia se llama numeración k-ádica.
Ejemplo 2:
Sea B = {a1, a2} un alfabeto, donde, a1=0, a2=1; r = {r1, r2} = {1,2}, sea w = 0101 una palabra formada por los caracteres del alfabeto B. Numeremos los caracteres de w con los números enteros no negativos (comenzando por el cero), de derecha a izquierda, s = {s3, s2, s1,s0} = {3, 2, 1, 0}.
Determinemos el número natural que le corresponde a la palabra w, es decir, la numeración 2-ádica para la palabra w:
r1xkS3 + r2xkS2 + r1xkS1 + r2xkS0 =1×23+ 2×22+ 1×2+ 2×20=20.
La numeración k-adica asocia a cada palabra un único número entero no negativo, lo que, la hace diferente a la representación usual en la base k (por ejemplo en la base usual 2 las palabras 0101 y 101 responden ambas al número 5).
0101=0x23+ 1×22+ 0x2+ 1×20=5
101=1×22+ 0x2+ 1×20=5
El conjunto de las palabras definidas sobre un alfabeto se llama lenguaje sobre este alfabeto. Dado un alfabeto A, sobre el pueden definirse como lenguajes particulares: el vacío O, que no contiene palabra alguna, y W(A), el lenguaje completo, que contiene todas las posibles palabras sobre A.
Dado un conjunto discreto de símbolos no vacío M, una representación de M sobre el alfabeto A, es una función inyectiva R: M ® W(A), que asocia a cada símbolo s€M una palabras w€W(A). La función R asocia al conjunto M el lenguaje LM sobre A, es decir, LM = Im(R) Í W(A),
LM= {w: w€W(A) y w =R(s) para algún s€M}
Ahora podemos dar una definición rigurosa (formal) de algoritmo:
Definición 1: Un algoritmo A no es más que una terna (M; LM; gL), donde M es un conjunto discreto no vacío de símbolos, LM Í W(A), un lenguaje asociado a M, gL: LM ® LM una función que transforma las palabras w€LM en otras palabras de LM.
En otras palabras, el algoritmo proporciona al agente de cómputo un método sistemático (función) que transforma las palabras w€LM en otras palabras de LM.
I.3 Requisitos básicos de los algoritmos:
El requisito básico que debe cumplir un algoritmo, es que el mismo debe ser eficaz, las reglas deben ejecutarse de modo preciso sin ambigüedades.
Asumamos que existe algún agente de cómputo eficaz, es decir, su tarea es realizada mediante un número finito de pasos elementales (instrucciones), en un tiempo prudencial. El procedimiento de cómputo a ejecutar por el agente de cómputo puede contener cualquier número de instrucciones, pero siempre tiene que ser una sucesión finita, que proporcione una notación formal conveniente, mostrando de forma precisa las instrucciones que el agente de cómputo debe ejecutar, y en que orden deben realizarse. La sucesión de instrucciones del procedimiento de cómputo puede depender de los datos de la entrada, según las reglas especificadas; pero nunca se determinarán de manera aleatoria o arbitraria. No se definirá a priori límite en el tamaño de los datos de la entrada e intermedios a procesar, así como de los resultados. Sólo requeriremos que todos sean finitos. En resumen todos los elementos del procedimiento de cómputo (datos, sucesión de instrucciones) a ejecutar por el agente de cómputo tienen que ser finitas.
Como hemos planteado los algoritmos deben ser escritos de forma clara, sin ambigüedades, para que los mismos sean ejecutados de manera eficaz por el agente de cómputo. mputoue los mismos sean ejecutados por el agente de come forma clara ebe ejecutar e los caracteres
Cualquiera que sea la representación que se adopte para escribir un algoritmo, la misma debe cumplir los requisitos siguientes:
a) El algoritmo debe ser comprensible para el agente de cómputo
b) La longitud del algoritmo es finita.
c) Cada paso del algoritmo indica una operación, ejecutable sin ambigüedad en un tiempo finito.
d) El algoritmo recibe los datos de entrada, los procesa y produce los resultados como datos de salida.
e) El algoritmo debe terminar para todos los datos de entrada aceptados, en un tiempo finito.
En la práctica, la condición de terminación no es suficiente, para definir cuan eficaz es un algoritmo, la eficacia de un algoritmo significa que el agente de cómputo transforma los valores de la data inicial haciendo uso de los recursos y el tiempo de ejecución de forma eficaz, hasta obtener los valores de la data final.
I.4 Estructuras de los algoritmos:
La representación (escritura) de los algoritmos está directamente relacionada con el agente de cómputo que va a ejecutarlo: gráfico, seudo-código, lenguaje de programación, etc. Nosotros emplearemos el seudo-código, una representación intermedia entre el lenguaje natural y los leguajes de programación, este queda definido por un sistema de reglas (instrucciones) para la escritura de los algoritmos.
Las instrucciones definen la unidad estructural, designa un paso del tratamiento o la representación de la información de cualquier algoritmo.
Como se ha expresado, al ejecutar un algoritmo, este transforma los valores de algunas magnitudes (vamos a considerar la magnitudes definidas en el conjunto de los números reales), con las cuales opera el algoritmo. Estas magnitudes tienen un nombre identificador: secuencia de símbolos que comienza con una letra que las identifica. Las magnitudes se clasifican en constantes y variables (simples y dimensionales). Los valores de las constantes permanecen invariables, mientas que los valores de las variables cambian. El valor de una variable se puede cambiar con ayuda de una instrucción de asignación,
[identificador] = [expresión]
[expresión] define una función o constante
Ejemplo 3: Perímetro de un triángulo dados sus lados.
P = a +b +c
P = 20
A la variable puede asignarse un valor con ayuda de la instrucción de entrada que transmite el valor de las variables a partir de cierta fuente exterior.
Entrada [variable 1], [ variable 2], [ variable 3]
Ejemplo 4:
Entrada a, b, c
También existe la instrucción análoga de salida.
Salida [variable 1], [ variable 2], [ variable 3]
Ejemplo 5:
Salida P
Un elemento útil es el uso de comentarios dentro del algoritmo,
// [ comentario]
Ejemplo 6: Calcular el perímetro de un triángulo, dado sus lados:
//Cálculo el perímetro de un triángulo.
Entrada a, b, c // lados del triángulo
P = a + b + c
Salida P // perímetro de un triángulo
//Fin del algoritmo
Analicemos ahora el siguiente problema: Dados los lados de un triángulo, se desea clasificarlo en: equilátero, isósceles, escaleno.
Como es conocido un triángulo solamente admite una clasificación de acuerdo a la dimensión de sus lados, por lo que estamos en presencia de la selección de alternativas: Un triángulo se define como equilátero si la dimensión de sus lados son iguales, es decir, a = b = c, por la propiedad de transitividad
a = c; un triángulo es isósceles si dos de sus lados son iguales, es decir, a = b o b = c o a = c; es escaleno si sus lados son diferentes a ≠ b y b ≠c y a ≠ c.
Para expresar la anterior situación se emplea la instrucción de bifurcación (condicional), la cual efectúa la elección de las instrucciones a ejecutar en función del cumplimiento de un conjunto de condiciones (en general estos pueden ser relaciones de orden (≤, ≥, <, >, ≠, =) unidos con los operadores lógicos: y, o, no), como se expresa a continuación,
Si [relación de oprden1] (operador lógico) [ relación de orden 2]
Entonces
[ instrucción 1]
[ instrucción 2]
:
Sino
[ instrucción 1],
[ instrucción 2]
:
Fin Si
Cuando se ejecuta la instrucciones de bifurcación se realiza solamente un bloque de instrucciones: si las condiciones se cumplen se ejecutan las instrucciones que aparecen después de la palabra reservada Entonces, en caso de no cumplirse la condición se ejecutan las instrucciones que aparecen después de la palabra reservada Sino. Dentro de las instrucciones pueden aparecer otras instrucciones de bifurcación, como se presenta en el ejemplo siguiente.
Ejemplo 7: Dados los lados de un triángulo se desea clasificarlo en: equilátero, isósceles, escaleno.
// Clasificar un triángulo en: equilátero, isósceles, escaleno.
Entrada a, b, c // lados del triángulo
Si a = b y b = c
Entonces
Clas = triángulo equilátero
Sino Si a = b o b = c o a = c
Entonces
Clas = triángulo isósceles
Sino
Clas = triángulo escaleno
Fin Si
Fin Si
Salida Clas // clasificación del triángulo.
//Fin del algoritmo
Veamos una nueva situación:
Se tiene un conjunto que contiene los lados de n triángulos, se desea conocer cuantos triángulos equiláteros, isósceles y escalenos contiene el conjunto.
Hasta el momento fuimos capaces de clasificar un triángulo dado sus lados. La nueva situación nos presenta un conjunto finito o lista determinada de elementos (se conoce de antemano la cantidad de elementos que la componen).
Lo anterior puede ser representado de la forma siguiente: sea un conjunto finito T, cuyos elementos son ternas (vectores de R3),
T= { (a1, b1, c1), (a2, b2, c2),…, (an, bn, cn) }
Para resolver el problema planteado definiremos la instrucción de iteración (repetitiva o cíclica) con contador:
Para [ contador]=[ valor inicial] hasta [ valor final] (paso)
[ instrucción 1]
[ instrucción 2]
:
Próximo [ nuevo valor del contador]
El contador toma un valor inicial y se ejecutan las instrucciones que se encuentra entre las palabras reservadas Para-Próximo (ciclo). Al llegar a la palabra reservada Próximo el contador se incrementa de acuerdo al valor del paso (cuando no se define se asume como 1). Este proceso se repita hasta que el contador alcance el valor final.
Ejemplo 8: Se desea conocer cuantos triángulos equiláteros, isósceles y escalenos, contiene un conjunto de n triángulos.
// Determinar total de triángulos equiláteros, isósceles y escalenos
Entrada n // total de triángulos a clasificar
CEQ = 0, CES = 0, CIS = 0 // valores iniciales de los contadores
Para I =1 hasta n
Entrada a, b, c // lados del triángulo
Si a = b y b = c
Entonces
Clas = triángulo equilátero
CEQ = CEQ +1
Sino Si a = b o b = c o a = c
Entonces
Clas = triángulo isósceles
CIS= CIS+1
Sino
Clas = triángulo escaleno
CES = CES +1
Fin Si
Fin Si
Salida Clas // clasificación del triángulo.
Próximo I
Salida CEQ, CIS, CES // total de triángulos equiláteros, isósceles y escalenos
//Fin del algoritmo
Hay problemas en que se desconoce el tamaño de la lista (lista indeterminada) que va hacer procesada, solamente se conoce una condición que determina el final de la lista (último elemento). En estos casos es necesario emplear la instrucción de iteración con condición
Mientras [relación de orden1] (operador lógico) [ relación de orden 2]
[ instrucción 1]
[ instrucción 2]
:
Fin Mientras
Al principio se prueba la condición que aparece después de la palabra reservada Mientras, si esta se satisface se ejecutan las instrucciones que se encuentran entre las palabras reservadas Mientras-Fin Mientras (ciclo), estas se van a repetir hasta que la condición deje de satisfacerse. Para esto es necesario que las instrucciones que se ejecutan dentro del ciclo influyan en la condición.
Ejemplo 9: Se tiene un conjunto finito triángulos, se conoce que el último triangulo es escaleno y las dimensiones de sus lados son: a = 27.5, b = 12.2,
c =32. Determine cuantos triángulos equiláteros, isósceles y escalenos, contiene el conjunto.
// Determinar total de triángulos equiláteros, isósceles y escalenos
CEQ = 0, CES = 0, CIS = 0 // valores iniciales de los contadores
Entrada a, b, c // lados del triángulo
Mientras a ≠ 27.5 y b ≠12.2 y c ≠ 32
Si a = b y b = c
Entonces
Clas = triángulo equilátero
CEQ = CEQ +1
Sino Si a = b o b = c o a = c
Entonces
Clas = triángulo isósceles
CIS= CIS+1
Sino
Clas = triángulo escaleno
CES = CES +1
Fin Si
Fin Si
Salida Clas // clasificación del triángulo.
Entrada a, b, c
Fin Mientras
Salida CEQ, CIS, CES +1 // total de triángulos equiláteros, isósceles y escalenos
//Fin del algoritmo
No es difícil ver que una lista determinada puede ser tratada con la instrucción iterativa condicionada, como se muestra a continuación.
Retomemos el problema del ejemplo 8, y escribamos el algoritmo empleando la instrucción iterativa condicionada.
// Determinar total de triángulos equiláteros, isósceles y escalenos
Entrada n // total de triángulos a clasificar
CEQ = 0, CES = 0, CIS = 0 // valores iniciales de los contadores
I = 0 // valor inicial para el contador del ciclo
Mientras I ≠ n
Entrada a, b, c // lados del triángulo
Si a = b y b = c
Entonces
Clas = triángulo equilátero
CEQ = CEQ +1
Sino Si a = b o b = c o a = c
Entonces
Clas = triángulo isósceles
CIS= CIS+1
Sino
Clas = triángulo escaleno
CES = CES +1
Fin Si
Fin Si
I = I + 1
Fin Mientras
Salida Clas // clasificación del triángulo.
Salida CEQ, CIS, CES // total de triángulos equiláteros, isósceles y escalenos
//Fin del algoritmo
I.4.1 Variables dimensionales (arreglos). Algoritmos subor-dinados.
Las variables dimensionales (variables con índices, ejemplo: A(I), B(I, J)), describen las estructuras compuestas de un conjunto de elementos ordenados conforme al valor de los índices, es decir, la posición de los elementos queda definida por los valores de los índices. Las variables dimensionales tienen sus antecedentes en los entes matemáticos, los vectores y las matrices.
A diferencia de las variables simples (cada variable simple almacena un sólo valor), las variables con un índice A(I), almacenan tantos valores como el valor máximo que toma el índice (en el caso de la variable bidimensional B(I; J) estas almacenan un número de elementos igual al producto de los máximos valores de los índices).
En la generalidad de los casos se conoce el máximo valor de los índices, siendo muy usada la instrucción iterativa con contador para operar con las variables con índices (lo anterior no significa que no sea utilizada la instrucción iterativa con condición).
Ejemplo 10: Determinar la suma de todos los elementos positivos de una matriz n x n.
// Suma de los elementos positivos de una matriz.
Entrar n // número de filas y columnas de la matriz
Sum = 0 //valor inicial de la suma
Para I =1 hasta n // inicio del ciclo para el índice de las filas
Para J =1 hasta n // inicio del ciclo para el índice de las columnas
Entrar A(I ;J) // entrada de los elementos de la matriz por filas
Si A(I ;J) > 0
Entonces
Sum = Sum +A(I ;J)
Fin Si
Próximo J // próximo valor del índice por las columnas
Próximo I // próximo valor del índice por las filas
Salida Sum //valor final de la suma
//Fin del algoritmo
Mostraremos ahora como realizar el algoritmo anterior, si se emplea la instrucción iterativa condicional para definir el ciclo,
// Suma de los elementos positivos de una matriz.
Entrar n // número de filas y columnas de la matriz
Sum = 0 //valor inicial de la suma
I = 1, J = 1 // valores iniciales de los índices de las columnas y las filas
Mientras I ≠ N
Mientras J ≠ N
Entrar A(I ;J) // entrada de los elementos de la matriz por filas
Si A(I ;J) > 0
Entonces
Sum = Sum +A(I ;J)
Fin Si
J =J +1
Fin Mientras
I = I +1
Fin Mientras
Salida Sum //valor final de la suma
//Fin del algoritmo
Con frecuencia al desarrollar un algoritmo, resulta posible aprovechar los algoritmos elaborados antes. De tal modo al construir el algoritmo, habitualmente se trata de dividir todo el problema en subproblemas más simples, y si para algún subproblema ya existe el algoritmo, éste puede incluirse en el algoritmo en desarrollo. Esto permite no repetir el trabajo ya realizado, economizar el tiempo.
Los algoritmos acabados, incluidos por completo en el algoritmo que se elabora, se llaman algoritmos auxiliares o subordinados, y el algoritmo en que ellos se incorporan se llama algoritmo principal o fundamental.
El empleo de los algoritmos subordinados provoca la necesidad de formalizarlos de modo especial para poder invocarlos en el algoritmo principal, para llamar un algoritmo subordinado desde el algoritmo principal, nosotros utilizaremos la instrucción de llamada al algoritmo subordinado,
Llamada [nombre] [ (Lista de parámetros) ]
La ejecución de la instrucción de llamada al algoritmo subordinado equivale a la ejecución del algoritmo subordinado. Luego de la palabra reservada Llamada se escribe un nombre el cual identifica al algoritmo subordinado, la lista de parámetros entre paréntesis, separados por comas, indicándose el nombre de los parámetros de entrada y salida (los parámetros que son transferidos desde el algoritmo principal al algoritmo subordinado, y los resultados que se obtienen en el algoritmo subordinado y son transferidos al algoritmo principal), estos deben aparecer en el mismo orden. Los algoritmos subordinados se escriben al final del algoritmo principal y su nombre tiene que coincidir con el nombre que aparece en la instrucción de llamada al algoritmo subordinado, a continuación la lista de de parámetros entre paréntesis separados por coma en el mismo orden en que aparecen la llamada.
Ejemplo 11: Dado un conjunto de n triángulos, se desea conocer:
a) El valor máximo de la sucesión de perímetros.
b) Cuantos triángulos equiláteros, isósceles y escalenos contiene el conjunto.
// Algoritmo Principal Triángulos
Entrada n // total de triángulos
CEQ = 0, CES = 0, CIS = 0 // valores iniciales de los contadores
Max = 0 ,P = 0 //valor inicial del perímetro máximo, y el perímetro
Para I =1 hasta n
Entrada a, b, c // lados del triángulo
Llamada CalPer (a, b, c, P)
Llamada MaxPer (P, Max)
Llamada ConTipoTrian (a, b, c, CEQ, CES, CIS)
Próximo I
Salida Max //valor del perímetro máximo
Salida CEQ, CIS, CES // total de triángulos equiláteros, isósceles y escalenos
//Fin del Algoritmo Principal
//Algoritmo Auxiliar Calculo Perímetro
CalPer (a, b, c, P)
P = a + b + c
//Fin Algoritmo Auxiliar
//Algoritmo Auxiliar Máximo
MaxPer (P, Max)
Si P > Max
Entonces
Max = P
Fin Si
//Fin Algoritmo Auxiliar
//Algoritmo Auxiliar Contar tipo de triángulo
ConTipoTrian (a, b, c, CEQ, CES, CIS)
Si a = b y b = c
Entonces
CEQ = CEQ +1
Sino Si a = b o b = c o a = c
Entonces
CIS= CIS+1
Sino
CES = CES +1
Fin Si
Fin Si
//Fin Algoritmo Auxiliar
La forma de escribir los algoritmos diseñando el algoritmo principal y los algoritmos auxiliares, es conocida como diseño estructurado (modular) y más que una técnica de diseño constituye una filosofía de programación.
I.4.2 Algoritmos recursivos y Algoritmos de ordenamiento:
Un algoritmo recursivo es aquel que contiene un procedimiento recursivo, un procedimiento recursivo queda definido mediante una función recursiva.
La teoría de las funciones recursivas fue desarrollada a finales de la primera mitad del siglo pasado.
Vamos a considerar funciones de argumentos de la forma:
,
donde denota el conjunto de los números naturales. Intuitivamente, una función computable (o calculable) es una función numérica cuyo valor puede ser hallado mediante algún algoritmo.
Analicemos el caso particular . Supongamos que su valor se halla a través del siguiente esquema de cálculo:
Definición 2: Una función numérica cuyo valor se calcula con ayuda de un esquema de cálculo recursivo, se llama función primitiva recursiva.
Ejemplos 12:
1. 
Podemos apreciar que 
, 
, …, 
. Así, por inducción se establece que 
– suma de dos números naturales.
2. 
Tenemos que 
, 
, …, 
. Por tanto, 
– producto de dos números naturales.
3. Introduzcamos la operación de diferencia truncada:
Mostremos que esta función es primitiva recursiva. Primero vamos a probar que 
es primitiva recursiva. De hecho,
A seguir, es fácil ver que:
De forma general, la recursividad es un método de definir una función mediante el cual para una cantidad arbitraria de argumentos, un valor de ella se calcula por medio de un esquema determinado a través de los valores de la función ya conocidos o calculados anteriormente. Así obtenemos:
En resumen, un procedimiento recursivo es aquel, en el cual una función se llama a sí. La recursividad es una forma poderosa, elegante y natural de resolver una amplia clase de problemas.
El factorial de un número n€N se define como,
Es decir si n ³1, n! es igual al producto de todos los enteros entre 1 y n.
Por ejemplo 5!= 5 4 3 2 1=120
Observemos que n! puede escribirse en términos de sí mismo pues si quitamos n, el producto restante es tan solo (n-1)!, es decir,
n! = n (n-1) (n-2)…2 1= n (n-1)!
Por ejemplo 5!= 5 4!
La ecuación n! = n (n-1)!, muestra como descomponer el problema original (calcular n!) en subproblemas cada vez más sencillos (calcular (n-1)!, calcular (n-2)!…). Al final las soluciones de cada subproblema se combinan (multiplicando) para resolver el problema original.
Por ejemplo el problema 5! se reduce a calcular 4!; el problema 4! se reduce a calcular 3!; el problema 3! se reduce a calcular 2!; el problema 2! se reduce a calcular 1! y el problema 1! se reduce a calcular 0! Que por definición es 1.
Una vez que el problema original se ha reducido a resolver subproblemas, la solución del subproblema más sencillo puede utilizarse para resolver el siguiente subproblema más sencillo, y así sucesivamente, hasta lograr la solución del problema original .
Por ejemplo 5!,
0! = 1
1!=1 0!=1
2!=2 1!=2
3!=3 2!=3 2=6
4!=4 3!=4 6=24
5!=5 4!=5 24=120
Ahora escribiremos un algoritmo para el calculo del factorial, esto no es más que una traducción de la ecuación n! = n (n-1)!.
Para definir un procedimiento recursivo utilizaremos la instrucción,
Procedimiento [nombre] [ (Lista de parámetros) ]
Ejemplo 13:
// Calculo del factorial con recursividad.
Entrar n
Procedimiento factorial (n)
Si n = 0 entonces
Fac.= 1
Sino
Fac = (n factorial(n-1))
Fin Si
Salida Fac.
Consideremos n = 3, como 3 es distinto de 0, la ejecución va a la línea debajo de la palabra reservada Sino, sustituye a n por 3 y llama al procedimiento factorial para el valor n=2, de forma análoga el procedimiento se ejecuta hasta obtener Fac = (3 2 1 factorial (0)), se verifica la condición, por lo que factorial (0) retorna el valor Fac =1.
Teorema 1: El algoritmo anterior produce como salida el valor de n!,
Demostración (Por inducción matemática):
Paso base (n = 0). Ya hemos observado que para n = 0, el algoritmo produce como salida el valor 1.
Paso inductivo. Supongamos que el algoritmo produce correctamente el valor para (n -1)!, n > 0. Ahora supongamos que n es la entrada del algoritmo. Como n ¹ 0, al ejecutar el algoritmo vamos a la línea debajo de la palabra reservada Sino. Por la hipótesis de inducción el procedimiento calcula correctamente el valor (n -1)!. En la línea debajo de la palabra Sino el procedimiento calcula correctamente (n -1)! n = n!
Por tanto el algoritmo produce como salida el valor de n! para cada entero
n ³ 0.
Deben existir ciertas situaciones en las que un procedimiento recursivo no se llama a sí mismo, en caso contrario se llamaría a si mismo por siempre. En el algoritmo anterior, si n = 0, el procedimiento no se llama a sí mismo. Los valores para los que un procedimiento recursivo no se llama a sí mismo son los casos bases. Todo procedimiento recursivo debe tener casos bases para lograr que el procedimiento recursivo concluya.
La inducción matemática nos ha permitido demostrar que un algoritmo recursivo calcula el valor que afirma calcular. Con frecuencia, una demostración por inducción matemática puede considerarse un algoritmo, donde el paso base de inducción corresponde a los casos base de un procedimiento recursivo, y el paso inductivo corresponde a la parte donde el procedimiento recursivo se llama a sí mismo.
Un problema clásico solucionado con la implementación de algoritmos es el siguiente: Dado un conjunto (lista) de n elementos {a1, a2,…, an} y una relación de orden (≤) sobre ellos se desea obtener los elementos ordenados de forma creciente (decreciente).
La idea general del ordenamiento consiste en encontrar una permutación que ordene los elementos de la lista. Varios factores pueden influir al ordenar una lista: tipo y tamaño de los elementos, la distribución de los elementos en la lista, el agente de cómputo en donde se encuentran almacenados.
Existen distintos algoritmos, con distintos ordenes de eficiencia, que resuelven el problema de ordenar los elementos de una lista, aquí nos limitaremos a presentar sólo dos de ellos:
Algoritmo de ordenación secuencial: Este algoritmo ordena los elementos de la lista en orden creciente (decreciente). La idea del algoritmo consiste en realizar permutaciones de forma secuencial comenzando por el primer elemento de la lista, por ejemplo: sea la lista {7, 8, 3, 5}, ordenémosla de menor a mayor, tomamos el primer elemento y lo comparamos con los restantes elementos permutándolos cuando sea necesario, obtenemos la lista {3, 8, 7, 5}, tomamos el segundo lo comparamos con los restantes elementos y permutamos cuando es necesario, obtenemos {3, 5, 8, 7}, se continua el proceso hasta obtener la lista ordenada {3, 5, 7, 8}.
Ejemplo 14:
// Ordenar de menor a mayor
Entrar n //tamaño de la lista
Para I =1 hasta n
Entrar A (I) //elementos de la lista
Próximo I
//ordenamiento secuencial
Para I =1 hasta n-1
Para J = 2 hasta n
Si A(I) > A(J) entonces
Tem = A(J)
A(J)=A(I) //permutación de los elementos
A(I) = Tem
Fin Si
Próximo J
Próximo I
Para I =1 hasta n
Salida A(I) // lista ordenada de menor a mayor
Próximo I
// Fin del algoritmo
Algoritmo de ordenación burbuja: El nombre de este algoritmo trata de reflejar cómo el elemento mínimo "sube", a modo de burbuja hasta el principio de la lista, consiste en recorrer los elementos de la lista tomados los dos consecutivos siempre en la misma dirección, comenzando por el último elemento de la lista intercambiando elementos si fuera necesario, por ejemplo, sea la lista {7, 8, 3, 5}, ordenémosla de menor a mayor, tomamos el último elemento y lo comparamos con el anterior, luego el anterior con el siguiente en la misma dirección continuamos el proceso y obtenemos {3, 7, 8, 5}, a esta nueva lista le realizamos de nuevo el procedimiento anterior, obtenemos la lista ordenada {3, 5, 7, 8}.
Ejemplo 15:
// Ordenar de menor a mayor
Entrar n //tamaño de la lista
Para I =1 hasta n
Entrar A(I) //elementos de la lista
Próximo I
//ordenamiento burbuja
Para I =1 hasta n-1
Para J = n hasta I +1 paso -1
Si A(J-1) > A(J) entonces
Tem = A(J)
A(J)=A(J-1) //permutación de los elementos
A(J-1) = Tem
Fin Si
Próximo J
Próximo I
// Fin ordenamiento burbuja
Para I =1 hasta n
Salida A(I) // lista ordenada de menor a mayor
Próximo I
// Fin del algoritmo
Ejercicios para el trabajo independiente:
Escribir un algoritmo para calcular:
1. El valor de la función G(y ,z)= y2 + Exp (z/2), donde y =2×2+ x + 1,
z = (x2 +y2)1/2.
2. La función:
3. El valor de la función H (y ,z) = Ln (y2 ) – 1/ z1/2., donde y =2×2+ x,
z = x +y.
4. Dados tres ángulos se desea determinar:
a) Si estos ángulos pueden determinar un triángulo.
b) Si el triángulo es rectángulo, acutángulo o obtusángulo.
c) El mayor lado del triangulo.
d) La diferencia entre la suma de los ángulos interiores y los ángulos exteriores.
Escriba un algoritmo.
5. Dados los valores de verdad de las preposiciones simples p , q. Determine el valor de verdad de las proposiciones compuestas:
a) p y q (p^q)
b) p o q (pvq),
Nota: 1 (verdadero), 0 (falso)
p | Q | p^q | pvq |
1 | 1 | 1 | 1 |
1 | 0 | 0 | 1 |
0 | 1 | 0 | 1 |
0 | 0 | 0 | 0 |
Escriba un algoritmo.
6. Dada una sucesión (lista) de n números reales. Escriba un algoritmo para:
a) Calcular la suma de los elementos de la sucesión.
b) Determinar el mayor y el menor elemento de la sucesión.
c) Determinar cuantos elementos son mayores que la suma.
7. Escriba un algoritmo para determinar la factorial de un entero no negativo n.
Nota: Escriba un algoritmo donde se emplee la instrucción iterativa con contador y otro donde emplee la instrucción iterativa con condición, para definir el ciclo.
8. Escriba un algoritmo para determinar el mayor y menor elemento de las sumas parciales de una sucesión de n números reales.
9. Escriba un algoritmo para determinar el mayor y menor elemento de las sumas consecutivas de una sucesión de n números reales.
10. Escriba un algoritmo para determinar el máximo común divisor (MCD) de dos enteros no negativos.
11. Dadas dos sucesiones de n números naturales. Escriba un algoritmo para calcular el número de pares de números, correspondiente a cada sucesión, múltiplos entre si.
12. Escriba un algoritmo para contar las consonantes de una frase que contiene 20 caracteres.
13. Escriba un algoritmo para contar las vocales de una frase que culmina con el caracter *.
14. Sea un conjunto cuyos elementos son las palabras del idioma español formadas por 5 caracteres, cuya última palabra es cinco. Escriba un algoritmo para:
a) Determinar cuantas palabras comienzan con vocal y cuantas comienzan con consonante.
b) Calcular el número de vocales de cada palabra.
c) Calcular el total de consonantes del conjunto.
15. Escriba un algoritmo para determinar cuantos números enteros existen en el intervalo [1; 1000], que sólo son divisibles por tres números enteros distintos.
16. Dada una matriz de dimensión n x n. Escriba un algoritmo que:
a) Encuentre el mayor elemento de cada columna.
b) Encuentre el menor elemento de cada fila.
c) Calcule: la suma de los elementos no negativos de la diagonal principal y producto de los elementos negativos de la diagonal principal.
d) Calcule la factorial de la suma de los elementos no negativos.
Nota: 1. Escriba un algoritmo donde se emplee la instrucción iterativa con contador y otro donde emplee la instrucción iterativa con condición, para definir el ciclo y las variables indexadas.
2. Escriba el algoritmo empleando algoritmos auxiliares.
17. Para los ejercicios 6, 8, 9, 11, 13, 14, 15 escriba un algoritmo estructurado, empleando arreglos.
18. Escriba el algoritmo estructurado, empleando arreglos para calcular:
, para todo n, m que pertenecen a los naturales.
19. Escriba un algoritmo donde se implemente un procedimiento recursivo para los ejercicios:7 , 10 y 18.
20. Un robot puede dar pasos de 1 o 2 metros. Escribir un algoritmo para el cálculo del número de formas en que el robot puede recorrer n metros.
21. Escriba los algoritmos de ordenamiento para ordenar una lista de mayor a menor. Impleméntelos utilizando instrucción iterativa con condición.
Análisis de los algoritmos
II.1 Complejidad Computacional:
Cada programador desea escribir el algoritmo o programa más eficaz para el problema que desea resolver. Tal acercamiento nos conlleva a pensar, ¿qué hace que un algoritmo sea difícil de ejecutar por un agente de cómputo?, esto es lo que de forma intuitiva se define como complejidad computacional. Lo anterior nos lleva a definir criterios para medir la eficiencia del algoritmo. Como eficiente puede entenderse el algoritmo o programa que minimiza los recursos que emplea el agente de cómputo para lograr la solución del problema planteado, es decir, el problema radica en minimizar ciertas función de costo, por ejemplo, el tamaño del programa, el número de pasos a ejecutar por el agente de computo, la economía de la memoria, la velocidad de ejecución, la simplicidad de su implementación, etc.
Ejemplo 16. Para resolver el sistema de ecuaciones algebraicas lineales 
de orden 
con ayuda de la regla de Cramer se necesitan hallar las componentes del vector 
como la relación de determinantes: 
, para 
. Si se calculan los determinantes directamente a partir de su definición, es necesario realizar 
multiplicaciones y 
sumas. Supongamos que para los cálculos empleamos un agente de cómputo que realiza 
multiplicaciones por segundo, y que queremos resolver un sistema con 
incógnitas (bien pequeño para los que surgen en aplicaciones prácticas). Entonces el cálculo de un solo determinante necesita 
multiplicaciones, y por tanto, para hallar la solución se requiere aproximadamente de 10 años de trabajo continuo del agente de cómputo. Por otro lado, para la solución de este mismo sistema en la misma máquina usando el método de Gauss, sólo se necesitan 
. Esto indica que como algoritmo de cálculo, la regla de Cramer no debe ser tomada en consideración.
Ejemplo 17. Supongamos que se necesita calcular 
, donde 
es un número natural. El cálculo de esta magnitud usando multiplicaciones sucesivas por exige que se realicen 
operaciones de multiplicación. No es difícil convencerse de que este método no es el más efectivo. Por ejemplo, 
puede hallarse realizando no 63, sino sólo 6 operaciones de multiplicación, si de manera sucesiva elevamos al cuadrado y calculamos 
, 
, 
, 
, 
, . En general, representamos como potencias de 2:
,
donde 
es un número estándar para cada agente de cómputo, y 
son cifras binarias. Entonces
.
Note que en estos productos solamente debemos considerar aquellos factores para los cuales 
, o sea, cuando 
. Un algoritmo basado en la descomposición anterior se llama algoritmo binario. Este permite hallar en a lo sumo 
operaciones de multiplicación.
Otra medida de la eficiencia de un algoritmo es la exactitud, lo cual significa que un algoritmo de cálculo debe ser capaz de proporcionar una solución del problema con una exactitud 
dada o adecuada para el problema en cuestión.
Dos direcciones pueden adoptarse para evaluar la complejidad de un algoritmo:
En la primera, nos preocupamos por la complejidad estática de un algoritmo, relacionada con la complejidad del texto del algoritmo (por ejemplo, su longitud, su complejidad estructural, la variedad de tipos de la instrucción usadas en él, etc.). Esta medida de complejidad caracteriza al algoritmo independientemente de los datos de entrada a los que pueden aplicarse el algoritmo. El segundo, nos preocupamos por la complejidad dinámica, está relacionado con el uso de los recursos requeridos por el agente de cómputo para llevar a fin la ejecución del algoritmo para una entrada determinada de datos (por ejemplo, tiempo para su ejecución, memoria, etc.
La complejidad (estática y dinámica) de un algoritmo depende de varios elementos: el formalismo con que es expresado el algoritmo, el agente de cómputo que lo ejecuta, y el criterio para evaluar su eficacia.
Las dos direcciones, estática o dinámica, pueden ser usadas para escoger el algoritmo menos complejo entre dos o más algoritmos equivalentes que resuelven el mismo problema. Lo anterior impone evaluar la complejidad intrínseca del problema a solucionar. Esto nos conlleva a considerar todos los algoritmos que resuelven el problema dado, y evaluar la complejidad entre ellos para obtener el menos complejo.
Claro, evaluar la complejidad intrínseca de un problema es en general una tarea difícil, porque puede existir un gran número de algoritmos equivalentes diferentes que resuelven el problema dado. En general la complejidad de un algoritmo sólo es determinada de manera aproximada, por medio de acotaciones (una cota superior y una cota inferior). Dos estrategias pueden seguirse para obtener una aproximación más fina de la complejidad de un algoritmo. La primera consiste en disminuir la cota superior, la otra aumentar la cota inferior.
Un rasgo muy importante para la teoría de la complejidad es lograr estudios generales, independientes del agente de cómputo que ejecutará el algoritmo, lo anterior no minimiza la importancia de obtener medidas de complejidad específicas al agente de cómputo que ejecuta el algoritmo.
II.1.1 Axiomas de Blum.
El estudio de la complejidad abstracta proporciona resultados que se sostienen para cualquier agente de cómputo, y cualquier criterio para evaluar el costo de la ejecución del algoritmo. Esta generalidad tiene algunas desventajas, pues se obtienen en algunos casos resultados paradójicos, pues no se consideran algunos elementos específicos del agente de cómputo.
Considere la lista de todos los agentes de cómputo (M1,M2,…), y correspondientemente, una lista (T1(n),T2(n),…) de las funciones para evaluar el costo de ejecución de cada agente, Tk(n) es una función definida en los naturales (Tk: N–>N), la cual indica el costo de ejecución del agente Mk para una entrada n. Es decir, la función Tk(n) puede ser considerada como el número de unidades de recurso consumidos en la ejecución por el agente de cómputu Mk para una entrada n (Mk(n)).
La lista (T1(n),T2(n),…) proporciona una medida de complejidad si se satisfacen los siguiente dos requisitos (Axiomas de Blum ):
- Para todos los números naturales k y n, Tk(n) esta definida si y sólo si Mk(n) esta definida.
- Existe un algoritmo, que para valores arbitrarios k, n y m, decide si Tk(n)=m o no.
El primer axioma expresa la idea: el costo de ejecución para cualquier algoritmo que es ejecutado hasta el final es calculable, pero debe ser considerado como indefinido el costo de ejecución de los algoritmos cuya ejecución no concluye, el segundo axioma exige la existencia de un procedimiento algorítmico para decidir si una máquina dada Mk, para una entrada dada n, consume m unidades de recurso.
Esto significa que a medida que la ejecución avanza se consumen más unidades del recurso, por consiguiente, para verificar si Tk(n)=m, podemos simplemente observa Mk para la entrada n durante un tiempo finito, esto define el período en que son consumidas las m unidades del recurso. Si Mk se detiene en este período, entonces Tk(n)=m, si Mk se detiene antes, o si continua, entonces Tk(n) es diferente de m, debe notarse que, para el caso contrario, no tendría sentido exigir un algoritmo para decidir si Tk(n)=m, para k, n y m arbitrarios.
Como se ha mostrado, los requisitos de los axiomas anteriores son muy generales, y expresan el deseo de ser satisfechos para cualquier medida de complejidad, por lo que estos no son suficientes, por ejemplo: considerando Tk(n) = Mk(n) para todo n y k, se satisface el axioma 1, sin embargo, el axioma 2 no se satisface, pues no se puede decidir si la máquina concluye la ejecución. Como otro ejemplo, consideremos Tk(n)=0 para todo n y k (es decir la ejecución está libre de costo), el axioma 2 se satisface, pero se viola el axioma 1, porque la lista de todas las máquinas incluye necesariamente algunas que no concluyen la ejecución. Los ejemplos anteriores muestran que los axiomas de Blum pueden satisfacerse independientemente, y por consiguiente estos son independientes.
Como hemos expresado la complejidad de un algoritmo define el uso eficiente de los recursos, por el agente de cómputo para ejecutarlo. Frecuentemente la eficiencia se mide en función de dos parámetros: el tiempo que empleó el agente de cómputo Mk para ejecutar un número finito de pasos para una entrada n Sk(n) y el número de células (espacios de memoria) Ck(n) necesarias que usó el agente de cómputo Mk para la entrada n al ejecutar el algoritmo (medidas de complejidad), es decir, la complejidad temporal y capacitiba. La primera medida Sk(n) parece violar el axioma 1 de Blum, porque un algoritmo que no concluye la ejecución podría usar un número finito bien definido de células (espacios de memoria). Lo anterior se evita al considerar por definición a Ck(n) como indefinido, de esta manera el axioma 1 se satisface y el axioma 2 también es satisfecho en todos los casos, pues podemos decidir si Mk para la entrada n ejecuta el algoritmo, tal que Ck(n)=m para todo k, n y m arbitrario, lo anterior se sustenta en el hecho que hay sólo un número finito de configuraciones de la máquina diferentes de m.
Según lo expresado, una medida de complejidad consiste en asignar una función de costo, para evaluar cómo cada agente de cómputo ejecuta un algoritmo. Diremos, que el agente de cómputo Mr es menos complejo que el agente Ms, respecto ha cierta función T(n) dada, si para todas las entradas suficientemente grande n (de longitud mayor que algún valor dado q), Tr(n) está definida siempre que Ts(n) este definida, y el valor Tr no es mayor que el valor de Ts.
II.2 Complejidad temporal.
El tiempo de ejecución de un algoritmo va a depender de diversos factores: los datos de entrada, las características del agente de cómputo, la complejidad intrínseca del algoritmo. Con el florecer de computadoras a partir de la década 1960-70, la comunidad científica convino que la medida más significativa de la eficacia de un algoritmo es la expresión matemática que define el tiempo de ejecución del algoritmo por el agente de cómputo, la cual se expresa como una función de los datos de entrada T(n), complejidad temporal. T(n) es una función creciente de n.
Es posible realizar el estudio del tiempo de ejecución de las maneras siguientes:
- Consiste en obtener una función que acote (superior e inferiormente) el tiempo de ejecución para unos valores de entrada, esto nos proporciona una medida teórica a priori.
- Medir el tiempo de ejecución en un agente de cómputo especifico para unos valores de entrada dados, esto nos proporciona una medida real a posteriori.
Ambas medidas son importantes, la primera nos ofrece estimaciones del comportamiento del algoritmo de forma independiente del agente de cómputo en el cual será ejecutado, la segunda representa la medida real del comportamiento del algoritmo.
En los algoritmos secuenciales una medida de complejidad temporal viene expresada por el número de operaciones elementales (OE) que realiza cada instrucción del algoritmo a ejecutar por el agente de cómputo para una entrada determinada n, es decir las operaciones que el agente de cómputo ejecuta en un tiempo acotado para la entrada n.
Consideraremos OE:
- Las operaciones aritméticas básicas.
- Las asignaciones a variables.
- Las llamadas y retorno a algoritmos auxiliares.
- Retorno a las instrucciones de inicio de ciclo.
- Las operaciones lógicas (relaciones de orden unidas a los operadores lógicos).
- Variables dimensionales, cada índice de la variable dimensional contabilizará como una OE.
Ejemplo 18: Para el algoritmo del ejemplo 9 calcular el número de OE.
- En la línea (2) se ejecutan 3 OE (asignación).
- En la línea (3) se ejecutan 3 OE (asignación).
- En la línea (4) se ejecutan un total de 5 OE (3 operaciones de relación y 2 operaciones lógicas).
- En la línea (5) se ejecutan 3 OE (2 operaciones de relación y 1 operación lógicas).
- En la línea (7) se ejecutan 1 OE (asignación).
- En la línea (8) se ejecutan 2 OE (un incremento (suma) y una asignación).
- En la línea (9) se ejecutan un total de 5 OE (3 operaciones de relación y 2 operaciones lógicas).
- En la línea (11) se ejecutan 1 OE (asignación).
- En la línea (12) se ejecutan 2 OE (un incremento (suma) y una asignación).
- En la línea (14) se ejecutan 1 OE (asignación).
- En la línea (15) se ejecutan 2 OE (un incremento (suma) y una asignación).
- En la línea (19) se ejecutan 3 OE (asignación).
- En la línea (20) se ejecutan 1 OE (retorno al inicio del ciclo).
- En la línea (21) se ejecutan 1 OE (un incremento (suma)).
Tenemos un total de 33 OE, pero debemos tener presente que las líneas 4 y 20 definen un ciclo, por lo que las operaciones de las líneas (5), (7), (8), (9), (11), (12), (14), (15) y (19) se ejecutaran tantas veces como veces se ejecute el ciclo.
La función temporal T: N–>R+, depende del tamaño de los datos de entrada, por ejemplo: si tenemos que evaluar un polinomio de grado n, multiplicar dos matrices cuadradas de orden n.
Ejemplo 19: Para el algoritmo del ejemplo 18 determinemos una expresión para calcular su tiempo de ejecución.
Como mostramos en el ejemplo 12, el algoritmo realiza 7 OE fuera del ciclo y 26 dentro del ciclo, por tanto T(n) =26 (n -1)+7= 26n -19
T(n) es una función que mide el número de OE de un algoritmo para una entrada n, independiente del agente de cómputo.
Comúnmente para la solución de un problema puede obtenerse dos o más implementaciones de un algoritmo, por lo que es necesario acotar la diferencia que se puede producir entre ellas.
Teorema 2 (Principio de Invarianza):
Sea A un algoritmo y I1 e I2 dos implementaciones que concluyen la ejecución, sean T1(n) y T2(n) el tiempo de ejecución de I1 e I2, entonces E C€R, c > 0 y no€N, tal que "n ³ n0, se verifica que T1(n) ú c T2(n).
Demostración:
Sean dos sucesiones finitas que representan el tiempo de ejecución de cada una de las instrucciones correspondientes a las implementaciones I1 e I2, para la entrada n ³ no, no es un número fijo:
Consideremos 
, i = 1, 2,…,p, j = 1,2,…,q,
,
Denotemos por T1(n) y T2(n) el tiempo total de ejecución de las dos implementaciones, de forma que
Entonces,
Luego,
- Nota: Este teorema fue presentado en el Libro en formato electrónico (Internet). Universidad de Málaga, 1999, sin demostración.
La demostración del mismo es original de los autores de la monografía.
El Principio de Invarianza nos dice que el tiempo de ejecución de dos implementaciones distintas de un algoritmo dado no van diferir más que en una constante multiplicativa.
En otras palabras un algoritmo tarda en su ejecución un tiempo del orden T(n) si existe una constante real c > 0 y una implementación I del mismo que tarda menos que cT(n), para toda entrada de tamaño n.
Es importante tener en cuenta las constantes c y no para las que se verifican las condiciones, pues, por ejemplo, sean dos implementaciones de un algoritmo, tal que T1(n)=105n2 y T2(n)=2n3, el primero sólo será mejor que el segundo para n > 50.000.
II.2.1 Cotas asintóticas de complejidad temporal.
Se desea estimar medidas para el tiempo de ejecución que permitan comparar la eficiencia de los algoritmos, por ejemplo, si determinamos la cota superior del tiempo de ejecución de un algoritmo podemos asegurar que, en ningún caso, el tiempo de ejecución será superior al de la cota.
Definición 3: Sean T1 y T2 funciones de N–>R+. Escribimos T1(n) = O(T2(n)), y diremos que T1(n) es de orden a la sumo de T2(n), si E C1€R, C1 > 0 tal que T1(n) menor o igual C1 T2(n), An€N, excepto para un número finito.
La igualdad T1(n)=O(T2(n)) expresa que T1(n) esta acotada superiormente por T2(n),.excepto para un número finito de excepciones.
,
donde C1 es una constante. El símbolo O(1) denota una función acotada por una constante.
Propiedades de O:
- T1= O(T1(n))
- T1= O(T2(n)) –> O(T1(n)) < O(T2(n))
- O(T1(n)) = O(T2(n)) <–> T1= O(T2(n)) y T2= O(T1(n))
- Si T1(n) = O(T2(n)) y T2(n) = O(T3(n)) –> T1(n) = O(T3(n))
- Si T1(n) = O(T2(n)) y T1(n) = O(T3(n)) –> T1(n) = O(min(T2(n), T3(n))).
- Si T1(n) = O(T2(n)) y T3(n) = O(T4(n)) –> T1(n) +T3(n)= O(max(T2(n), T4(n))).
- Si T1(n) = O(T2(n)) y T3(n) = O(T4(n)) –> T1(n) T3(n)= O(T2(n) T4(n)).
- Si $
, dependiendo de los valores de que tome C1 tenemos:
a) Si C1€(0,Ñ) entonces O(T1(n)) = O(T2(n))
b) Si C1= 0 entonces T1= O(T2(n)) –> O(T1(n)) < O(T2(n))
Definición 4: Sean T1 y T2 funciones de N–>R+. Escribimos T1(n) = W(T2(n)), y diremos que T1(n) es de orden al menos de T2(n), si E C2€R, C2 > 0 tal que T1(n) ³ C2 T2(n), An€N, excepto para un número finito.
La igualdad T1(n)=W(T2(n)) expresa que la función T1(n) esta acotada inferiormente por T2(n), excepto para un número finito de excepciones.
Propiedades de W:
- T1= W (T1(n))
- T1= W (T2(n)) –> W (T1(n)) < W (T2(n))
- W (T1(n)) = W (T2(n)) <–> T1= W (T2(n)) y T2= W (T1(n))
- Si T1(n) = W (T2(n)) y T2(n) = W (T3(n)) –> T1(n) = W (T3(n))
- Si T1(n) = W (T2(n)) y T1(n) = W (T3(n)) –> T1(n) = W (max(T2(n), T3(n))).
- Si T1(n) = W (T2(n)) y T3(n) = W (T4(n)) –> T1(n) +T3(n)= W (T2(n)+ T4(n))).
- Si T1(n) = W (T2(n)) y T3(n) = W (T4(n)) –> T1(n) T3(n)= W (T2(n) T4(n)).
- Si $
, dependiendo de los valores de que tome C2 tenemos:
| Página siguiente |