Desarrollo-de-contenido-curricular-en-el-tema-de-analisis-y-diseno-de-algoritmos-computacionales

Vista previa del material en texto

Desarrollo de contenido curricular en 
el tema de Análisis y Diseño de 
Algoritmos Computacionales 
 
 
 
 
 
 
 
 
Tesis para obtener el grado de Ingeniero en Computación 
Presenta: José Julián Argil Torres 
Director: M.I. Jorge Valeriano Assem 
 
 
 
 
 
 
 
 
 
UNAM – Dirección General de Bibliotecas 
Tesis Digitales 
Restricciones de uso 
 
DERECHOS RESERVADOS © 
PROHIBIDA SU REPRODUCCIÓN TOTAL O PARCIAL 
 
Todo el material contenido en esta tesis esta protegido por la Ley Federal 
del Derecho de Autor (LFDA) de los Estados Unidos Mexicanos (México). 
El uso de imágenes, fragmentos de videos, y demás material que sea 
objeto de protección de los derechos de autor, será exclusivamente para 
fines educativos e informativos y deberá citar la fuente donde la obtuvo 
mencionando el autor o autores. Cualquier uso distinto como el lucro, 
reproducción, edición o modificación, será perseguido y sancionado por el 
respectivo titular de los Derechos de Autor. 
 
 
 
 
 
A mi madre por acompañarme y enseñarme desde siempre, 
A mi hermano Mateo y mi hermana Sofía, 
A Sol por apoyarme como nadie, 
A Jorge por guiarme, 
A mis compañeros del “Labo” por compartir tantas horas, 
Y a muchos más que han estado y me han ayudado a llegar hasta este momento. 
Desarrollo de contenido curricular en el tema de Análisis y Diseño de Algoritmos 
Computacionales 
 
 
�DICE 
 
CAPÍTULO 1. Introducción………………………………………………………………1 
 
CAPÍTULO 2. Microsoft Visual Studio 2005 y C#............................................................4 
 2.1 Microsoft Visual Studio 2005…………………………………………....5 
 2.1.1 Introducción a Microsoft Visual Studio 2005………….............5 
 2.1.2 Área de trabajo…………………………………………............5 
 2.1.3 Cómo crear un proyecto………………………………………..6 
 2.2 C#...............................................................................................................7 
 2.2.1 ¿Qué es C#?................................................................................7 
 2.2.2 ¿Por qué utilizar C#?...................................................................7 
 2.2.3 .NET Framework 2.0…………………….…………………….8 
 2.2.4 La evolución del .NET Framework……………………………9 
 2.2.5 Arquitectura del .NET Framework…………………………...10 
 2.2.6 Introducción a la programación con C#....................................11 
 
CAPÍTULO 3. Fundamentos de análisis de algoritmos………..………………………31 
 3.1 Algoritmos………………………………………………..…………….32 
 3.1.1 ¿Qué son?..................................................................................32 
 3.1.2 Historia……………………..…………………………………32 
 3.2 Complejidad…………………………...………………………………..33 
 3.2.1 ¿Para qué y por qué?.................................................................33 
 3.2.2 ¿Qué se debe medir?.................................................................33 
 3.2.3 Análisis de complejidad de peor caso…….…………………..34 
 3.2.4 Análisis de complejidad promedio……….…………………..34 
 3.2.5 Ejemplo de análisis de complejidad de peor caso y 
 complejidad promedio…………………….………………….35 
 3.3 Análisis asintótico………………………………………………………36 
 3.3.1 Necesidad…………………………….……………………….36 
 3.3.2 Notaciones Big O, Big Ω y Big Θ……………………………37 
 3.3.3 Big O………………………………………………………….40 
 3.3.4 Propiedades de Big O, Big Ω y Big Θ………………………..45 
 3.3.5 Jerarquía………………………………………………………45 
 3.3.6 Problemas NP-Completos…………………………………….46 
 3.4 Ejemplos………………………………………………………………..48 
 3.4.1 Ciclo…………………………………………………………..48 
 3.4.2 Ciclo anidado…………………………………………………48 
 3.4.3 Ordenamiento por inserción…………………………………..49 
 
CAPÍTULO 4. Principales estrategias de diseño de algoritmos……………………….51 
 4.1 “Divide y vencerás”…………………………………...………………..52 
 4.1.1 Introducción…………………………………………………..52 
 4.1.2 Quicksort……………………………………..……………….53 
 4.1.3 Análisis de peor caso: Quicksort…………….……………….57 
 4.1.4 Análisis de recursividad……………………..………………..58 
Índice 
 
 4.1.5 Análisis de complejidad promedio: Quicksort..………………64 
 4.2 Programación dinámica………………………………...………………66 
 4.2.1 Introducción………………………………….……………….66 
 4.2.2 Fibonacci…………………………………….………………..67 
 4.2.3 Dijkstra……………………………………….……………….69 
 4.3 Algoritmos codiciosos………………………………………………….72 
 4.3.1 Introducción………………………………….……………….72 
 4.3.2 Algoritmo de Kruskal………………………...………………73 
 4.3.3 Algoritmo de Prim…………………………...……………….76 
 4.4 Algoritmos de retroceso………………………………...………………79 
 4.4.1 Introducción…………………………………………………..79 
 4.4.2 Problema de las ocho reinas……………………..……………80 
 
CAPÍTULO 5. Material de apoyo para el profesor, el alumno y desarrollo de 
laboratorios………………………………………….…………………………………….85 
 5.1 Material para el profesor…………………………..……………………86 
 5.2 Material para el alumno…………………………..…………………….88 
 5.3 Desarrollo de los laboratorios……………………..……………………90 
 
CO�CLUSIO�ES…………………………………………………...……………………92 
 
GLOSARIO………………………………………………………….……………………95 
 
BIBLIOGRAFÍA Y MESOGRAFÍA……………………………….………………….101 
 
 
Desarrollo de contenido curricular en el tema de Análisis y Diseño de Algoritmos 
Computacionales 
- 1 - 
 
 
 
 
 
 
CAPÍTULO 1 
 
Introducción 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Introducción - 2 - 
 
A lo largo de la preparación como Ingeniero se nos enseña que para llegar a una solución 
hay que estudiar el problema, quizá exista alguna herramienta que nos sirva para atacarlo, 
entonces deberemos buscarla, cuando la encontremos trataremos de aplicarla, generalmente 
estas herramientas serán matemáticas, esto suena como algo cotidiano cuando trabajamos 
con mecánica o quizá electrónica, ¿pero con la Computación? Generalmente llegamos a 
una solución, ¿pero es la mejor? ¿Podría haber sido mejor? ¿Cómo sabemos si es la mejor o 
por lo menos pretende serlo? Deberemos analizar nuestra solución. 
 
En el capítulo 3 de esta tesis se explorarán algunas de las principales herramientas para el 
análisis de algoritmos, se verá probado que las ciencias básicas son tan básicas en la 
computación como en cualquiera otra de las ramas que se imparten en nuestra facultad. 
 
Después del más reciente análisis que se ha hecho al plan de estudios, se ha decidido que el 
tema de los algoritmos es importante (aunque yo diría vital), para la formación de buenos 
Ingenieros en Computación, es por ello que nació la idea de escribir este trabajo, porque no 
existe tanto material del tema como nos gustaría, y el que hay en su mayoría se encuentra 
en otros idiomas, lo cual los hace inaccesible para algunos, además estos libros en su 
mayoría tratan el tema de los algoritmos desde un enfoque demasiado matemático/teórico 
que bajo ciertas circunstancias asustan al alumno Ingeniero que busca el conocimiento, de 
esta manera comencé a investigar, a aprender y desarrollar una idea y un enfoque, una 
forma de acercar un tema que considero tan importante hacia el resto de mis compañeros. 
 
Este es el principal objetivo, escribir una teoría fundamentada en muchos y diversos libros 
de índoles más bien matemáticas y algunas veces computacionales, pero hacerlo con el 
enfoque que me da la formación de Ingeniero, redactarlo de tal manera que los demás como 
yo podrán entender de que les hablan cuando les dicen “obtén la big o de este algoritmo” y 
sin dudarlo podrán contestar “la obtengo y además sé qué significa el resultado”. 
 
Pero todo este análisis solamente lo podemos aplicar si ya hemos planteado por lo menos 
algún bosquejo de solución, es por ello que decidí incluir también el capítulo 4 para las 
principales estrategias que podemos encontrar para solucionar un mundo de problemas, 
dándoles a todas las estrategias una descripción detallada, y en todos los casos una serie de 
ejemplos desarrollados de diferentes maneras y puestos a prueba bajo las herramientas 
matemáticas que para ese capitulo ya dominaremos. 
 
El capítulo 5 trata sobre un Material para profesor y otro para alumno, quizá sea a travésde 
este capítulos como se llegue a más gente, el Material para el profesor es una serie de 
presentaciones que un instructor podría utilizar para guiar un curso del tema en cuestión, y 
la parte para el alumno es una guía para el que esta escuchando, de tal manera que en todo 
momento pueda adentrarse más en el tema que su profesor le esté presentando. En otras 
palabras el capítulo 5 lleva toda la teoría desarrollada al aula de clase. 
 
El material para ambos (profesor y alumno) se ha separado en módulos, que van desde el 
módulo 0 el cual va de la mano directamente con el capítulo 2 de esta tesis en el cual se 
introduce al lenguaje de programación C# (en ningún momento se pretende que este sea un 
curso del lenguaje sino una breve descripción de la sintaxis que pueda ser suficiente siendo 
que se conoce otro lenguaje similar como puede ser Java o incluso C++) luego el módulo 2 
Desarrollo de contenido curricular en el tema de Análisis y Diseño de Algoritmos 
Computacionales 
- 3 - 
 
y 3 que van emparejados con el capítulo 3, finalmente los módulos 4, 5 y 6 que desarrollan 
a forma de curso el capítulo 4, al final de cada módulo se encuentra un laboratorio, que 
pondrá a prueba al estudiante con un ejercicio que deberá ser resuelto en un lenguaje de alto 
nivel, para este trabajo de tesis se ha escogido C# por las razones que en el capítulo 2 se 
detallan. 
 
El capítulo 5 incluye además el desarrollo o guía de cómo se debe resolver cada uno de los 
laboratorios incluidos al final de cada módulo. 
 
La solución para todos los laboratorios se ha incluido también. 
 
Espero que al final de este trabajo de tesis, la importancia de analizar los algoritmos y de 
utilizar la estrategia adecuada para el problema que se desea solucionar quede clara. 
Microsoft Visual Studio 2005 y C# - 4 - 
 
 
 
 
 
 
CAPÍTULO 2 
 
Microsoft Visual Studio 2005 y C# 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Desarrollo de contenido curricular en el tema de Análisis y Diseño de Algoritmos 
Computacionales 
- 5 - 
 
2.1 Microsoft Visual Studio 2005 [14] 
 
