La estructura de datos es una forma de recopilar y organizar datos de tal manera que podamos realizar operaciones sobre estos datos de una manera efectiva. Data Structures se trata de representar elementos de datos en términos de alguna relación, para una mejor organización y almacenamiento. Por ejemplo, tenemos el nombre del jugador de datos “Virat” y la edad 26. Aquí “Virat” es del tipo de datos String y 26 es del tipo de datos enteros .
Podemos organizar estos datos como un registro como el registro del jugador . Ahora podemos recopilar y almacenar los registros del jugador en un archivo o base de datos como una estructura de datos. Por ejemplo: “Dhoni” 30, “Gambhir” 31, “Sehwag” 33
En lenguaje simple, las Estructuras de datos son estructuras programadas para almacenar datos ordenados, de modo que se pueden realizar varias operaciones en ellos fácilmente.
Como hemos comentado anteriormente, cualquier cosa que pueda almacenar datos puede ser llamada como una estructura de datos, por lo tanto, Integer, Float, Boolean, Char, etc., todas son estructuras de datos. Son conocidos como estructuras de datos primitivos .
Luego también tenemos algunas estructuras de datos complejas, que se utilizan para almacenar datos grandes y conectados. Algunos ejemplos de estructura de datos abstracta son Para obtener más información, puede visitar este enlace C y clases de formación de estructuras de datos en línea | Cursos de C y Estructuras de Datos en línea
Todas estas estructuras de datos nos permiten realizar diferentes operaciones sobre los datos. Seleccionamos estas estructuras de datos según el tipo de operación que se requiera. Examinaremos estas estructuras de datos con más detalle en nuestras lecciones posteriores.
Un algoritmo es un conjunto finito de instrucciones o lógica, escrito en orden, para realizar una determinada tarea predefinida. El algoritmo no es el código o programa completo, es solo la lógica central (solución) de un problema, que puede expresarse como una descripción informal de alto nivel como pseudocódigo o mediante un diagrama de flujo .
Se dice que un algoritmo es eficiente y rápido, si se tarda menos tiempo en ejecutarse y consume menos espacio de memoria. El rendimiento de un algoritmo se mide sobre la base de las siguientes propiedades:
- Complejidad del tiempo
- Complejidad espacial
- Es la cantidad de espacio de memoria requerida por el algoritmo, durante el curso de su ejecución. La complejidad del espacio debe tomarse en serio para los sistemas multiusuario y en situaciones donde la memoria limitada está disponible.
Un algoritmo generalmente requiere espacio para los siguientes componentes:
- Espacio de instrucciones: Es el espacio requerido para almacenar la versión ejecutable del programa. Este espacio es fijo, pero varía según el número de líneas de código en el programa.
- Espacio de datos: Es el espacio requerido para almacenar todas las constantes y el valor de las variables.
- Espacio de entorno: es el espacio necesario para almacenar la información de entorno necesaria para reanudar la función suspendida
- La complejidad del tiempo es una forma de representar la cantidad de tiempo que necesita el programa para ejecutarse hasta su finalización. Vamos a estudiar esto en detalle en nuestra sección.
para (i = 0; i
La complejidad del tiempo para el algoritmo anterior será lineal . El tiempo de ejecución del bucle es directamente proporcional a N. Cuando N se duplica, también lo hace el tiempo de ejecución.
para (i = 0; i
Esta vez, la complejidad del tiempo para el código anterior será cuadrática . El tiempo de ejecución de los dos bucles es proporcional al cuadrado de N. Cuando N se duplica, el tiempo de ejecución aumenta en N * N.
while (bajo <= alto) {medio = (bajo + alto) / 2; if (target list [mid]) low = mid + 1; de lo contrario romper }
Este es un algoritmo para dividir un conjunto de números en mitades, para buscar un campo en particular (lo estudiaremos en detalle más adelante). Ahora, este algoritmo tendrá una complejidad de tiempo logarítmica . El tiempo de ejecución del algoritmo es proporcional al número de veces que N se puede dividir entre 2 (N es alto-bajo aquí). Esto se debe a que el algoritmo divide el área de trabajo a la mitad con cada iteración.
void quicksort (int list [], int left, int right) {int pivot = partition (list, izquierda, derecha); quicksort (list, left, pivot - 1); quicksort (lista, pivote + 1, derecha); }
Tomando el algoritmo anterior hacia adelante, arriba tenemos una pequeña lógica de Ordenación rápida (estudiaremos esto en detalle más adelante). Ahora, en Ordenación rápida, dividimos la lista en mitades cada vez, pero repetimos la iteración N veces (donde N es el tamaño de la lista). Por lo tanto, la complejidad del tiempo será N * log (N) . El tiempo de ejecución consiste en N bucles (iterativos o recursivos) que son logarítmicos, por lo que el algoritmo es una combinación de lineal y logarítmico.
NOTA: En general, hacer algo con cada elemento en una dimensión es lineal, hacer algo con cada elemento en dos dimensiones es cuadrático y dividir el área de trabajo por la mitad es logarítmico.
Tipos de notaciones para la complejidad del tiempo
Ahora discutiremos y entenderemos las diversas notaciones utilizadas para la complejidad del tiempo.
- Big Oh denota " menos o lo mismo que " iteraciones.
- Big Omega denota " más o lo mismo que " iteraciones.
- Big Theta denota " lo mismo que " iteraciones.
- Little Oh denota " menos que " iteraciones.
- Little Omega denota " más que " iteraciones.
Entendiendo las notaciones de la complejidad del tiempo con el ejemplo.
O (expresión) es el conjunto de funciones que crecen más lentamente o al mismo ritmo que la expresión.
Omega (expresión) es el conjunto de funciones que crecen más rápido o al mismo ritmo que la expresión.
Theta (expresión) consiste en todas las funciones que se encuentran tanto en O (expresión) como en Omega (expresión).
Para obtener más información, puede visitar este enlace C y clases de formación de estructuras de datos en línea | Cursos de C y Estructuras de Datos en línea
Supongamos que ha calculado que un algoritmo toma f (n) operaciones, donde,
f (n) = 3 * n ^ 2 + 2 * n + 4. // n ^ 2 significa el cuadrado de n
Como este polinomio crece a la misma velocidad que n ^ 2 , entonces podría decirse que la función f se encuentra en el conjunto Theta (n ^ 2) . (También se encuentra en los conjuntos O (n ^ 2) y Omega (n ^ 2) por la misma razón).
La explicación más sencilla es que Theta denota lo mismo que la expresión. Por lo tanto, a medida que f (n) crece por un factor de n ^ 2 , la complejidad del tiempo puede representarse mejor como Theta (n ^ 2) .
C Programación y Estructuras de datos es un curso básico diseñado para brindar capacitación sobre conceptos básicos de computadoras, organización de memoria, preprocesador, compilador y vinculador. Proporciona un excelente aprendizaje para crear su primer programa en C y sesiones de práctica sobre tipos de datos y operadores, variables y calificadores, flujo de control, funciones en C, recursión, matrices, cadenas. El curso incluye además punteros en C y operaciones avanzadas de estructuras de datos como aritmética de punteros, matrices multidimensionales, asignación de memoria dinámica, estructuras, listas vinculadas, uniones, búsqueda y clasificación, operaciones de archivos y funciones de cadena.
