coste comptacional

Complejidad Computacional

15

CAPÍTULO 2.
COMPLEJIDAD COMPUTACIONAL

La complejidad computacional estudia la eficiencia de los algoritmos
estableciendo su efectividad de acuerdo al tiempo de corrida y al espacio
requerido en la computadora o almacenamiento de datos, ayudando a evaluar
la viabilidad de la implementación práctica en tiempo y costo.
Por otra parte, provee herramientas paraclasificar la dificultad inherente de un
problema, de esta manera se puede conocer previamente si la búsqueda de un
algoritmo eficiente para la solución de dicho problema es posible o no.
Existen problemas que únicamente pueden resolverse utilizando un algoritmo
de tiempo exponencial o incluso, puede ser que no exista algoritmo alguno, por
lo cual, al tener este tipo de información puede optarse por labúsqueda o
aplicación de técnicas heurísticas existentes, que si bien no garantizan una
solución óptima, si pueden proporcionar una buena solución o una aproximada.

2.1.

DEFINICIÓN DE ALGORITMO

Un algoritmo es un procedimiento computacional bien definido, el cual
considera un valor o conjunto de valores como valores de entrada y a través de
una secuencia de instrucciones organizadas produce unvalor o conjunto de
valores de salida, en un tiempo determinado con la finalidad de dar solución a
un problema específico.

Complejidad Computacional

16

Las características principales de un algoritmo son:
Preciso y Definido. Cada paso debe ser definido en forma precisa e indicar el
orden de realización.
Datos de entrada (input). El algoritmo recibe datos iniciales antes de su
ejecución.
Datos desalida (output). El algoritmo tiene una o más salidas, es decir,
datos que tienen una relación específica respecto a los datos de entrada.
Generalidad. Independientemente de las veces que se siga un algoritmo, se
debe obtener el mismo resultado.
Finito. Un algoritmo debe terminar siempre después de un número finito de
pasos.
Al analizar un algoritmo se considera el tiempo de corrida y consiste enel
número de operaciones elementales que ejecuta en cada paso. Dicho análisis se
concentra generalmente en encontrar el peor caso de tiempo de corrida, es
decir, el mayor tiempo que tardaría el algoritmo en obtener los valores de
salida.

2.2.

ANÁLISIS ASINTÓTICO DE LOS ALGORITMOS

El análisis asintótico permite conocer la eficiencia de un algoritmo con base en
el tiempo de corrida cuando eltamaño de los datos de entrada es
suficientemente grande de tal forma que las constantes y los términos de
menor orden no afectan.
Para expresar la tasa de crecimiento de una función se toma en cuenta:

Complejidad Computacional

17

− El término dominante con respecto a n ; y
− Se ignoran las constantes.
Ejemplo:
1) k1n + k2 ∼ n
2) k1nlogn ∼ nlogn
3) k1n2 + k2n + k3 ∼ n2
Este tipo de análisis permitefacilitar la elección del mejor algoritmo entre varios
y, por supuesto, es más conveniente aplicar medidas para la eficiencia que
implementarlo y medir la eficacia después de cada corrida.

2.2.1. NOTACIÓN ASINTÓTICA
Las notaciones para el tiempo de corrida asintótico de un algoritmo se definen
en términos de funciones cuyo dominio es el conjunto de números naturales.
Las notaciones se utilizanpara describir la función del peor caso del tiempo de
corrida, T(n), normalmente definidas en tamaños de entrada enteros.
i. Notación Θ. Dada una función g(n), se denota por Θ(g(n)) al conjunto de
funciones:

Θ(g(n)) = {f(n) : existen las constantes positivas c1, c2, y n0 tales que 0 ≤
c1g(n) ≤ f(n) ≤ c2g(n) para toda n ≥ n0 }
La definición de Θ(g(n)) implica que cada miembro de Θ(g(n)) seaasintóticamente no negativo, es decir, que f(n) es no negativa cuando n sea
suficientemente grande.
Entonces si:

f(n) = Θ(g(n)) sí y solo sí f(n) = O(g(n)) y f(n) = Ω(g(n))

Complejidad Computacional

18

Figura 2.1. f(n) = Θ(g(n))
Fuente: [Misra, 2005]

Ejemplo:
1) k1n2 + k2n + k3 ∈ Θ(n2)
2) n2 / 3 – 3n ∈ Θ(n2)
ii. Notación O. Representa una cota asintótica superior. Sea una función g(n),
se...