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 anterior | Volver al principio del trabajo | Página siguiente  |