Notación o grande en la estructura de datos: todo lo que debe saber

La notación Big O en una estructura de datos se usa para determinar la eficiencia de un algoritmo, la cantidad de tiempo que lleva ejecutar la función con el crecimiento de la entrada y qué tan bien escala la función. La medición de esta eficiencia se puede dividir en dos partes, a saber, la complejidad del espacio y la complejidad del tiempo.

La notación Big O se refiere a la notación matemática que actúa como un factor limitante de cualquier función cuando un argumento es más propenso a inclinarse hacia un valor específico o infinito. Pertenece a la categoría de notaciones matemáticas inventadas por Edmund Landau, Paul Bachmann y otros. Por lo tanto, se denomina colectivamente la notación de Bachmann-Landau o la notación asintótica.

Según la deducción matemática, dos funciones, f(n) y g(n) se definen sobre un conjunto de números reales o positivos que no están ligados. Aquí, g(n) es estrictamente positivo para todo valor grande de n. Se puede escribir de la siguiente manera:

f(n) = O(g(n)) donde n tiende a infinito (n → ∞)

Sin embargo, aquí, la suposición de n a infinito no está definida exclusivamente, por lo que la expresión anterior se puede escribir como:

f(n) = O(g(n))

Aquí, f y g son las funciones necesarias que parten de números enteros positivos a números reales que no son negativos.

Por lo tanto, los valores grandes de n se denotan con la asintótica Big O.

Propiedades de la notación Big O en la estructura de datos

El algoritmo Big O en la estructura de datos tiene bastantes propiedades requeridas obligatoriamente. Dichas propiedades esenciales de la notación Big O son las siguientes:

• Función de suma:
  Si f(n) = f 1 (n) + f 2 (n) + — + f m (n) y f i (n)≤ f i +1(n) ∀ i=1, 2,–, m,
  entonces O(f(n)) = O(max(f1(n), f2(n), –, fm(n))).
• Función logarítmica:
  Si f(n) = logan y g(n)=logbn,
  entonces O(f(n))=O(g(n))
• Multiplicación constante:
  Si f(n) = cg(n), entonces O(f(n)) = O(g(n)) en la que c es una constante distinta de cero.
• Función polinómica:
  Si f(n) = a0 + a1.n + a2.n2 + — + am.nm,
  entonces O(f(n)) = O(nm).

Aprenda cursos de desarrollo de software en línea de las mejores universidades del mundo. Obtenga Programas PG Ejecutivos, Programas de Certificado Avanzado o Programas de Maestría para acelerar su carrera.

Explore nuestros cursos populares de ingeniería de software

Aquí, al abordar Big O, cada función de registro individual aumenta de manera similar.

Importancia de la notación Big O en el análisis de tiempo de ejecución de algoritmos

Las complejidades del tiempo de ejecución del algoritmo en el peor de los casos se utilizan para realizar comparaciones y cálculos, especialmente en el caso de analizar el rendimiento de un algoritmo. El orden de O(1), representado como el tiempo de ejecución constante, es el tiempo de ejecución más rápido del algoritmo: el tiempo que tarda el algoritmo es el mismo para varios tamaños de entrada. Es importante tener en cuenta que el tiempo de ejecución ideal de un algoritmo es el tiempo de ejecución constante, que rara vez se logra porque el tiempo de ejecución del algoritmo depende del tamaño de entrada de n.

Por ejemplo:

Como se mencionó anteriormente, el rendimiento en tiempo de ejecución de un algoritmo depende en gran medida del tamaño de entrada de n. Aclaremos este hecho con algunos ejemplos matemáticos para realizar el análisis en tiempo de ejecución de un algoritmo para varios tamaños de n:

• norte = 20
  registro (20) = 2,996;
  20 = 20;
  20 log (20) = 59,9;
  20 2 = 400;
  2 20 = 1084576;
  20! = 2,432902 + 18 18 ;
• norte = 10
  registro (10) = 1;
  10 = 10;
  10 registro (10) = 10;
  10 2 = 100;
  2 10 = 1024;
  10! = 3628800;

El rendimiento en tiempo de ejecución de un algoritmo se calcula de manera similar.

Aquí hay algunos otros ejemplos algorítmicos de análisis de tiempo de ejecución:

• Cuando se trata de búsqueda lineal, la complejidad del tiempo de ejecución es O(n).
• La complejidad del tiempo de ejecución es O(log n) para la búsqueda binaria.
• Para la ordenación por selección, la ordenación por burbujas, la ordenación por cubos, la ordenación por inserción, la complejidad del tiempo de ejecución es O(n^c).
• Cuando se trata de algoritmos exponenciales como Tower of Hanoi, la complejidad del tiempo de ejecución es O(c^n).
• Para Merge SortSort y Heap Sort, la complejidad del tiempo de ejecución es O(n log n).

¿Cómo analiza Big O la complejidad del espacio?