2.1.1 Introducción a Microsoft Visual Studio 2005 
 
Para poder llevar a cabo los ejemplos y ejercicios propuestos, será necesario conocer 
ciertas características básicas del entorno de trabajo, en este caso de Microsoft Visual 
Studio 2005, el cual nos permite crear proyectos sin importar su complejidad o su tipo, 
ya que podemos crear tanto aplicaciones Web, como aplicaciones que correrán sobre 
una plataforma Windows. 
 
Microsoft Visual Studio 2005 no es un lenguaje de programación, es un entorno 
integrado de desarrollo. Por lo tanto es una herramienta que nos facilita el llevar a cabo 
nuestra programación en el lenguaje de nuestra preferencia, siempre y cuando éste se 
encuentre soportado por el .NET Framework. 
 
Visual Studio 2005 identificado en sus orígenes mediante el nombre código “Whidbey” 
(en referencia a la Isla Whidbey) fue oficialmente lanzado en línea en Octubre de 2005, 
solo unas semanas después llegó a las tiendas. Esta es la primera versión en la que 
Microsoft remueve la palabra “.NET” del título de su producto al igual que en todos sus 
productos lanzados en el mismo año, sin embargo el .NET Framework sigue siendo el 
principal objetivo, el cual fue actualizado a la versión 2.0. Visual Studio 2005 es la 
versión 8.0 en la serie de entornos de desarrollo producidos por Microsoft. 
 
Entre varias mejoras, esta nueva versión agrega soporte a desarrollo de aplicaciones 
para 64 bits. Aún cuando el entorno esta disponible únicamente en versiones de 32 bits, 
permite compilaciones para x64 (AMD64 y EM64T) así como para IA-64 (Itanium). 
 
Podemos encontrarlo en diferentes versiones, cada una incorpora más o menos cosas; la 
versión Professional nos sirve para desarrollar aplicaciones Web, aplicaciones para 
dispositivos móviles, para clientes inteligentes o aplicaciones Office, por otro lado 
podemos encontrar las versiones Standard y Express, indicadas para los que se inician 
en la programación, la segunda es además gratuita y se puede descargar desde el sitio 
oficial de Microsoft. [15] 
 
Para el desarrollo de esta tesis se eligió la versión Professional, por lo que las imágenes 
presentadas pueden no ser las mismas que en las demás versiones. 
 
2.1.2 Área de trabajo 
 
Visual Studio 2005 es uno de los entornos de trabajo más intuitivos y robustos que 
podemos encontrar en el mercado; le agrega sencillez a todos los procesos complicados 
y repetitivos de la programación, haciendo que el desarrollador pueda preocuparse 
únicamente por escribir código necesario para llevar a cabo las tareas que requiere su 
aplicación. 
 
En la figura 2.1 podemos observar la pantalla inicial del IDE, en la cual se nos presenta 
del lado derecho una serie de noticias extraídas de la MSDN (Microsoft Developers 
Network por sus siglas en inglés) y del lado izquierdo una lista con los proyectos 
Microsoft Visual Studio 2005 y C# - 6 - 
 
recientes, de tal manera que podemos abrirlos rápido, así como una serie de ayudas para 
comenzar a utilizar el entorno. 
 
 
Figura 2.1 – Microsoft Visual Studio 2005 IDE 
 
Cada uno de los controles presentados en la pantalla tienen asignado un nombre 
significativo y una posición en pantalla la cual podemos modificar para personalizarlo 
de acuerdo a nuestras preferencias. En la parte superior encontramos los menús, 
mediante los cuales podemos crear y modificar las propiedades de nuestros proyectos 
así como del área de trabajo. 
 
2.1.3 Cómo crear un proyecto 
 
Dar clic en el menú File, después en New y posteriormente en Project. Con lo cual 
aparecerá el dialog box de nuevo proyecto (Figura 2.2). 
 
Desarrollo de contenido curricular en el tema de Análisis y Diseño de Algoritmos 
Computacionales 
- 7 - 
 
 
Figura 2.2 – Dialog box 
 
Se puede observar que existe la posibilidad de crear proyectos para 4 lenguajes 
distintos, Visual Basic, Visual C#, Visual J# y Visual C++, todos ellos incorporados en 
la versión Professional de Visual Studio 2005. 
 
Lo que sigue es seleccionar el lenguaje, para esta tesis será Visual C#, y seleccionar el 
tipo de proyecto, que en general se utilizará Windows Application o Console 
Application, pues nos sirven perfectamente para el desarrollo de algoritmos. 
 
Finalmente debe asignarse un nombre a una primer aplicación, una ruta en la cual se 
guardará nuestro trabajo y un nombre a la solución, este último será el nombre del 
contenedor de aplicaciones, esto quiere decir que podemos tener una sola solución y 
trabajar con varias aplicaciones dentro de ella. 
 
2.2 C# [12] 
 
2.2.1 ¿Qué es C#? 
 
C# es un lenguaje simple y moderno de programación orientada a objetos desarrollado 
por Microsoft como parte principal de su plataforma .NET Framework, posteriormente 
este lenguaje fue aprobado como un estándar por ISO y ECMA. 
 
La sintaxis de C# se deriva del lenguaje C/C++ aunque contiene ciertas influencias de 
otros lenguajes como Java o Visual Basic. 
 
2.2.2 ¿Por qué utilizar C#? 
 
Al igual que en el mundo real, en el mundo de la programación existen diferentes 
herramientas, unas mejores que otras para realizar ciertas tareas. Existen lenguajes 
orientados a resolver ciertos problemas en particular; en el caso de los algoritmos, C# es 
una herramienta que nos provee de estructuras básicas, fáciles de programar y 
Microsoft Visual Studio 2005 y C# - 8 - 
 
comprender, así como un entorno de trabajo amigable que nos permite el preocuparnos 
únicamente por nuestro programa. 
 
Es además un lenguaje muy intuitivo y similar a otros lenguajes muy populares como C, 
o Java lo que hace que sea un lenguaje ideal. 
 
2.2.3 .8ET Framework 2.0 [16] 
 
El .NET Framework es un componente que podemos agregar a cualquier sistema 
operativo Windows. En la versión de Windows Vista se incorpora la versión 3.0 de 
forma predeterminada. 
 
La versión 2.0 fue liberada a finalesdel año 2005. Esta mejora al .NET Framework se 
trajo junto con la actualización del IDE, Visual Studio 2005, incluye mejoras tales como 
la incorporación de Generics, que son plantillas como las utilizadas en C++ las cuales 
permiten tener un mejor control en los datos evitando así errores desde la compilación y 
no necesariamente hasta la ejecución de nuestras aplicaciones. 
 
El .NET Framework mediante los namespaces incluidos en la librería de clases y en 
combinación con código producido por nosotros mismos, nos permite encontrar 
soluciones para diferentes problemas de la programación, como son soporte para 
aplicaciones Web, manejo de colecciones, trabajo con fuentes de datos, criptografía, 
comunicaciones mediante redes, expresiones regulares, etc. 
 
Todos los programas escritos para el .NET Framework se ejecutan sobre un entorno de 
software, esto quiere decir que todos los requerimientos que llegue a necesitar la 
aplicación son administrados por otra aplicación de software llamada el CLR, de esta 
manera el desarrollador no tiene que preocuparse de las capacidades o características 
específicas del equipo sobre el cual se ejecutará la aplicación, ya que el CLR hace las 
veces de máquina virtual (Figura 2.3), proveyendo así de portabilidad a todos los 
programas escritos para .NET. Además de esto, el CLR también provee de mecanismos 
de seguridad, manejo de memoria, y una amplia capacidad para manejo de excepciones, 
evitando así los errores críticos de las aplicaciones. 
 
Desarrollo de contenido curricular en el tema de Análisis y Diseño de Algoritmos 
Computacionales 
- 9 - 
 
 
Figura 2.3 – COM vs CLR 
 
En si el .NET Framework es: 
 
• Un entorno de ejecución 
• Un conjunto de bibliotecas de funcionalidad (Class library) 
• De libre distribución 
 
.NET Framework se distribuye en 3 versiones: 
 
• .NET Framework Redistributable Package 
• .NET Framework SDK 
• .NET Compact Framework 
 
2.2.4 La evolución del .8ET Framework [17] 
 
La versión 1.0 del Framework fue liberada a principios del año 2002, e incluía también 
la versión 2002 de Visual Studio, así como varios lenguajes compatibles, como son 
Visual Basic y Visual C#. 
 
La versión 1.1 fue liberada en el año 2003. Esta versión se introdujo junto con el Visual 
Studio 2003, junto con la primer versión del .NET Compact Framework así como junto 
con un nuevo lenguaje llamado Visual J#.NET. 
 
La versión 2.0 del .NET Framework y del .NET Compact Framework fue liberada en el 
año 2005 junto con Visual Studio 2005. 
 
Microsoft Visual Studio 2005 y C# - 10 - 
 
 
Figura 2.4 – Línea del tiempo 
 
 
2.2.5 Arquitectura del .8ET Framework 
 
El .NET Framework esta compuesto de distintas capas (Figura 2.5). 
 
 
Figura 2.5 – Arquitectura 
 
Esta arquitectura se monta sobre la familia de sistemas operativos Windows y sobre los 
servicios COM+. 
 
Visual Studio 6.0 
Visual Basic 
VBA 
Visual FoxPro 
VBScript 
C++ 
J++ 
JScript 
ASP 
Visual Studio .NET 2003 
.NET Framework 1.1 
.NET Compact Framework 
J# 
Visual Studio “Orcas” 
.NET Framework “Orcas” 
.NET Compact Framework “Orcas” 
2000 2001 2002 2003 2004 2005 2006 y más 
Visual Studio 2005 (“Whidbey”) 
.NET Framework 2.0 (“Whidbey”) 
.NET Compact Framework 2.0 (“Whidbey”) 
 
Visual Studio .NET 2002 
.NET Framework 1.0 
Visual Basic .NET 
C# 
Windows COM+ Services 
Common Language Runtime 
Base Class Library 
ADO.NET y XML 
ASP.NET Windows Forms 
Common Language Specification 
VB C++ C# J# + 
.NET Framework 
Redistributable 
.N
E
T 
Fr
a
m
e
w
or
k 
 
S
D
K 
.NET 
Framew
ork 
Class 
Library 
 
 
 
 
 
Desarrollo de contenido curricular en el tema de Análisis y Diseño de Algoritmos 
Computacionales 
- 11 - 
 
