Big-O en C - Proyecto final

El proyecto final combina todo lo aprendido: implementar funciones con distintos órdenes de crecimiento, medir tiempos, mostrar un gráfico sencillo en consola, optimizar y ofrecer un menú de pruebas listo para compilar.

12.1 Escribir funciones con distintos Big-O

int constante(int n) { return 42; }               // O(1)

int suma_lineal(const int *v, int n) {            // O(n)
  int total = 0;
  for (int i = 0; i < n; i++) total += v[i];
  return total;
}

int busca_cuadratica(const int *v, int n) {       // O(n^2)
  for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
      if (v[i] == v[j]) return 1;
    }
  }
  return 0;
}

Prepara entradas de distinto tamaño para ver cómo crece el tiempo en cada función.

12.2 Medir tiempo real y compararlo con el teórico

double medir_segundos(void (*fn)(int *v, int n), int *v, int n) {
  const int rep = 2000;         // repeticiones altas para ver tiempos > 0
  fn(v, n);                     // calentamiento
  clock_t inicio = clock();
  for (int i = 0; i < rep; i++) fn(v, n);
  clock_t fin = clock();
  return (double)(fin - inicio) / (CLOCKS_PER_SEC * rep);
}

Corre cada función con varios n, guarda los pares (n, tiempo) y verifica si la curva coincide con el Big-O esperado.

12.3 Implementar un gráfico simple por consola

void grafico_ascii(const int *ns, const double *ts, int m) {
  double max = 0.0;
  for (int i = 0; i < m; i++) if (ts[i] > max) max = ts[i];
  for (int i = 0; i < m; i++) {
    int barras = (int)((ts[i] / max) * 50); // escala a 50 caracteres
    printf("%6d | ", ns[i]);
    for (int j = 0; j < barras; j++) putchar('#');
    printf(" %.6f s\n", ts[i]);
  }
}

Este gráfico de barras da una vista rápida del crecimiento sin depender de herramientas externas.

12.4 Optimizar versiones lentas

Sustituye la búsqueda cuadrática por ordenar y contar en O(n log n).
Reemplaza loops anidados por estructuras como hash para llegar a O(n) promedio.
Comprueba la mejora midiendo antes y después.

int main(void) {
  int opcion;
  int datos_suma[200000];
  int datos_busca[8000];
  generar_datos(datos_suma, 200000);
  generar_datos(datos_busca, 8000);
  do {
    printf("1) Suma lineal\n2) Buscar duplicado (cuadratico)\n3) Buscar duplicado optimizado\n0) Salir\n");
    scanf("%d", &opcion);
    switch (opcion) {
      case 1: printf("Tiempo: %.6f s\n", medir_segundos(suma_lineal, datos_suma, 200000)); break;
      case 2: printf("Tiempo: %.6f s\n", medir_segundos(busca_cuadratica_wrap, datos_busca, 8000)); break;
      case 3: printf("Tiempo: %.6f s\n", medir_segundos(busca_hash_wrap, datos_busca, 8000)); break;
      case 0: puts("Fin"); break;
      default: puts("Opcion invalida");
    }
  } while (opcion != 0);
  return 0;
}

Las funciones _wrap son adaptadores con la firma esperada (reciben int *v y n). Ajusta n para que cada prueba tarde un tiempo razonable.

12.6 Compilar y depurar en CLion

Configura un proyecto de consola; agrega main.c y los archivos con tus funciones.
Compila con -O2 -g para equilibrar optimización y depuración.
Usa breakpoints para inspeccionar variables y asegurarte de que los datos de entrada no se alteren entre pruebas.
Integra sanitizers (Address/Leak) para descartar fugas al repetir benchmarks.

12.7 Archivos a incorporar en el proyecto

main.c: menú interactivo y orquestación de pruebas.
funciones.h: declaraciones de las funciones de cada Big-O y utilidades compartidas.
funciones.c: implementaciones de versiones lenta/optimizada, generación de datos y adaptadores para medir.
benchmark.c: helpers de medición y exportación opcional a CSV.
Makefile o configuración de CLion: flags de compilación (-O2 -g -fsanitize=address,leak en modo debug).
README.md: instrucciones de ejecución, tamaños de entrada sugeridos y precauciones de memoria.
resultados.csv (opcional): salidas para graficar tiempos.

