Estructuras de Datos y Algoritmos/Introducción
El objetivo de este curso es mostrar las 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 más 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 número de operaciones necesarias para realizarlo.
Se dice que un algoritmo es de complejidad constante K si el número de instrucciones necesarias para ejecutarlo no depende del número 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 array. 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 número de instrucciones necesarias para ejecutarlo depende del número de elementos de la estructura que estemos tratando.
Ejemplo : imprimir el contenido de una lista
int n=10 // longitud del array.
int array[n]; // creación del array.
for (int i=0;i<n;i++){
print array[i]; // imprime el i-ésimo 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 array.
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
}
}