En la parte más baja de la arquitetura se sitúa lo que se conoce como el Common 
Language Runtime o CLR por sus siglas en inglés, el cual se encarga como ya se 
mencionó antes de controlar la ejecución de las aplicaciones, por encima del CLR 
hablando de la arquitectura como una serie de capas, se sitúan un conjunto de librerías 
(.NET Framework Class Library), este conjunto de librerías se subdivide a su vez en 4 
subcomponentes principales, el primero de ellos es la Base Class Library o BCL la cual 
contiene funcionalidades comúnmente utilizadas en las aplicaciones, como por ejemplo 
el trabajo con cadenas, programación multihilos, trabajo con matemáticas, manejo de 
colecciones como las pilas o las colas, etc. Después se encuentra ADO.NET el cual nos 
otorga una serie de clases para trabajar con archivos XML o realizar interacciones con 
manejadores de bases de datos relacionales como por ejemplo SQL Server 2005, dentro 
de este conjunto de librerías también encontramos ASP.NET y Windows Forms, el 
primero nos sirve para desarrollar aplicaciones Web y el segundo es una tecnología que 
nos permite desarrollar aplicaciones que se ejecutan directamente en el cliente y por lo 
tanto permiten un entorno mucho más rico y vistoso para el usuario. Finalmente y sobre 
todo esto se sitúan los compiladores y las herramientas de desarrollo para los lenguajes 
.NET. [20] 
 
2.2.6 Introducción a la programación con C# [13] 
 
Para poder comenzar, hay que conocer que tipos de datos podemos utilizar y que tipo de 
valores pueden almacenar, identificar cuales son los posibles nombres que podemos 
asignar a nuestras variables, aprender la sintaxis de las estructuras básicas del lenguaje, 
así como saber de qué partes esta compuesto un programa en C#. 
 
2.2.6.1 Identificar las partes de un programa en C# 
 
En la figura 2.6 se puede observar el código de un programa muy simple. 
 
 
Figura 2.6 – Ejemplo de programación con C# 
 
De la línea 1 a las 3, se localizan las declaraciones de namespaces, hay que recordar que 
el .NET Framework nos da la facilidad de utilizar un conjunto de librerías de clases con 
soluciones a problemas comunes, la manera de acceder a ellas es mediante el uso de la 
palabra reservada using seguida del namespace que deseamos utilizar. 
 
En la línea 5, se encuentra la declaración de un nuevo namespace seguido del nombre 
que deseamos asignarle (identificador), de esta manera nosotros podemos crear nuestros 
Microsoft Visual Studio 2005 y C# - 12 - 
 
propios namespaces e incluso exportarlos para compartirlos o utilizarlos en otros 
programas. 
 
En la línea 6 hay una llave que abre, estas llaves en C# denotan el alcance de una cierta 
estructura, en este caso del namespace, van siempre acompañadas de una llave que 
cierra, en este caso se encuentra en la línea 14. 
 
En la línea 7 se encuentra la declaración de una clase, C# por tratarse de un lenguaje 
orientado a objetos debe contener sus métodos y sus variables dentro de clases. En la 
línea 9 se puede ver un ejemplo de método, en este caso se trata del Main el cual 
representa el punto de entrada del programa, como puede verse esta contenido dentro de 
la clase “Program”. 
 
La línea 11 que se encuentra dentro del método Main, hace una llamada al método 
WriteLine que se encuentra dentro de la clase Console que se encuentra dentro del 
namespace System declarado en las primeras líneas. Este método sirve para arrojar una 
salida a la pantalla. 
 
2.2.6.2 Palabras reservadas e identificadores 
 
En C#, existen 77 palabras o identificadores reservados (Tabla 2.1), esto quiere decir 
que de todos los posibles nombres que podemos utilizar para nuestros propósitos no 
podemos elegir ninguno de estos. Estos identificadores son llamados palabras 
reservadas. 
 
abstract as base bool 
break byte case catch 
char checked class const 
continue decimal default delegate 
do double else enum 
event explicit extern false 
finally fixed float for 
foreach goto if implicit 
in int interface internal 
is lock long namespace 
new null object operator 
out override params private 
protected public readonly ref 
return sbyte sealed shortsizeof stackalloc static string 
struct switch this throw 
true try typeof uint 
ulong unchecked unsafe ushort 
using virtual void volatile 
while 
Tabla 2.1 – Palabras reservadas 
 
El significado y uso de algunas de estas palabras se verá en este capítulo. 
 
 
 
 
 
Desarrollo de contenido curricular en el tema de Análisis y Diseño de Algoritmos 
Computacionales 
- 13 - 
 
2.2.6.3 Declaración y asignación de variables 
 
Los identificadores que podemos asignar a nuestras variables no pueden coincidir con 
una palabra reservada; por otro lado, la sintaxis de C# no nos permite comenzar los 
identificadores con números o caracteres especiales, a excepción del guión bajo. 
 
Las variables son espacios en los cuales almacenamos cosas de un cierto tipo, en C# 
existen diferentes tipos de cosas que podemos almacenar; cuando declaramos una 
variable debemos especificar un tipo de dato. 
 
La sintaxis para declarar variables es: 
 
tipo_de_dato identificador ; 
 
En donde tipo_de_dato debe sustituirse con alguno de los soportados por el .NET 
Framework o por uno creado por nosotros mismos. 
 
Una vez que hemos declarado una variable, podemos proceder a utilizarla, o mejor 
dicho asignarle algún valor para que esta lo almacene. Esto se hace mediante un 
operador, llamado el operador de asignación (Figura 2.7). En la primera línea puede 
verse la declaración de la variable y en la segunda la asignación del literal 5 a la 
variable. Todas las asignaciones en C# se hacen de derecha a izquierda. 
 
1. int variable; 
2. variable = 5; 
Figura 2.7 – Declaración y asignación de una variable 
 
C# contiene una serie de tipos de datos predefinidos llamados tipos de datos primitivos, 
la Tabla 2.2 lista lo más comunes así como los rangos de valores que podemos 
almacenar en ellos: 
Tipo de dato Descripción Tamaño en bits Rango* Ejemplo de uso 
int Todo tipo de 
números enteros 
32 <-> 231 hasta 
231<->1 
int variable; 
variable = 5; 
long Todo tipo de 
números enteros 
64 <->263 hasta 
263<->1 
long variable; 
variable = 5L; 
float Números con 
punto flotante 
32 +-3.4x10
38
 float variable; 
variable = 0.5F; 
double Doble precisión 
con punto flotante 
64 +-1.7x10308 double variable; 
variable = 0.5; 
decimal Valores 
monetarios 
128 28 figuras 
significativas 
decimal variable; 
variable = 0.5M; 
string Secuencia de 
caracteres 
16 bits por 
caracter 
N/A string variable; 
variable = “5”; 
char Un solo caracter 16 0 hasta 216<->1 char variable; 
variable = ‘5’; 
bool Booleanos 8 true o false bool variable; 
variable = true; 
Tabla 2.2 – Tipos de datos primitivos [14] 
* El valor 216 es 32,768; el valor 231 es 2,147,483,648 y el valor 263 es 
9,223,372,036,854,775,808 
 
Microsoft Visual Studio 2005 y C# - 14 - 
 
Una vez que hemos declarado una variable como cualquiera de los tipos de datos 
expuestos en la tabla anterior, antes de poder presentarlo en pantalla o de realizar 
operaciones aritméticas sobre ella, debemos inicializarla, en otras palabras asignarle un 
valor inicial, de lo contrario obtendremos un error en tiempo de compilación. 
 
2.2.6.4 Operaciones aritméticas 
 
En C# están soportadas todas las operaciones aritméticas comunes: 
 
• + suma 
• - resta 
• * multiplicación 
• / división 
• % residuo 
 
A estos símbolos mediante los cuales denotamos las operaciones, los llamamos 
operadores y a los valores que operan los llamamos operandos. 
 
No todos los operadores se pueden utilizar en todos los tipos de datos. Por ejemplo, se 
pueden usar todos los operadores aritméticos en tipos de dato char, int, long, double o 
decimal, pero no todos en tipos string o bool. 
 
 
 
 
Figura 2.8 – Ejemplo de suma 
 
En este caso el operador suma modificaría el valor contenido dentro de variable, 
dejándolo como el resultado de sumar variable más 5, con lo que se obtendría 10. 
 
La precedencia de los operadores en C# sigue las mismas reglas de la aritmética común, 
de tal manera que los operadores *, / y % tienen precedencia sobre + y -. Esto puede 
modificarse mediante el uso de paréntesis. 
 
Existen además lo operadores de incremento y decremento los cuales nos servirán 
únicamente para modificar en 1 el valor de cualquier variable. 
 
• variable++; 
• ++variable; 
• variable--; 
• --variable; 
 
Si el operador se encuentra antes o después indica si el incremento se hará antes o 
después de la lectura de la variable. 
 
Desarrollo de contenido curricular en el tema de Análisis y Diseño de Algoritmos 
Computacionales 
- 15 - 
 
Existen además otros operadores llamados operadores compuestos, la siguiente tabla 
muestra cuales son y cómo funcionan a través de una analogía con los operadores 
aritméticos en su forma común. 
 
Forma común Operador compuesto 
variable = variable + 5; variable += 5; 
variable = variable – 5; variable -= 5; 
variable = variable * 5; variable *= 5; 
variable = variable / 5; variable /= 5; 
variable = variable % 5; variable %= 5; 
 
2.2.6.5 Métodos 
 
• Un método es una secuencia de sentencias/acciones. 
• Cada método tiene un nombre y un cuerpo. 
• El cuerpo del método contiene todas las sentencias que se ejecutan cuando el 
método es utilizado. 
• Los métodos pueden recibir datos para procesar y regresar algún tipo de 
información. 
• C# no soporta métodos globales por lo que todos deben ser escritos dentro de 
una clase. 
 
 
tipoDeDato identificador (Lista de parámetros) 
{ 
 cuerpo del método 
} 
 
Figura 2.9 – Sintaxis básica de un método 
 
1. tipoDeDato debe ser el identificador de algún tipo de dato predefinido, 
especifica además que tipo de información será la que regrese el método. Puede 
ser cualquier tipo como int, string, o si el método no regresará información 
deberá especificarse void. 
2. El identificador del método es mediante el cual lo podremos utilizar. 
3. La lista de parámetros es opcional, y describe los tipos de datos y los valores que 
se le pasan al método. 
4. El cuerpo del método incluye todas las líneas de código que se ejecutan cuando 
el método es llamado. Se delimita por las llaves que abren y cierran { … }. 
 
La manera de regresar información desde un método es mediante la palabra reservada 
return seguida del valor que se desea regresar; el valor debe coincidir con el tipo de dato 
que se especifique en la declaración del método. 
 
Para utilizar un método debemos llamarlo mediante su identificador, y debemos 
especificarle de ser necesario la lista de parámetros que requiera. 
 
 
Microsoft Visual Studio 2005 y C# - 16 - 
 
 
identificador ( Lista de parámetros ) ; 
 
Figura 2.10 – Sintaxis para llamar a un método 
 
2.2.6.6 Operadores relacionales y operadores condicionales lógicos 
 
Sirven para saber si un valor es mayor, menor, igual o diferente que otro del mismo tipo 
mediante la formación de expresiones booleanas. 
 