// funciones.h
#include <stddef.h>

void generar_datos(int *v, int n);
int constante(int n);
int suma_lineal(const int *v, int n);
int busca_cuadratica(const int *v, int n);
int busca_hash(const int *v, int n, int max_valor);

void busca_cuadratica_wrap(int *v, int n);
void busca_hash_wrap(int *v, int n);

// funciones.c
#include "funciones.h"
#include <stdlib.h>
#include <time.h>

#define MAX_VALOR 100000

void generar_datos(int *v, int n) {
  srand((unsigned)time(NULL));
  for (int i = 0; i < n; i++) v[i] = rand() % MAX_VALOR;
}

int constante(int n) { (void)n; return 42; }

int suma_lineal(const int *v, int n) {
  int total = 0;
  for (int i = 0; i < n; i++) total += v[i];
  return total;
}

int busca_cuadratica(const int *v, int n) {
  for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
      if (v[i] == v[j]) return 1;
    }
  }
  return 0;
}

int busca_hash(const int *v, int n, int max_valor) {
  int *tabla = calloc((size_t)max_valor, sizeof(int));
  if (!tabla) return 0;
  int hallado = 0;
  for (int i = 0; i < n; i++) {
    int clave = v[i] % max_valor;
    if (tabla[clave]) { hallado = 1; break; }
    tabla[clave] = 1;
  }
  free(tabla);
  return hallado;
}

void busca_cuadratica_wrap(int *v, int n) {
  (void)busca_cuadratica(v, n);
}

void busca_hash_wrap(int *v, int n) {
  (void)busca_hash(v, n, MAX_VALOR);
}

// benchmark.c
#include "funciones.h"
#include <stdio.h>
#include <time.h>

double medir_segundos(void (*fn)(int *v, int n), int *v, int n) {
  const int rep = 2000;
  fn(v, n);
  clock_t inicio = clock();
  for (int i = 0; i < rep; i++) fn(v, n);
  clock_t fin = clock();
  return (double)(fin - inicio) / (CLOCKS_PER_SEC * rep);
}

void grafico_ascii(const int *ns, const double *ts, int m) {
  double max = 0.0;
  for (int i = 0; i < m; i++) if (ts[i] > max) max = ts[i];
  for (int i = 0; i < m; i++) {
    int barras = max == 0 ? 0 : (int)((ts[i] / max) * 50);
    printf("%6d | ", ns[i]);
    for (int j = 0; j < barras; j++) putchar('#');
    printf(" %.6f s\n", ts[i]);
  }
}

void escribir_csv(const char *ruta, const int *ns, const double *ts, int m) {
  FILE *f = fopen(ruta, "w");
  if (!f) return;
  fprintf(f, "n,tiempo_s\n");
  for (int i = 0; i < m; i++) fprintf(f, "%d,%.6f\n", ns[i], ts[i]);
  fclose(f);
}

// main.c
#include "funciones.h"
#include <stdio.h>

double medir_segundos(void (*fn)(int *v, int n), int *v, int n); // declarado en benchmark.c

int main(void) {
  int opcion;
  int datos_suma[200000];
  int datos_busca[8000];
  generar_datos(datos_suma, 200000);
  generar_datos(datos_busca, 8000);
  do {
    printf("1) Suma lineal\n2) Buscar duplicado (cuadratico)\n3) Buscar duplicado optimizado\n0) Salir\n");
    if (scanf("%d", &opcion) != 1) break;
    switch (opcion) {
      case 1:
        printf("Tiempo: %.6f s\n", medir_segundos(suma_lineal, datos_suma, 200000));
        break;
      case 2:
        printf("Tiempo: %.6f s\n", medir_segundos(busca_cuadratica_wrap, datos_busca, 8000));
        break;
      case 3:
        printf("Tiempo: %.6f s\n", medir_segundos(busca_hash_wrap, datos_busca, 8000));
        break;
      case 0:
        puts("Fin");
        break;
      default:
        puts("Opcion invalida");
    }
  } while (opcion != 0);
  return 0;
}

Retornar