Introduccion a las Estructuras de Datos

Estructuras de Datos

Introduccion

Podemos pensar en un programa como una serie de instrucciones que realizan acciones sobre datos. Sin datos, no tendriamos programas.

Estructuras de Datos

Una estructura de datos se puede definir como una coleccion de elementos sobre la que se realizan operaciones y se utiliza eficientemente.

Basicamente, es como se organizan datos en memoria (RAM).

Stack vs Heap

La memoria esta dividida por bytes, cada byte tiene una direccion y se almacenan de manera lineal.

La memoria esta dividida en tres secciones: la seccion code, el heap, y el stack.

La seccion code es donde estan almacenadas las instrucciones del programa.

Stack

En el siguiente programa:

int
main (void)
{
  int a = 0;
  float b = 0;

  return 0;
}

Esas dos variables seran almacenadas en el stack.

En el stack se va a crear un “activation record” o “stack frame” para cada funcion (una division del stack, donde unicamente las variables definidas dentro de el seran visibles.)

El tamano de memoria que se necesita para almacenar una variable se decide durante la compilacion del programa, por eso se llama gestion de memoria estatica.

Heap

La memoria en el heap puede ser gestionada de forma dinamica (puede ser creada, destruida, incrementada o disminuida).

A diferencia del stack, esta no se crea ni se destruye automaticamente.

Si no liberamos memoria que pusimos en el heap vamos a tener memory leaks (fugas de memoria.)

Para manejar el heap, utilizamos pointers.

Por ejemplo, si queremos un espacio en memoria para almacenar 5 enteros:

int *enteros = malloc (5 * sizeof (int));

Y manualmente tenemos que liberarla cuando no sea necesaria:

free (enteros);

Estructuras de Datos Fisicas vs Logicas

Las estructuras de datos se pueden categorizar como estructuras de datos fisicas y estructuras de datos logicas.

Estructuras de Datos Fisicas

Las estructuras de datos fisicas definen como la memoria esta organizada. Por ejemplo arrays y linked lists.

En los arrays la memoria es continua, el proximo elemento esta justo despues del anterior.

Estructuras de Datos Logicas

Las estructuras de datos logicas son formas organizadas de almacenar y manipular datos en memoria para su uso eficiente, independientemente de como se almacenen fisicamente.

Ejemplos de estructuras de datos logicas:

1. Stack
2. Queues
3. Trees
4. Graphs
5. Hash Tables

Los stacks y queues son estructuras de datos lineales, los trees y graphs son no-lineales, y las hash tables son estructuras de datos tabulares.

Complejidad de Espacio y de Tiempo

Complejidad de Tiempo

La complejidad de tiempo, es una manera de medir que tanto tiempo le toma a una maquina realizar una tarea.

Por ejemplo, si tenemos un array de \(n\) elementos (5, 10, 20, 100, 10000, etc), si queremos pasar por cada uno de estos elementos y nos preguntamos que tanto tiempo tomara hacerlo? Decimos que su complejidad de tiempo es \(n\). Es decir, si tenemos una lista, y estamos recorriendo sus elementos una sola vez, su complejidad de tiempo es \(O(n)\).

Si tenemos una lista, de \(n\) elementos y tenemos que recorrer esos elementos 2 veces, ahora su complejidad de tiempo es \(O(n^2)\).

Si tenemos que iterar sobre una lista \(\frac{n}{2}\) veces, su complejidad de tiempo seria \(O(\log n)\).

• Ejemplo 1

  Cual es la complejidad de tiempo de este bucle:

  for (int i = 0; i < n; i++)
    {
      /* operaciones aqui */
    }
  

  • Solucion

    \(O(n)\) porque apenas interamos \(n\) cantidad de veces.

• Ejemplo 2

  Cual es la complejidad de tiempo de este bucle:

  for (int i = 0; i < n; i++)
    {
      for (int j = 0; j < n; j++)
        {
          /* operaciones aqui */
        }
    }
  

  • Solucion

    \(O(n^2)\) porque tenemos que iterar por todos los elementos dos veces.

• Ejemplo 3

  Cual es la complejidad de tiempo de esta funcion.

  for (int i = 0; i < n; j++)
    {
      for (int j = i + 1; j < n; j++)
        {
          /* operaciones aqui */
        }
    }
  

  • Solucion

    \(O(n^2)\) tambien, aunque en el segundo bucle \(j = i + 1\) estamos pasando \(n\) cantidad de veces, en dos veces.

• Ejemplo 4

  Cual es la complejidad de tiempo de esta funcion:

  int i = n;
  while (i > 1)
    {
      /* operaciones aqui */
  
      i = i / 2;
    }
  

  • Solucion

    \(O(\log n)\) porque estamos pasando \(\frac{n}{2}\) cantidad de veces.

Complejidad de Espacio

Cuando queremos saber cuanto espacio es consume en memoria durante la ejecucion de un programa, a eso le llamamos la complejidad de espacio.

Es importante saber que no estamos calculando el espacio en bytes, unicamente queremos saber en que depende el espacio que se utilice.

Si en un array hay \(n\) elementos, su complejidad de espacio es \(O(n)\).

Ejemplos con codigo

• Ejemplo 1

  int
  suma (int num[], int n)
  {
    int total = 0;
    for (int i = 0; i < n; i++)
      {
        total += num[n];
      }
    return total;
  }
  

  • Solucion

    Complejidad de tiempo: \(O(n)\)

• Ejemplo 2

  void
  suma (int **a, int **b, int **out, int n)
  {
    for (int i = 0; i < n; i++)
      {
        for (int j = 0; j < n; j++)
          {
            out[i][j] = a[i][j] + b[i][j];
          }
      }
  }
  

  • Solucion

    Complejidad de tiempo: \(O(n^2)\)

• Ejemplo 3

  void
  swap (int *x, int *y)
  {
    int temp = *x;
    *x = *y;
    *y = temp;
  }
  

  • Solucion

    Complejidad de tiempo: \(O(1)\). Es constante, unicamente se realizan 2 asignaciones siempre.

• Ejemplo 4

  Cual es la complejidad de tiempo de func1?

  void
  func2 ()
  {
    for (int i = 0; i < n; i++)
      {
        /* operaciones aqui */
      }
  }
  
  void
  func1 ()
  {
    func2();
  }
  

  • Solucion

    La complejidad de tiempo de func1 es \(O(n)\). Aunque apenas tengamos una sola instruccion, eso no lo hace \(O(1)\), porque esa instruccion es llamar a una funcion cuya complejidad de tiempo es \(O(n)\).