Operador Significa Ejemplo de expresión Resultado si a=19 
< Menor que a < 19 ; false 
<= Menor o igual que a <= 19; true 
> Mayor que a > 19; false 
>= Mayor o igual que a >= 19; true 
== Igual que a == 19; true 
!= Diferente que a != 19; false 
Tabla 2.3 – Operadores relacionales 
 
Los operadores condicionales lógicos nos sirven para construir expresiones más 
complejas al permitirnos combinar operadores relacionales. Existen dos operadores 
condicionales, el primero de ellos es el operador OR denotado con || y el segundo es el 
operador AND denotado con &&. 
 
2.2.6.7 Estructuras de decisión 
 
a) IF 
 
Se utilizan cuando queremos elegir entre ejecutar diferentes bloques de código 
dependiendo del resultado de una expresión booleana 
 
 
1. ( a != 6) 
2. ( a < 10 ) && (a > 0) 
3. ((a >= b) || (b < 100)) && (a < 10) 
 
Figura 2.11 – Ejemplo de expresiones booleanas 
 
Sintaxis: 
 
if ( Expresión booleana ) 
{ 
 Sentencias que se ejecutarán si la expresión es verdadera 
} 
else 
{ 
 Sentenciasque se ejecutarán si es falsa 
} 
 
Figura 2.12 - Sintaxis básica del IF 
Desarrollo de contenido curricular en el tema de Análisis y Diseño de Algoritmos 
Computacionales 
- 17 - 
 
b) SWITCH 
 
Se utiliza cuando podemos reducir la expresión booleana a una expresión común 
que nos permita decidir entre varios bloques variando únicamente el valor contra 
el cual se hace la comparación. 
 
Sintaxis: 
 
switch ( Expresión de control ) 
{ 
 case expresiónConstante: 
 sentencias; 
 break; 
 case expresiónConstante: 
 sentencias; 
 break; 
 … 
 default: 
 sentencias: 
 break; 
} 
 
Figura 2.13 – Sintaxis básica del SWITCH 
 
• La expresión de control es evaluada una sola vez. 
• Las sentencias que se ejecutan son únicamente las que se encuentren en 
el case cuya “expresión Constante” coincide con el resultado arrojado 
por la expresión de control. 
• Si ninguna de las expresiones constantes tiene un valor igual al de la 
expresión de control, se ejecutan las sentencias que contiene default. 
 
2.2.6.8 Estructuras de iteración 
 
a) WHILE 
 
Esta estructura se puede utilizar para ejecutar una sentencia varias veces, en 
tanto una expresión booleana se cumpla. 
 
Sintaxis: 
 
 
while ( Expresión booleana ) 
{ 
Sentencias 
} 
 
Figura 2.14 – Sintaxis básica del WHILE 
 
La expresión booleana es evaluada y si es verdadera, las sentencias del cuerpo 
son ejecutadas, luego la expresión booleana es evaluada otra vez; si la expresión 
Microsoft Visual Studio 2005 y C# - 18 - 
 
sigue siendo verdadera, el cuerpo se ejecuta hasta que se vuelva a evaluar la 
expresión. Este proceso continúa hasta que la expresión booleana se evalúe falsa, 
entonces el while termina. 
 
b) FOR 
La sentencia for nos permite escribir una versión más formal de while al 
combinar la inicialización de una variable de control, la expresión booleana y la 
actualización de la variable de control en un mismo lugar. 
 
Sintaxis: 
 
 
for ( inicialización; expresión Booleana; actualización) 
{ 
Sentencias 
} 
 
Figura 2.15 – Sintaxis básica del FOR 
 
La inicialización de la variable o variables de control ocurre una sola vez al 
inicio del ciclo for. Si la expresión booleana es evaluada verdadera, las 
sentencias se ejecutan. La variable de control es actualizada antes de que la 
expresión booleana sea reevaluada. Mientras la expresión booleana se mantenga 
verdadera se seguirán ejecutando las sentencias del cuerpo. 
 
c) DO – WHILE 
 
Las estructuras WHILE y FOR evalúan su expresión booleana al inicio del ciclo. 
Esto significa que si la expresión booleana se evalúa falsa desde el principio, el 
cuerpo del ciclo no se ejecuta ni una vez. 
 
La sentencia DO – WHILE es diferente, su expresión booleana es evaluada 
después de la primer iteración, por lo que el cuerpo es ejecutado por lo menos 
una vez. 
 
Sintaxis: 
 
 
do 
{ 
Sentencias; 
} while ( Expresión booleana ); 
 
Figura 2.16 – Sintaxis básica del DO – WHILE 
d) FOREACH 
 
La estructura FOREACH declara una variable de iteración que automáticamente 
toma el valor de cada elemento de un cierto arreglo o contenedor. La sintaxis del 
FOREACH es mucho más declarativa; es decir expresa mucho mejor la 
intención del código a diferencia de un simple FOR. 
Desarrollo de contenido curricular en el tema de Análisis y Diseño de Algoritmos 
Computacionales 
- 19 - 
 
 
La estructura FOREACH es la mejor para iterar a través de arreglos y de 
colecciones. 
 
Sin embargo en algunos casos hay que utilizar un FOR: 
 
• Una estructura FOREACH siempre itera a través de todo el arreglo o 
colección. Si se quiere iterar sobre una porción o pasar sobre ciertos 
elementos, es más fácil utilizar una estructura FOR. 
• Una estructura FOREACH siempre itera desde el índice 0 al índice final. 
Si se quiere iterar de atrás hacia adelante, se necesita un FOR. 
• Si el cuerpo del ciclo necesita conocer el índice del elemento en lugar de 
solo su contenido, se necesita usar un FOR. 
• Si se necesita modificar los elementos del arreglo, se necesita usar un 
FOR. Esto es porque la variable de iteración es solamente una copia del 
valor contenido en el arreglo. 
 
Sintaxis: 
 
 
foreach ( tipo identificador in contenedor ) 
{ 
Sentencias 
} 
 
Figura 2.17 – Sintaxis básica FOREACH 
 
 El tipo de identificador debe ser del mismo que los elementos almacenados en el 
contenedor. Contenedor puede ser por ejemplo un arreglo o una colección. 
 
2.2.6.9 Manejo de errores y excepciones 
 
Es un hecho que las cosas malas suceden. Los errores pueden ocurrir en cualquier 
momento de la ejecución de nuestros programas. Para ello C# incorpora una estructura 
que nos permite probar ciertas líneas de código y si se detecta un error permitirnos 
corregirlo y evitar que se convierta en algo crítico. 
 
Para poder hacer esto, tenemos que hacer básicamente 2 cosas: 
 
• Escribir el código dentro de un bloque try. De esta manera cada línea de 
código dentro del bloque se tratará de ejecutar. 
• Escribir tantos bloques catch como sean necesarios inmediatamente después 
del bloque try para poder interceptar cualquier posible condición de error. 
 
 
 
 
 
 
Microsoft Visual Studio 2005 y C# - 20 - 
 
Sintaxis: 
 
 
try 
{ 
Sentencias a probar/ejecutar 
} 
catch ( Excepción a interceptar ) 
{ 
Corrección del posible error 
} 
catch ( Segunda posible excepción ) 
{ 
Corrección del posible error 
} 
… 
finally 
{ 
Sentencias que siempre se deberán 
ejecutar 
} 
 
Figura 2.18 – Sintaxis básica try – catch 
 
Si se detecta una condición de error en el bloque try, la ejecución del programa salta 
inmediatamente al primer bloque catch cuya excepción coincida con dicha condición. 
 
Cuando el flujo del programa se ve modificado, es obvio que algunas líneas de código 
pueden llegar a no ser ejecutadas, en algunas ocasiones ciertas sentencias son vitales y 
no podemos permitir que no se lleven a cabo, con este propósito se utiliza el bloque 
finally. 
 
 
2.2.6.10 Clases y objetos 
 
Las clases se declaran utilizando la palabra reservada class. 
 
 
class Clase 
{ 
Métodos, propiedades, campos, eventos, delegados, y clases anidadas se 
escriben aquí 
} 
 
Figura 2.19 – Clases 
Una vez que declaramos una clase podemos utilizarla como utilizaríamos cualquier otro 
tipo de dato con la diferencia de que las clases necesitan ser “construidas” mediante el 
uso de la palabra reservada new y la utilización de un constructor. 
 
Dentro de las clases escribiremos todo el código de nuestros programas. 
Desarrollo de contenido curricular en el tema de Análisis y Diseño de Algoritmos 
Computacionales 
- 21 - 
 
 
Los métodos, propiedades, campos y demás contenido de las clases puede estar afectado 
por modificadores de acceso. Estos modificadores permiten o no el acceso a dichos 
elementos desde clases exteriores. Los modificadores de acceso básicos son: 
 
• Public 
• Protected 
• Private 
 
Public provee de la máxima libertad de acceso, mientras que private provee de la 
máxima seguridad. En cuanto a protected se comportará de diferente manera 
dependiendo de si se trata de una clase derivada o no desde la cual se trata de tener 
acceso. Si no se especifica un modificador de acceso, por omisión el compilador tomará 
private. 
 
2.2.6.11 Enumeraciones 
 
Las enumeraciones son un set de constantes en forma de lista. Cada enumeración tiene 
un tipo de dato asociado el cual puede ser cualquier tipo de entero, este sirve como 
índice para acceder a cualquier elemento dentro de la lista. Por omisión el índice se 
almacena en un int y el primer elemento de la lista tiene asociado el índice 0, para cada 
elemento sucesivo el índice se incrementa en 1. 
 
Sintaxis: 
 
 
 
enum identificador 
{ 
Lista de elementos 
} 
 
Figura 2.20 – Sintaxisbásica de enum 
 
La lista de elementos son una serie de literales separados entre si por comas. 
 
Una vez que hemos declarado una enumeración, podemos utilizarla de la misma 
manera que utilizaríamos cualquier otro tipo de dato, por ejemplo un string. Esto 
quiere decir que podemos crear variables del tipo de nuestra enumeración. 
 
 
 
 
 
 
 
 
 
 
 
Microsoft Visual Studio 2005 y C# - 22 - 
 
Ejemplo: 
 
 
Figura 2.21 – Declaración y uso de enumeraciones 
 
Este pedazo de código imprimiría en consola: “SegundoElemento”. 
 
2.2.6.12 Estructuras 
 
Las estructuras tienen una sintaxis muy similar al de las clases. 
 
 
struct identificador 
{ 
Métodos, propiedades, etc. 
} 
 
Figura 2.22 – Estructuras 
 
Las diferencias básicas entre una clase y una estructura son: 
 
• Las estructuras no pueden tener constructores default. 
• En las estructuras si se hace un constructor alternativo, se deben inicializar todos 
los campos. 
• En el caso de las estructuras los campos no pueden ser inicializados desde que 
son declarados. 
 