Determinar la complejidad tanto del espacio como del tiempo de ejecución para un algoritmo es un paso esencial. Esto se debe a que podemos determinar el tiempo de ejecución que tarda un algoritmo analizando el rendimiento del tiempo de ejecución del algoritmo y el espacio de memoria que ocupa el algoritmo mediante el análisis de la complejidad del espacio del algoritmo. Por lo tanto, para medir la complejidad espacial de un algoritmo, debemos comparar el desempeño de la complejidad espacial del algoritmo en el peor de los casos.

Para determinar la complejidad espacial de un algoritmo, debemos seguir estas dos tareas:

Tarea 1: Es vital implementar el programa para un algoritmo en particular.

Tarea 2: es esencial conocer el tamaño de la entrada n para determinar la memoria que contendrá cada elemento.

Estas dos tareas esenciales deben realizarse antes de calcular la complejidad del espacio para un algoritmo.

Ejemplos de algoritmos de complejidad espacial

Hay muchos ejemplos de algoritmos con complejidad espacial, algunos de los cuales se mencionan a continuación para una mejor comprensión de este tipo de algoritmo:

• Para la clasificación de burbujas, la búsqueda lineal, la clasificación de selección, la clasificación de inserción, la clasificación de montones y la búsqueda binaria, la complejidad del espacio es O(1) .
• La complejidad del espacio es O(n+k) cuando se trata de ordenar radix .
• La complejidad del espacio es O(n) para SortSort rápido.
• La complejidad del espacio es O (log n) para la ordenación por fusión.

Ejemplo de notación Big O en C

Es un hecho que la notación Big O se usa principalmente en informática para determinar la complejidad o el rendimiento de un algoritmo. Esta notación nos brinda la capacidad de clasificar el comportamiento de los algoritmos según el crecimiento del espacio de memoria o los requisitos de tiempo de ejecución cuando la extensión de los datos de entrada se vuelve grande. No está diseñado para predecir el uso real de la memoria o el tiempo de ejecución, sino para comparar algoritmos y luego seleccionar el mejor entre ellos para el trabajo. No es específico del idioma, pero también se implementa en C.

A continuación, encontrará el algoritmo de clasificación de selección en C donde se ha calculado la complejidad del peor de los casos (notación Big O) del algoritmo:

para(int i=0; i<n; i++)

{

int min = i;

para(int j=i; j<n; j++)

{

if(matriz[j]<matriz[min])

mín=j;

}

int temp = arreglo[i];

arreglo[i] = arreglo[min];

matriz[min] = temperatura;

}

Para analizar el algoritmo:

• Ya se puede denotar que el rango del ciclo for externo es i < n , lo que establece que el orden del ciclo es O(n).
• A continuación, podemos identificar que también es O(n) cuando j < n para el bucle for interno.
• La constante se ignora, incluso si la eficiencia promedio se encuentra n/2 para una constante c. Entonces, el orden es O(n).
• Después de multiplicar el orden del ciclo interno y del ciclo externo, la complejidad del tiempo de ejecución lograda es O(n^2).

Se pueden implementar fácilmente otros algoritmos en C, donde las complejidades se pueden analizar y determinar fácilmente de manera similar.

Uso de la notación Big O

Hay dos áreas principales donde se aplica la notación Big O: -

• Matemáticas : la notación Big O se usa con bastante frecuencia en el campo de las matemáticas para describir cómo una serie finita se aproxima mucho a una función, especialmente cuando se trata de los casos de una expansión asintótica o una serie de Taylor truncada.
• Informática: es un hecho bien establecido que la notación Big O se usa principalmente en el campo de la informática debido a su utilidad en el análisis de algoritmos.

Sin embargo, en ambas aplicaciones, la función g ( x ) que aparece dentro de O (·) a menudo se elige como posiblemente la más simple si se omiten los términos de orden inferior y los factores constantes.

Hay otros dos usos de esta notación que son formalmente cercanos pero relativamente diferentes. Están:-

• Asintóticas infinitas
• Asintóticas infinitesimales.

Sin embargo, esta distinción no es en principio, en aplicación solo con la definición formal de la "Gran O" siendo exactamente la misma para ambos casos. La única diferencia son los límites para el argumento de la función.

Lea nuestros artículos populares relacionados con el desarrollo de software

Conclusión

En conclusión, podemos decir que Big Data juega un papel integral en las estructuras de datos, y tener un conocimiento profundo y completo sobre la notación Big O es un excelente conjunto de habilidades para poseer. Tiene una gran demanda en el sector laboral y puede ser potencialmente una excelente opción para una carrera profesional. El Programa de Certificado Avanzado en Big Data de upGrad le dará el impulso que necesita para impulsar su carrera. Le presentará las mejores habilidades profesionales como el procesamiento de datos con PySpark, el almacenamiento de datos, MapReduce, el procesamiento de Big Data en la nube de AWS, el procesamiento en tiempo real, etc.