Estructuras de Datos y Algoritmos / Introducción

De Wikiversidad

El objetivo de este curso es de mostrar la estructuras de datos elementales en la programación y discutir sobre la utilización de las mismas. Es fundamental estudiar junto con estas estructuras de datos los diferentes algoritmos que se pueden implementar sobre ellas (búsquedas, inserciones, etc ..). Para elegir la estructura que mas se adapta a las necesidades. Vamos a dar una medida de la performancia de los diferentes algoritmos para ayudarnos en nuestra elección.

Nociones básicas de calculabilidad y complejidad

La complejidad de un algoritmo es el numero de operaciones necesarias para realizarlo.

Se dice que un algoritmo es de complejidad constante K si el numero de instrucciones necesarias para ejecutarlo no depende del numero de elementos de la estructura que estemos tratando. Ejemplo : la inserción de un elemento en la posición n de un array (o tabla de longitud constante)

 int n=10 // longitud del arrray.
 int array[n]; // creación del array.
 array[3]=10; // inserción de un elemento en la posición 3, atención 3<n.

Se dice que un algoritmo es de complejidad N si el numero de instrucciones necesarias para ejecutarlo depende del numero de elementos de la estructura que estemos tratando. Ejemplo : imprimir el contenido de una lista

 int n=10 // longitud del arrray.
 int array[n]; // creación del array.
 for (int i=0;i<n;i++){
   print array[i]; // imprime el i-essimo elemento de la lista.
 }

la búsqueda secuencial dentro de una lista tiene una complejidad de N/2. Veamos el código :

 int n=10 // longitud del arrray.
 int array[n]; // creación del array.
 for (int i=0;i<n;i++){
   if (array[i]==elemento_buscado){
       exit ; // final de la búsqueda 
   }
 }