Para poder utilizar las estructuras, al igual que con las clases se debe crear una variable 
a partir de la estructura y se debe utilizar la palabra reservada new para poder llamar al 
constructor y así inicializar la variable de tipo estructura. 
Desarrollo de contenido curricular en el tema de Análisis y Diseño de Algoritmos 
Computacionales 
- 23 - 
 
 
Ejemplo: 
 
 
Figura 2.23 – Declaración y uso de estructuras 
 
2.2.6.13 Arreglos 
 
Un arreglo es una secuencia no ordenada de elementos. Todos los elementos en el 
arreglo tienen que ser del mismo tipo. Los elementos de un arreglo se ubican en bloques 
contiguos de memoria y son accedidos utilizando un índice de tipo entero. 
 
Para declarar un arreglo se necesita especificar el tipo de dato, seguido de un par de 
paréntesis cuadrados, seguido de un identificador (Figura 2.24). 
 
 
tipoDeDato[ ] identificador ; 
 
Figura 2.24 – Sintaxis básica de un arreglo 
 
Se pueden crear arreglos de estructuras, enumeraciones y clases, no únicamente de tipos 
primitivos. 
 
Para poder utilizar los arreglos, hay que crear después de declarar el identificador una 
instancia mediante el uso de la palabra reservada new. 
 
Microsoft Visual Studio 2005 y C# - 24 - 
 
 
1.tipo[ ] identificador = new tipo[ tamaño del arreglo ]; //unidimensional 
2.tipo[ , ] identificador = new tipo[ tamaño , tamaño ]; //bidimensional 
 
Figura 2.25 – Declaración de arreglos multidimensionales 
 
Los arreglos pueden inicializarse también mediante el uso de enumeraciones sin tener 
que especificar el tamaño: 
 
 
tipo[ ] identificador = {1,2,3,4}; 
 
Figura 2.26 – Definición del arreglo mediante una enumeración 
 
Para acceder un elemento individual de un arreglo, se debe especificar el índice del 
elemento que se requiere entre paréntesis cuadrados. El índice es un valor entero. 
 
• Lectura de un índice del arreglo: 
 
 
int variable; 
variable = arreglo[ índice que se desea leer ] ; 
 
Figura 2.27 – Leyendo del arreglo 
 
• Escritura en un índice del arreglo: 
 
 
int variable = 23; 
arreglo [ índice en el que se desea escribir ] = variable; 
 
Figura 2.28 – Escribiendo en el arreglo 
 
2.2.6.14 Colecciones 
 
Los arreglos son muy útiles, pero tienen limitantes. De cualquier manera, los arreglos 
son solo una manera para almacenar elementos de un mismo tipo. El .NET Framework 
provee de muchas clases que sirven para coleccionar elementos de otras maneras más 
especializadas. Estas clases son llamadas Colecciones, y las podemos encontrar en el 
namespace System.Collections. 
 
Arreglos contra colecciones: 
 
• Un arreglo declara el tipo de los elementos que almacena, una colección no. Esto 
es porque las colecciones almacenan sus elementos como objetos. 
• Una instancia de arreglo tiene un tamaño determinado el cual no puede 
modificarse. Una colección tiene un tamaño dinámico. 
• Un arreglo es una estructura de datos de lectura/escritura (no hay manera de 
crear un arreglo de solo lectura), sin embargo es posible utilizar colecciones en 
un modo de solo lectura utilizando el método ReadOnly. 
Desarrollo de contenido curricular en el tema de Análisis y Diseño de Algoritmos 
Computacionales 
- 25 - 
 
 
 
Existen 5 clases de colecciones muy comunes: 
 
a) ArrayList 
 
Es una clase muy útil para ordenar elementos en forma de arreglo. Sobre todo en 
ocasiones en que un arreglo convencional es muy restrictivo: 
o Si queremos modificar el tamaño del arreglo, tenemos que crear una 
copia. 
o Si queremos remover elementos del arreglo, tenemos que hacer una 
copia de los elementos y luego moverlos todos 1 posición. 
o Si queremos insertar un elemento en el arreglo, debemos mover los 
elementos 1 posición para dejar un espacio libre. 
o Podemos remover elementos de un ArrayList simplemente utilizando el 
método Remove. El ArrayList esta implementado para que 
automáticamente se reordenen sus elementos. 
o Podemos agregar elementos al final del ArrayList, utilizando el método 
Add. El ArrayList modifica automáticamente su tamaño. 
o Podemos insertar elementos a la mitad del arreglo utilizando el método 
Insert. ArrayList modifica su tamaño si es necesario. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Microsoft Visual Studio 2005 y C# - 26 - 
 
Ejemplo: 
 
 
 using System; 
 using System.Collections; //necesario para uso de colecciones 
 … 
 ArrayList numeros = new ArrayList(); //creación del ArrayList 
 … 
 //llenar el ArrayList 
 foreach(int numero in new int[12]{1,2,3,4,5,6,7,8,9,10,11,12}) 
 numeros.Add(numero); 
 … 
 //remover el primer elemento que su valor sea 7 
 numeros.Remove(7); //indice 6 
 //remover el elemento en el índice 6 
 numeros.RemoveAt(6); 
 … 
 //iterar en los 10 elementos restantes 
 for(int i = 0; i != numeros.Count ; i++) 
 { 
 int numero = (int)numeros[i]; //cast de object a int 
 Console.WriteLine(numero); 
 } 
 … 
 //iterar utilizando un foreach 
 foreach (int numero in numeros) //no hace falta un cast 
 Console.WriteLine(numero); 
 
 
Figura 2.29 - ArrayList 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Desarrollo de contenido curricular en el tema de Análisis y Diseño de Algoritmos 
Computacionales 
- 27 - 
 
 
b) Queue 
 
La clase Queue implementa un mecanismo FIFO (first-in first-out). 
 
Un elemento es insertado en la cola en la parte trasera y es removido de la parte 
delantera. 
 
Ejemplo: 
 
 
 using System; 
 using System.Collections; 
 … 
 Queue numeros = new Queue(); 
 … 
 //llenando 
 foreach (int numero in new int[4]{1,2,3,4}) 
 { 
 numeros.Enqueue(numero); 
 Console.WriteLine(numero + “ha entrado a la cola”); 
 } 
 … 
 //iterando para obtener los elementos de la cola 
 foreach(int numero in numeros) 
 { 
 Console.WriteLine(numero); 
 } 
 ... 
 //vaciando la cola 
 while(numeros.Count != 0) 
 { 
 int numero = (int)numeros.Dequeue(); 
 Console.WriteLine(numero + “ha salido de la cola”); 
 } 
 
Figura 2.30 - Queue 
 
 
 
 
 
 
 
 
 
 
 
 
Microsoft Visual Studio 2005 y C# - 28 - 
 
c) Stack 
 
Implementa un mecanismo LIFO (last-in first-out). Un elemento entra al stack 
en la cima (operación push) y la abandona desde la cima (operación pop). 
 
Ejemplo: 
 
 
 using System; 
 using System.Collections; 
 … 
 Stack numeros = new Stack(); 
 … 
 //llenando la pila 
 foreach(int numero in new int[4]{1,2,3,4}) 
 { 
 numeros.Push(numero); 
 Console.WriteLine(numero + “ha entrado a la pila”); 
 } 
 … 
 //iteranco 
 foreach(int numero in numeros) 
 Console.WriteLine(numero); 
 … 
 //vaciando la pila 
 while(numeros.Count != 0) 
 { 
 int numero = (int)numeros.Pop(); 
 Console.WriteLine(numero + “ha salido de la pila”); 
 } 
 
 
Figura 2.31 – Stack 
 
d) Hashtable 
 
Los arreglos y los ArrayList nosproveen una manera de utilizar índices para 
acceder a un elemento. Hay ocasiones en que podemos querer acceder a la 
información de los elementos mediante índices que no sean de tipo int. En otras 
palabras utilizar arreglos asociativos. La clase Hashtable provee de esta 
funcionalidad al mantener internamente dos arreglos de objetos, uno para las 
llaves que se están utilizando como índices y otro para los valores que utilizamos 
para crear otros tipos de índices. 
 
Cuando insertamos un par de llaves en una Hashtable, automáticamente detecta 
que llave pertenece a cada valor, y nos permite recuperar el valor asociado a 
cada llave. Hay algunas consecuencias al utilizar la clase Hashtable: 
 
o No pueden haber llaves duplicadas. 
Desarrollo de contenido curricular en el tema de Análisis y Diseño de Algoritmos 
Computacionales 
- 29 - 
 
o Cuando utilizamos un foreach para iterar en un Hashtable, obtenemos un 
DictionaryEntry. La clase DictionaryEntry provee de acceso a la llave y a 
los valores de los elementos en ambos arreglos, a través de la propiedad 
Key y Value. 
 
 
Ejemplo: 
 
 
 using System; 
 using System.Collections; 
 … 
 Hashtable edades = new Hashtable(); 
 … 
 //llenando 
 edades[“Julian”] = 24; 
 edades[“Sol”] = 20; 
 edades[“Mateo”] = 12; 
 … 
 //iterando utilizando un foreach 
 foreach (DictionaryEntry elemento in edades) 
 { 
 string nombre = (string)elemento.Key; 
 int edad = (int)elemento.Value; 
 Console.WriteLine(“Nombre: {0} Edad: {1}”), nombre, edad; 
 } 
Figura 2.32 – Hashtable 
 
e) SortedList 
 
La clase SortedList es muy similar a la clase Hashtable, ya que permite asociar 
llaves con valores. La principal diferencia es que las llaves del arreglo siempre 
son ordenadas. 
 
Cuando insertamos una llave/valor en una SortedList, la llave es insertada dentro 
del arreglo de llaves en el lugar correcto para mantener así las llaves ordenadas. 
El valor es insertado en el arreglo de valores en el mismo índice. La clase 
SortedList automáticamente asegura que las llaves y los valores estén alineados, 
aún cuando se agregue o remueva elementos. Esto significa que podemos 
insertar llaves/valores en una SortedList en cualquier orden que queramos; y 
ellas siempre serán ordenadas de acuerdo al valor de su llave. 
 
Como la clase Hashtable, una SortedList no puede contener llaves duplicadas. 
Cuando utilizamos un foreach para iterar, recibimos un DictionaryEntry, los 
objetos vendrán ordenados de acuerdo a la propiedad Key 
 
 
 
 
 
Microsoft Visual Studio 2005 y C# - 30 - 
 
Ejemplo: 
 
 
 using System; 
 using System.Collections; 
 … 
 SortedList edades = new SortedList(); 
 … 
 //llenando 
 edades[“Julian”] = 23; 
 edades[“Sol”] = 19; 
 edades[“Mateo”] = 11; 
 … 
 //iterando 
 foreach(DictionaryEntry elemento in edades) 
 { 
 string nombre = (string)elemento.Key; 
 int edad = (int)elemento.Value; 
 Console.WriteLine(“Nombre: {0} Edad: {1}”, nombre, edad); 
 } 
 
 
