Universidad del Istmo Campus Tehuantepec
Ingeniería en Computación
Análisis y Complejidad de Algoritmos
Ana Patricia Matus Vicente
Décimo semestre

En la siguiente gráfica se observa que se graficaron las siguientes funciones: * fn=n * fn=n2 * fn=n3 * fn=n * fn=2n * fn=ln⁡(n) * fn=nln(n)
Se puede observar que fn=2n es la función que crece de una manera más rápida con respecto a las otras seis funciones, entre más grande sea el valor de n más rápido crece la función. De lo contrario para fn=ln⁡(n) crece de una manera muy lenta, aun cuando el valor de n sea muy grande.

Universidad del Istmo Campus Tehuantepec
Ingeniería en Computación
Análisis y Complejidad de Algoritmos
Ana Patricia Matus Vicente
Décimo semestre

Cuando de desea buscar un elemento en un arreglo se procede a realizar la búsqueda secuencialmente, a esto se le conoce como búsqueda lineal, las siguientes dos condiciones que ponen fin a la búsqueda: 1. Se encuentra el elemento, es decir ai=x. 2. Se recorrió todo el arreglo y no se encontró el elemento de búsqueda.
El algoritmo para la búsqueda lineal fue implementado en el sistema operativo Linux en el lenguaje de programación Go. La Figura 1 muestra el código que implementa dicho algoritmo. Se realiza la búsqueda del número 77 encontrando al elemento, también se realiza la búsqueda del número 1 que no es encontrado como se puede ver en la Figura.

Figura 1. Código implementado en lenguaje Go.

Figura 2. Resultados obtenidos.
Otra manera de realizar una búsqueda lineal es garantizando la concordancia y esto se logra colocando un elemento adicional con un valor x al final del arreglo, el cual se le llamará centinela, ya que previene a la búsqueda de exceder el límite del índice.
La Figura 3 muestra el código que implementa dicho algoritmo, donde se tiene un arreglo que va de [0 .. N], donde N=10 y en la posición N del arreglo se coloca la variable aux que tiene el valor de la variable centinela que es el elemento a buscar. Si i = N implica que no se hay concordancia excepto la centinela es decir el elemento no se encuentra en el arreglo. Se realiza la búsqueda del número 8 encontrando al elemento, también se realiza la búsqueda del número 1 que no es encontrado como se puede ver en la Figura 4.

Figura 3. Código implementado en lenguaje Go.

Figura 4. Resultados obtenidos con elemento auxiliar.