7 days of WordPress plugins, themes & templates - for free!* Unlimited asset downloads! Start 7-Day Free Trial
Advertisement
  1. Code
  2. Web Development

Algoritmos y Estructuras de Datos

Scroll to top
Read Time: 5 mins
This post is part of a series called Data Structures Succinctly: Part 1.
Stacks and Queues
The Set Collection

Spanish (Español) translation by Ruben Solis (you can also view the original English article)

Supongo que eres un programador de computadoras. Tal vez seas un estudiante nuevo de ciencia de la computación o quizás seas un ingeniero de software experimentado. Independientemente de dónde te encuentres en ese espectro, los algoritmos y las estructuras de datos son importantes. No solo como conceptos teóricos, sino como bloques de construcción utilizados para crear soluciones a problemas de negocios.

Por supuesto, es posible que sepas cómo usar la clase  List  o la clase  Stack de C#, pero ¿entiendes lo que está pasando bajo las sábanas? Si no es así, ¿realmente estás tomando las mejores decisiones sobre qué algoritmos y estructuras de datos estás utilizando?

La comprensión significativa de algoritmos y estructuras de datos comienza con tener una manera de expresar y comparar sus costos relativos.

Análisis asintótico

Cuando hablamos de medir el costo o la complejidad de un algoritmo, de lo que realmente estamos hablando es de realizar un análisis del algoritmo cuando los conjuntos de entrada son muy grandes. El análisis de lo que sucede cuando el número de entradas se hace muy grande se conoce como análisis asintótico. ¿Cómo cambia la complejidad del algoritmo cuando se aplica a diez, o mil o diez millones de elementos? Si un algoritmo se ejecuta en cinco milisegundos con mil elementos, ¿qué podemos decir sobre lo que sucederá cuando se ejecute con un millón? ¿Tomará cinco segundos o cinco años? ¿No preferirías resolver esto antes que tu cliente?

¡Esto importa!

Tasa de crecimiento

La tasa de crecimiento describe cómo cambia la complejidad de un algoritmo a medida que aumenta el tamaño de la entrada. Esto se representa comúnmente utilizando la notación Big-O. La notación Big-O usa una O mayúscula ("order") y una fórmula que expresa la complejidad del algoritmo. La fórmula puede tener una variable, n, que representa el tamaño de la entrada. Las siguientes son algunas funciones de orden comunes que veremos en este libro, pero de ninguna manera esta lista está completa.

Constante - O (1)

Un algoritmo O(1) es uno cuya complejidad es constante independientemente del tamaño de la entrada. El "1" no significa que haya una sola operación o que la operación tome una pequeña cantidad de tiempo. Puede tardar un microsegundo o una hora. El punto es que el tamaño de la entrada no influye en el tiempo que tarda la operación.

Lineal - O(n)

Un algoritmo O(n) es uno cuya complejidad crece linealmente con el tamaño de la entrada. Es razonable esperar que si un tamaño de entrada de uno toma cinco milisegundos, una entrada con mil elementos tomará cinco segundos.

A menudo se puede reconocer un algoritmo O(n) buscando un mecanismo de bucle que acceda a cada miembro.

Logarítmico - O(log n)

Un algoritmo O(log n) es uno cuya complejidad es logarítmica a su tamaño. Muchos algoritmos de divide y vencerás caen en este grupo. El método Contains del árbol binario de búsqueda implementa un algoritmo O(log n).

Linearítmico - O(n log n)

Un algoritmo linearítmico, o loglineal, es un algoritmo que tiene una complejidad de O(n log n). Algunos algoritmos de divide y vencerás caen en este grupo. Veremos dos ejemplos cuando examinemos el merge sort y el quick sort.

Cuadrático - O(n^2)

Un algoritmo O(n^2) es uno cuya complejidad es cuadrática a su tamaño. Si bien no siempre es evitable, el uso de un algoritmo cuadrático es un señal potencial de que necesitas reconsiderar la elección de tu algoritmo o estructura de datos. Los algoritmos cuadráticos no escalan bien a medida que aumenta el tamaño de la entrada. Por ejemplo, un array con 1000 enteros requeriría 1,000,000 de operaciones para completarse. Una entrada con un millón de elementos tomaría un trillón (1,000,000,000,000) de operaciones. Para poner esto en perspectiva, si cada operación tarda un milisegundo en completarse, un algoritmo O (n^2) que recibe una entrada de un millón de elementos tardará casi 32 años en completarse. Hacer ese algoritmo 100 veces más rápido aún llevaría 84 días.

Veremos un ejemplo de un algoritmo cuadrático cuando veamos el bubble sort.

El mejor caso, el caso promedio y el peor caso

Cuando decimos que un algoritmo es O(n), ¿qué estamos diciendo realmente? ¿Estamos diciendo que el algoritmo es O(n) en promedio? ¿O estamos describiendo el mejor o el peor escenario?

Normalmente nos referimos al peor escenario a menos que el caso común y el peor caso sean muy diferentes. Por ejemplo, en este libro veremos ejemplos donde un algoritmo es O(1) en promedio, pero periódicamente se convierte en O(n) (vea ArrayList.Add). En estos casos, describiré el algoritmo como O(1) en promedio y luego explicaré cuándo cambia la complejidad.

El punto clave es que decir O(n) no significa que siempre sean n operaciones. Podrían ser menos, pero no deberían ser más.

¿Qué estamos midiendo?

Cuando medimos algoritmos y estructuras de datos, generalmente estamos hablando de una de dos cosas: la cantidad de tiempo que la operación tarda en completarse (complejidad operacional) o la cantidad de recursos (memoria) que usa un algoritmo (complejidad de recursos).

Un algoritmo que se ejecuta diez veces más rápido pero usa diez veces más memoria puede ser perfectamente aceptable en un entorno de servidor con una gran cantidad de memoria disponible, pero puede no ser apropiado en un entorno integrado donde la memoria disponible está muy limitada.

En este libro me centraré principalmente en la complejidad operacional, pero en la sección de Algoritmos de Ordenamiento veremos algunos ejemplos de complejidad de recursos.

Algunos ejemplos específicos de cosas que podríamos medir incluyen:

  • Operaciones de comparación (mayor que, menor que, igual a).
  • Asignaciones e intercambio de datos.
  • Reservas de memoria.

El contexto de la operación que se realiza normalmente te dirá qué tipo de medición se está realizando.

Por ejemplo, cuando se analiza la complejidad de un algoritmo que busca un elemento dentro de una estructura de datos, es casi seguro que estamos hablando de operaciones de comparación. La búsqueda es generalmente una operación de solo lectura, por lo que no debería haber ninguna necesidad de realizar asignaciones o reservar memoria.

Sin embargo, cuando estamos hablando de ordenamiento de datos, podría ser lógico suponer que podríamos estar hablando de comparaciones, asignaciones o reservas. En los casos en que pueda haber ambigüedad, indicaré a qué tipo de medición se refiere realmente la complejidad.

A continuación

Esto completa la primera parte sobre algoritmos y estructuras de datos. A continuación, pasaremos a la lista enlazada.

Advertisement
Did you find this post useful?
Want a weekly email summary?
Subscribe below and we’ll send you a weekly email summary of all new Code tutorials. Never miss out on learning about the next big thing.
Advertisement
Looking for something to help kick start your next project?
Envato Market has a range of items for sale to help get you started.