Figura 2.33 - SortedList 
Desarrollo de contenido curricular en el tema de Análisis y Diseño de Algoritmos 
Computacionales 
- 31 - 
 
 
 
 
 
 
CAPÍTULO 3 
 
Fundamentos de análisis y diseño de 
algoritmos 
 
 
 
 
 
 
 
 
 
 
 
 
Fundamentos de análisis de algoritmos - 32 - 
 
3.1 Algoritmos 
 
3.1.1 ¿Qué son? 
 
Un algoritmo se puede ver como cualquier procedimiento computacional bien definido el 
cual toma uno o varios valores de entrada y produce uno o varios valores de salida. Por lo 
tanto un algoritmo es esa secuencia de pasos computacionales que se tienen que llevar a 
cabo para resolver un problema específico obteniendo una salida a partir de cierta entrada. 
 
De esto deriva, que si un problema puede ser resuelto algorítmicamente, significa que 
podemos escribir un programa de computadora que lo resuelva. 
 
3.1.2 Historia [3] 
 
Los algoritmos se ocupan de cierta manera desde hace más años de los que nos 
imaginamos. Un ejemplo de esto es la evaluación de potencias de un número desconocido 
X, para lo cual hace más de dos mil años se desarrolló un algoritmo que reducía el número 
de cálculos necesarios de forma considerable. Como este ejemplo podemos encontrar 
muchos otros. Sin embargo, hasta antes del siglo XX, el estudio de los algoritmos se había 
hecho de forma muy dispersa, es decir, había mucha gente trabajando pero no se estaba 
desarrollando una teoría general. 
 
En 1834 Charles Babbage ya había concebido pero de forma mecánica el concepto de un 
algoritmo mediante su “Máquina Analítica”. A diferencia de la “Máquina Diferencial” 
creada años antes, su Máquina Analítica pretendía resolver problemas de índoles que no 
fueran solamente cálculos de tablas logarítmicas, es decir, sería una máquina que pudiera 
realizar cualquier tipo de cálculo, convirtiéndose en una máquina de propósito general. 
Esta máquina sería programable mediante tarjetas perforadas, por lo tanto siguiendo la idea 
de un algoritmo, cada tarjeta representaría un paso en la solución de un problema, de tal 
manera que el conjunto de tarjetas para resolver dicho problema representaría un algoritmo 
computacional. 
 
El concepto matemático formal de algoritmo, fue formulado hasta la década de 1930, 
incluso antes de la llegada de las computadoras. Durante este proceso de formalización, se 
trabajó mucho con la definición de que cosas podrían ser resueltas algorítmicamente y que 
cosas no serían posibles. En este proceso, la mayor influencia sobre el desarrollo de las 
teorías algorítmicas vino del matemático inglés Alan Turing, quien describió un modelo 
llamado la Máquina de Turing, en el cual estableció el mecanismo mediante el cual las 
computadoras podrían resolver problemas. Además de esto, Alan Turing también describió 
de forma teórica el paradigma de los programas almacenados, el cual representa la base 
para las computadoras de propósito general de hoy en día. Sin embargo, John von Neumann 
fue quien demostró formalmente la practicidad de introducir las instrucciones y los datos 
que estas procesan en la memoria de una computadora. 
 
Desarrollo de contenido curricular en el tema de Análisis y Diseño de Algoritmos 
Computacionales 
- 33 - 
 
En la actualidad, si se usan los algoritmos apropiados, pueden resolverse problemas que 
alguna vez fueron imposibles. Ejemplos de esto son la robótica y la inteligencia artificial 
que implica, el cómputo gráfico, la solución a grandes problemas mediante sistemas 
computacionales, incluso la comunicación mediante redes implica el uso de los algoritmos 
correctos. 
 
3.2 Complejidad 
 
3.2.1 ¿Para qué y por qué? 
 
Para resolver un problema en particular mediante un algoritmo, la mayoría de las veces, 
sino es que todas, tendremos más de una opción, es decir podremos resolver el problema de 
más de una forma; si podemos analizar estos algoritmos, podremos mejorarlos y en el 
mejor de los casos elegir el que resuelva nuestro problema. 
 
Para analizar los algoritmos, podremos tomar como criterios a medir diferentes cosas, entre 
las cuales vamos a encontrar la complejidad. La complejidad no es más que la medición de 
la cantidad de trabajo que realiza un algoritmo. Existen otros posibles factores que podemos 
medir como por ejemplo el espacio utilizado o la claridad del código. [4] 
 
La complejidad o cantidad de trabajo realizado por un algoritmo, no depende del equipo 
sobre el cual se esté ejecutando, ni del lenguaje sobre el cual se esté programando, por lo 
que para este trabajo, la complejidad es el factor a medir para el análisis de algoritmos. 
 
3.2.2 ¿Qué se debe medir? 
 
Medir la cantidad de trabajo de un algoritmo podría llevar a la idea de que se medirán 
tiempos de ejecución, sin embargo esto no es lo mejor, pues los tiempos de ejecución de un 
cierto programa dependerán en gran medida de la computadora sobre la que estemos 
trabajando además del lenguaje sobre elcual hayamos programado. 
 
Lo que buscamos medir como cantidad de trabajo es aquello que nos sirve como punto de 
comparación entre dos o más algoritmos que realizan la misma tarea, y además que no sea 
dependiente de la computadora o del lenguaje empleado. [4] 
 
Elegiremos como características a medir las operaciones que realiza un cierto algoritmo 
elegido. De todas las operaciones que lleva a cabo, deberemos escoger solamente algunas 
que nos darán pauta para poder llevar a cabo las comparaciones. Por ejemplo, en el caso de 
un algoritmo de búsqueda podríamos elegir como operación la comparación que debe 
realizar dicho algoritmo entre el valor que buscamos y cada posición de la colección de 
elementos. [4] 
 
Sin embargo, la cantidad de trabajo que realiza un algoritmo variará en gran medida de 
acuerdo al tamaño de las entradas que le proporcionemos, por ello es que debemos elegir 
bien las operaciones que utilizaremos para analizar la complejidad. 
Fundamentos de análisis de algoritmos - 34 - 
 
3.2.3 Análisis de complejidad de peor caso 
 
Como ya se mencionó antes, la cantidad de trabajo o complejidad del algoritmo, dependerá 
en gran medida del tamaño de las entradas que le proporcionemos. Es por ello que además 
de las operaciones, debemos saber elegir una medida para el tamaño de las entradas. De 
aquí podemos poner como ejemplo el mismo que antes, si necesitamos realizar una 
búsqueda dentro de una colección, la medida del tamaño debería ser el número de 
elementos de dicha colección. 
 
Teniendo esta información, podremos realizar un primer análisis de algoritmos, el más 
utilizado para esto, es el llamado análisis de complejidad de peor caso porque nos 
proporciona una cota superior del trabajo que realiza el algoritmo. 
 
La definición que utilizaremos para la complejidad de peor caso es el siguiente: 
 
Sea Dn el conjunto de entradas de tamaño n para el problema en consideración, y sea I un 
elemento de Dn. Sea t(I) el número de operaciones seleccionadas que el algoritmo ejecuta 
con la entrada I. Definimos la función W de la siguiente manera: 
 
 
}|)({)( nDIItmáxnW ∈= 
 
Figura 3.1 – Peor caso [3] 
 
Esta función representará el número máximo de operaciones que realiza un algoritmo 
seleccionado para cualquier entrada de tamaño n. 
 
3.2.4 Análisis de complejidad promedio 
 
En algunas ocasiones una mejor medida de complejidad podría ser el trabajo promedio que 
realiza un algoritmo en lugar del peor caso. Esto se hace mediante la siguiente definición: 
 
Sea P(I) la probabilidad de que se presente la entrada I. Entonces, el comportamiento 
promedio del algoritmo será: 
 
 
∑
∈
=
nDI
ItIPnA )()()( 
 
Figura 3.2 – Complejidad promedio [3] 
 
La dificultad del análisis de complejidad promedio esta en el hecho de que se necesita 
utilizar un valor de probabilidad el cual no puede ser calculado de forma analítica como 
sería por ejemplo el valor de t(I). Por lo tanto, el valor que se le asigne a P(I) deberá ser 
supuesto, por ejemplo que todas las entradas tienen la misma probabilidad de aparecer. 
Desarrollo de contenido curricular en el tema de Análisis y Diseño de Algoritmos 
Computacionales 
- 35 - 
 
 
3.2.5 Ejemplo de análisis de complejidad de peor caso y 
complejidad promedio [5] 
 
Tomaremos como ejemplo el de la búsqueda de un cierto elemento dentro de una colección 
que no se encuentra ordenada: 
 
Algoritmo: Búsqueda de forma secuencial 
 
Entrada: arreglo, elementoBuscado 
 
Salida: Verdadero si se encuentra el elemento buscado, Falso si no se encuentra. 
 
 n � Número de elementos que contiene el arreglo 
 for i�0 to n-1 do 
 if elementoBuscado == arreglo en su posición i 
 return Verdadero termina el algorítmo 
 endif 
endfor 
 return Falso termina el algoritmo 
 
 
1. Análisis de complejidad de peor caso: 
 
Para saber cual será el resultado de este análisis elegimos como operación la 
comparación que se realiza dentro del ciclo entre lo que buscamos y cada 
posición dentro del arreglo y como medida de entrada el número de 
elementos del arreglo. Teniendo esto en cuenta, es fácil saber que en el peor 
de los casos el elemento buscado se encontrará al final de dicho arreglo, por 
lo tanto el máximo número de comparaciones que se realizarán será n, es 
decir el número total de elementos. Por lo tanto W(n) = n. 
 
2. Análisis de complejidad promedio 
 
Para llevar a cabo este análisis deberemos tomar en consideración que el 
elemento buscado si se encuentra dentro del arreglo no ordenado. 
 
Recordando la ecuación mencionada para este análisis, deberemos nombrar 
una variable X, la cual nos permitirá realizar la sumatoria desde que X es 0 
hasta n-1 (el tamaño del arreglo menos uno), por lo tanto 0 <= X < n. Para la 
ecuación debemos elegir un valor de probabilidad de éxito, es decir cuál es 
la posibilidad de que se presente el valor buscado, como sabemos que 
nuestra entrada será de tamaño n y asumimos que los valores no se repiten 
dentro del arreglo, la probabilidad será 
n
IP
1
)( = . Finalmente el número de 
Fundamentos de análisis de algoritmos - 36 - 
 
operaciones que se realizarán, será t(I) = i+1, puesto que el máximo valor de 
i será n-1, sin embargo el número de operaciones será n = i + 1. 
 
De esto deriva que: 
 
∑
−
=
=
1
0
)()()(
n
i
ItIPnA 
 
Sustituyendo P(I) y t(I) tenemos que: 
 
 
∑
−
=
+=
1
0
)1(
1
)(
n
i
i
n
nA 
 
De esto, sabemos que 
n
1
 es una constante, por lo que podemos sacarlo de la 
sumatoria, y además sabemos que: 
 
2
)1(
1
+
=∑
=
nn
i
n
i
 
 
Por lo que podemos aplicarlo para: 
 
∑
−
=
+
1
0
1
n
i
i 
 
De tal manera que obtenemos: 
 





 +=
2
)1(1
)(
nn
n
nA 
 
Finalmente: 
 
2
1
)(
+
=
n
nA 
 
3.3 Análisis asintótico 
 
3.3.1 3ecesidad 
 
Medir la cantidad de operaciones realizadas nos permite distinguir entre dos algoritmos 
siempre y cuando las cantidades sean drásticamente diferentes. Sin embargo, si dos 
algoritmos parecen realizar el mismo número de operaciones, será necesario hacer un 
Desarrollo de contenido curricular en el tema de Análisis y Diseño de Algoritmos 
Computacionales 
- 37 - 
 
análisis un poco más completo, es decir tendremos que compararlos de tal manera que solo 
tomemos en cuenta las entradas grandes. Al establecer esto, y siguiendo con la notación 
antes utilizada, querrá decir que lo que nos importará será n, es decir nos fijaremos en el 
orden de las funciones con las cuales estemos trabajando y dejaremos de lado cualquier otro 
término que no cambie de forma sustancial la magnitud de dicha función. [2] 
 
De esta manera podremos tener como resultado otra función, la cual nos dará de forma 
aproximada la eficiencia de la función original, sin embargo para nosotros este aproximado 
será suficiente cuando estemos trabajando con entradas grandes, como se estableció 
anteriormente. A esta medida de eficiencia bajo estas condiciones, se le llama Análisis 
Asintótico de Complejidad. 
 
Ejemplo: 
 
Sea 000,000,1000,10)( 3 ++= nnnf 
 
Para n = 10, evaluando 
 
000,000,1000,100000,1000,000,1)10(000,1010)10( 3 ++=++=f 
 
Se puede observar que para valores pequeños de n, la constante 1,000,000 es el valor más 
grande de la función. 
 
Para n = 100, evaluando 
 
000,000,1000,000,1000,000,1000,000,1)100(000,10100)100( 3 ++=++=f 
 
Se puede observar que en algún momento los 3 términos tiene el mismo valor y por lo tanto 
contribuyen de igual manera a la función. 
 
Para n = 1000, evaluado 
 
000,000,1000,000,10000,000,000,1000,000,1)000,1(000,10000,1)000,1( 3 ++=++=f 
 
Cuando el valor de n comienza a ser grande, la contribución que realizan el segundo y 
tercer término a la función comienza a ser mucho menor que el que realiza el primer 
término, esto es debido al crecimiento cúbico que tiene n
3
. De tal manera que el único 
término que nos interesaría para entradas grandes sería elprimero. 
 
3.3.2 3otaciones Big O, Big Ω y Big Θ [5] 
 
Cuando de hacer análisis asintótico se trata, se utilizan básicamente tres notaciones: 
 
• Big O 
o O(g) son todas aquellas funciones que no crecen más rápidamente que g 
Fundamentos de análisis de algoritmos - 38 - 
 
• Big Ω 
o Ω(g) son todas aquellas funciones que crecen por lo menos tan rápidamente 
como g 
• Big Θ 
o Θ(g) son todas aquellas funciones que crecen tan rápidamente como g, es 
decir la intersección entre Big O y Big Ω 
 
Para definir cada una de estas notaciones, tendremos que establecer que el orden de las 
funciones esta restringido únicamente a valores reales *:)( R�nf → en donde N es el 
conjunto de los naturales con ,...}2,1,0{=� y R* es el conjunto de los números reales no 
negativos, de tal manera que existe un entero n0 (que depende de f) tal que 0)( >nf para 
todos los 0nn > . Denotaremos como F a todo el conjunto de funciones que cumplan con 
lo anterior. 
 
• Definición de O(g): 
 
Sea una función Fng ∈)( , definimos ))(( ngO como el conjunto de todas las 
funciones Fnf ∈)( que tienen la propiedad de que para una constante real c y una 
constante entera no negativa n0, y para todo 0nn ≥ , 
 
).()( ncgnf ≤ 
 
 
 
Figura 3.3 – O(g) [3] 
Si ))(()( ngOnf ∈ entonces )(nf es Big O de )(ng . [5] 
Desarrollo de contenido curricular en el tema de Análisis y Diseño de Algoritmos 
Computacionales 
- 39 - 
 
• Definición de Ω(g): 
 
Sea una función Fng ∈)( , definimos (g(n))Ω como el conjunto de todas las 
funciones Fnf ∈)( que tienen la propiedad de que para una constante real c y una 
constante entera no negativa n0, y para todo 0nn ≥ , 
 
 
).()( nfncg ≤ 
 
 
 
Figura 3.4 - Ω(g) [3] 
 
 
Si ))(()( ngnf Ω∈ entonces )(nf es Big Ω de )(ng . [5] 
 
 
• Definición de Θ(g): 
 
Sea una función Fng ∈)( , definimos ))(( ngΘ como el conjunto de todas las 
funciones Fnf ∈)( que tienen la propiedad de que para dos constantes reales c1 y 
c2 y una constante entera no negativa n0, y para todo 0nn ≥ , 
 
Fundamentos de análisis de algoritmos - 40 - 
 
 
)()()( 21 ngcnfngc ≤≤ 
 
 
 
Figura 3.5 - Θ (g) [3] 
 
. 
 
Es decir, ))(())(())(( ngngOng Ω∩=Θ . 
 
Si ))(()( ngnf Θ∈ entonces )(nf es Big Θ de )(ng . [5] 
 
 
3.3.3 Big O 
 
Recordando la definición de Big O: 
 
Sea una función Fng ∈)( , definimos ))(( ngO como el conjunto de todas las 
funciones Fnf ∈)( que tienen la propiedad de que para una constante real c y una 
constante entera no negativa n0, y para todo 0nn ≥ , si ))(()( ngOnf ∈ entonces 
)(nf es Big O de )(ng . 
 
Por lo tanto sabemos que existen una serie de constantes (c, n y n0), pero en ningún 
momento se ha dicho como calcular estos valores. Como se verá a continuación, pueden 
Desarrollo de contenido curricular en el tema de Análisis y Diseño de Algoritmos 
Computacionales 
- 41 - 
 
haber muchísimos pares de c y n, dada una función f(n), una manera de obtenerlas es 
utilizando la función que estamos analizando y la definición de Big O. 
 
Del ejemplo anterior, tenemos: 
 
Sea )(000,000,1000,10)( 33 nOnnnf ∈++= como se mostró al final de la sección 3.3.1 
 
Sabemos por la definición que: 
 
33 000,000,1000,10 cnnn ≤++ 
 
Por lo tanto despejando la inecuación obtenemos: 
 
c
nn
≤++
32
000,000,1000,10
1 
 
De aquí podemos asignar valores, de tal manera que formemos los siguientes pares: 
 
n0 n0=1 2 3 4 100 101 200 1000 tiende 
a ∞ 
c c≥1010001 127501 38149 16251 3 2.95 1.37 1.0110 tiende 
a 1 
 
Para elegir el mejor par de c y n0, lo que tenemos que observar es en que punto uno de los 
factores de nuestra ecuación se convierte en el mayor y se mantiene siendo el mayor aún si 
seguimos aumentando n0. Los únicos términos en nuestro ejemplo que nos sirven para esto 
son 3n y n000,10 , en base a lo que vimos en secciones anteriores, queremos hallar los 
valores de c y n, para los cuales se cumple que: 
 
nn 000,103 > 
 
Esto se cumple a partir de que 100>n , por lo tanto obtenemos que el mejor par en nuestra 
tabla es: 
 
c = 2.95 y n = 101 
Es decir, si )(ncg es mayor o igual que )(nf desde n=101, entonces c tiene que ser al 
menos 2.95. 
 
Recordando la definición que se dio para O(g), podemos ver que la utilidad de hallar los 
posibles pares de c y n es mantener siempre la condición de Big O, la cual nos dice que g(n) 
es casi siempre más grande o igual que f(n) mientras g(n) sea multiplicada por una 
constante c correcta y n sea mayor que una constante n0. Esto queda más claro con la Figura 
3.6. 
 
Fundamentos de análisis de algoritmos - 42 - 
 
En la siguiente gráfica se comparan dos valores de )(ncg contra la función )(nf que es la 
cual estamos analizando en búsqueda de su Big O. 
 
 
 
Figura 3.6 – Funciones g(n) – f(n) 
 
Se puede observar en la gráfica que el punto en el cual se cruzan las funciones )(ng con 
)(nf coincide con el valor de n para la constante c elegida. 
 
De la figura 3.6 podemos concluir que para una función dada podemos encontrar múltiples 
funciones que cumplan con la definición de Big O, sin embargo para eliminar todo ese 
conjunto de posibilidades siempre nos interesará la menor, en este caso )( 3nO . 
 
Sabiendo esto, ¿cómo podemos identificar si una función es Big O/ Ω/ θ de otra función? 
Podemos emplear algunas herramientas. 
 
 
Para Big O, podemos utilizar el siguiente Lema: 
 
Una función ))(()( ngOnf ∈ si el ∞<=
∞→
c
ng
nf
n )(
)(
lim , incluido el caso cuando 
el límite es 0. 
Figura 3.7 – Big O [5] 
Desarrollo de contenido curricular en el tema de Análisis y Diseño de Algoritmos 
Computacionales 
- 43 - 
 
 
Si el límite del cociente de f(n) entre g(n) sí existe y no es infinito, podemos decir que g(n) 
crecerá más rápidamente que f(n). Pero si el límite es ∞ entonces f(n) sí crece más 
rápidamente que g(n). 
 
Ejemplo: 
 
Sean 1000100)( += nnf y 10)( 2 += nng . Demostrar que ))(()( ngOnf ∈ . 
 
Para 110≥n , sabemos que se cumple que )()( ncgnf ≤ en donde 1=c , por lo tanto 
))(()( ngOnf ∈ . 
 
Resolviéndolo mediante el lema especificado en la Figura 3.7, podemos ver que: 
 
0
10
1000100
lim
2
=
+
+
∞→ n
n
n
 
 
Por lo tanto ))(()( ngOnf ∈ . 
 
Para el análisis asintótico O(g(n)) podemos utilizar también otro teorema que aplica a 
límites: 
 
 
Sea )(nf y )(ng funciones diferenciables, con derivadas )(' nf y )(' ng 
respectivamente, tales que 
 
∞==
∞→∞→
)(lim)(lim ngnf
nn
 
 
Entonces 
 
)('
)('
lim
)(
)(
lim
ng
nf
ng
nf
nn ∞→∞→
= 
 
Figura 3.8 – Regla de L’Hôpital [5] 
 
 
 
 
 
 
 
 
 
 
Fundamentos de análisis de algoritmos - 44 - 
 
Ejemplo: 
 
Sean 1000lg)( 2 += nnf y 10)(
2 += nng . Demostrar que ))(()( nfOng ∉ . 
 
 
Para lo cual tenemos que: 
 
000,1lg
10
lim
2
2
+
+
∞→ n
n
n
 
 
Sabemos que para convertir de una base logarítmica a otra, podemos utilizar el siguiente 
lema: 
 
c
x
x
b
b
c
log
log
log = 
 
Con lo que tenemos: 
 
000,1
)2ln(
)ln(
10
lim
2
+
+
∞→ n
n
n
 
 
Si multiplicamos todo por ln(2): 
 
)2ln(000,1)ln(
)2ln()10(
lim
2
+
+
∞→ n
n
n
 
 
Aplicando regla de L’Hôpital: 
 
n
n
n 1
)2ln(2
lim
∞→
 
 
Finalmente: 
 
∞=
∞→
)2ln(2lim 2n
n
 
 
 
 
 
 
 
 
Desarrollo de contenido curricular en el tema de Análisis y Diseño de Algoritmos 
Computacionales 
- 45 - 
 
3.3.4 Propiedades de Big O, Big Ω y Big Θ [4] 
 
Estas notaciones tienen una serie de propiedades que nos pueden servir para facilitarnos el 
análisis de algoritmos. En todas las propiedades, suponemos que las funciones 
*:)(),(),( R�nhngnf → . 
 
1. (Transitividad) Si ))(()( ngOnf ∈ y ))(()( nhOng ∈ , entonces ))(()( nhOnf ∈ . Lo 
mismo aplica para Ω y Θ. 
2. ))(()( ngOnf ∈ si y sólo si ))(()( nfng Ω∈ . 
3. Si ))(()( ngnf Θ∈ , entonces ))(()( nfng Θ∈ . 
4. Si )(nf es ))(( nhO y )(ng es ))(( nhO , entonces )()( ngnf + es ))(( nhO . 
5. Si )()( ncgnf = , entonces )(nf es ))(( ngO .3.3.5 Jerarquía [3] 
 
Algunas complejidades se pueden identificar de cierta forma como menores que otras, tal es 
el caso de una complejidad de tipo linear O(n) y una complejidad cúbica O(n
3
). Sabemos 
que O(n) es de menor complejidad que O(n
3
). 
 
Siguiendo la definición que se encuentra en la figura 3.9, podemos construir una serie de 
conjuntos y construir un diagrama que nos permita identificar la jerarquía de diferentes 
complejidades. 
 
 
 
Dadas las funciones )(nf y )(ng , podemos decir que )(nf 
es de orden menor que )(ng si ))(( nfO esta contenido en 
))(( ngO , es decir, ))(())(( ngOnfO ⊂ . 
 
Figura 3.9 - Definición 
 
Al realizar los análisis Big O, Ω y Θ nos damos cuenta de que ciertas funciones se 
presentan con mucha frecuencia como resultado: 
 
• 1 
• logn 
• n 
• n 
• nlogn 
• n2 
• n3 
• 2n 
• n2n 
Fundamentos de análisis de algoritmos - 46 - 
 
• n! 
 
 
 
A partir de ellas podemos generar un diagrama de Venn (figura 3.9) que ilustre la jerarquía 
mediante la identificación de ciertas funciones como subconjunto de otras, es decir: 
 
)!()2()2()()()log()()()(log)1( 32 nOnOOnOnOnnOnOnOnOO nn ⊂⊂⊂⊂⊂⊂⊂⊂⊂
 
O(n!) 
O(n2
n
) 
O(2
n
) 
O(n
3
) 
O(n
2
) 
O(nlogn) 
O(n) 
O( n ) 
O(logn) 
O(1) 
 
 
 
 
 
 
 
 
 
Figura 3.10 – Diagrama de Venn 
 
Sabiendo esto, podríamos decir que si una función es O(n) por lo tanto también será O(n
2
) 
debido a que si ))(())(())(()( ngOnfOngOnf ⊆⇔∈ . Sin embargo en el análisis de 
algoritmos lo que nos interesa es identificar la complejidad de menor orden para cada 
algoritmo. 
 
A continuación se presenta una tabla que refleja el tiempo que se tardaría en ejecutar cierta 
cantidad de instrucciones en una computadora que pueda ejecutar 1 instrucción por 
microsegundo. Se pretende que con esta tabla quede claro por qué algunas complejidades 
son menores que otras: 
 
 
3 10 
instrucciones 
100 
instrucciones 
1,000 
instrucciones 
10,000 
instrucciones 
100,000 
instrucciones 
)1(O 1 sµ 1 sµ 1 sµ 1 sµ 1 sµ 
)(lognO 3 sµ 7 sµ 10 sµ 13 sµ 17 sµ 
n 3 sµ 10 sµ 31 sµ 100 sµ 316 sµ 
n 10 sµ 100 sµ 1,000 sµ 10,000 sµ 100,000 sµ 
nn log 33 sµ 664 sµ 10,000 sµ 133,000 sµ 1.6 seg 
2n 100 sµ 10,000 sµ 1 seg 1.7min 16.7min 
3n 1ms 1 seg 16.7min 11.6 día 31.7 año 
Desarrollo de contenido curricular en el tema de Análisis y Diseño de Algoritmos 
Computacionales 
- 47 - 
 
n2 1.024ms 4*10
16
año 3.39*10
287
año … … 
nn2 10.24ms 4*10
18
año … … … 
!n 4 seg 2.95*10144año … … … 
 
Queda claro que complejidades mayores requieren mucho más tiempo para realizar el 
mismo número de instrucciones. En algunos casos el tiempo es tan grande que deja de ser 
un algoritmo que pueda utilizarse. [4] 
 
 
3.3.6 Problemas 3P-Completos [11] 
 
Existen dos clases de problemas que nos conviene definir antes de poder decir lo que son 
los problemas NP-Completos: La clase P y la clase NP. 
 
La clase P solo se puede definir para problemas de decisión, es decir problemas en los 
cuales solo existen dos posibles respuestas: sí o no. Además P es la clase de problemas que 
se encuentran polinómicamente acotados: Problemas en los cuales su complejidad en el 
peor caso se puede definir mediante un polinomio del tamaño de las entradas. Los 
problemas que se encuentren dentro de esta clase, serán en muchas ocasiones eficientes, y 
podrán ser resueltos en un tiempo razonable, los problemas que no pertenezcan a esta clase 
por el contrario en su mayoría serán problemas que no se puedan resolver. Una propiedad 
de los problemas de la clase P, es que podemos obtener la solución a un problema a partir 
de la combinación de algoritmos para problemas más fáciles siempre y cuando los 
algoritmos para estos problemas también se encuentren polinómicamente acotados. Además 
de todo esto, los problemas P son resueltos por algoritmos determinísticos, es decir el 
conjunto de algoritmos que dada una entrada solo existe un posible camino para determinar 
el siguiente paso que deberá dar el algoritmo. 
 
La clase NP también se define para los problemas de decisión, que deben poder ser 
polinómicamente acotados y a diferencia de la clase P, los algoritmos NP son no-
determinísticos, es decir son algoritmos que utilizan algún tipo de operación que cuando se 
presenta una decisión hacen una conjetura para saber cuál es el siguiente paso que se debe 
tomar. La clase P es un subconjunto de NP, pues los algoritmos determinísticos son 
aquellos algoritmos no determinísticos que no utilizan decisiones no determinísticas. 
 
Un problema es NP-Completo si se puede resolver mediante un algoritmo polinómico no 
determinístico, y además se puede reducir cualquier problema NP a este problema NP-
Completo: 
 
Un problema se puede reducir a otro problema, si existe alguna función que al ser 
procesada con instancias del primer problema, devuelva instancias del segundo problema, 
es decir, para cada instancia del primer problema habrá una contraparte del segundo. La 
reducción no es simétrica, es decir un problema A puede ser reducido a un problema B, 
pero lo contrario no es necesariamente verdadero. Reducir un problema nos sirve pues si 
podemos encontrar una instancia del problema B para cualquier instancia del problema A, 
Fundamentos de análisis de algoritmos - 48 - 
 
entonces una solución eficiente del problema B puede ser eficientemente transformada en 
una solución al problema A. 
 
Un problema A en NP es NP-Completo si todos los problemas en NP son reducibles a A. 
Por lo tanto todos los problemas NP-Completo son computacionalmente equivalentes. 
 
Los problemas de NP-Completo son los problemas más difíciles de NP. En la actualidad 
cualquier algoritmo que forme parte del conjunto NP-Completo, empleará tiempo 
exponencial para hallar una solución (ver tabla en la sección 3.3.5), por lo que 
generalmente para resolver este tipo de problemas se emplean soluciones probabilísticas o 
simplemente se hacen aproximaciones. 
 
3.4 Ejemplos 
 
3.4.1 Ciclo 
 
Tomamos como primer ejemplo el siguiente ciclo: 
 
for i�0 hasta n-1 hacer 
 j � arreglo[i] “arreglo en su posición i” 
endfor 
 
La operación que utilizaremos para hacer el análisis asintótico y obtener Big O, serán las 
asignaciones que se realizan en la inicialización y durante el ciclo. 
 
Sabemos que i se inicializa en 0 y se incrementa de 1 en 1 hasta n-1. 
 
Primero se inicializa la variable i (i�0), después el ciclo itera n veces (de 0 a n-1), y 
durante cada iteración se asigna un nuevo valor a i y a j. De tal manera que al final del ciclo 
for se deberán haber hecho 1 + 2n asignaciones. 
 
Si nnf 21)( += y mediante el uso de las definiciones, sabemos que el único factor que a 
entradas grandes contribuirá al valor de la función es n, de tal manera que ))(()( ngOnf ∈ 
en donde nng =)( . Se puede escribir como que su complejidad asintótica es )(nO . 
 
3.4.2 Ciclo anidado 
 
Para este ejemplo lo que analizaremos es un ciclo dentro de otro ciclo, es decir un ciclo 
anidado: 
 
 for i�0 hasta n-1 do 
 for j� hasta i do 
 x � arreglo[j] “arreglo en su posición j” 
 endfor 
 endfor 
Desarrollo de contenido curricular en el tema de Análisis y Diseño de Algoritmos 
Computacionales 
- 49 - 
 
 
Una vez más utilizaremos las asignaciones como nuestra operación básica. 
 
Al igual que en el ejemplo anterior el for exterior se ejecuta n veces e inicializa para ello a 
i, solo que en esta ocasión en cada iteración del ciclo exterior se ejecuta un ciclo interior y 
se hacen asignaciones a i, j y x por lo tanto habrán 1+3n asignaciones. El ciclo interior se 
ejecuta i veces por cada i que en cada iteración exterior puede tomar valores entre 1 y n-1, 
además en cada iteración del ciclo interior se hacen asignaciones a x y j, en esta ocasión no 
podemos considerar la asignación inicial de j, pues esa ya la estamos considerando como 
parte del ciclo