Notación O grande es una poderosa herramienta utilizada en informática para describir la complejidad temporal o espacial de los algoritmos. Proporciona una forma estandarizada de comparar la eficiencia de diferentes algoritmos en términos de su peor desempeño. Comprensión Notación O grande Es esencial para analizar y diseñar algoritmos eficientes.
En este tutorial, cubriremos los conceptos básicos de Notación O grande , su importancia y cómo analizar la complejidad de los algoritmos utilizando O grande .
Tabla de contenidos
- ¿Qué es la notación O grande?
- Definición de notación O grande:
- ¿Por qué es importante la notación O grande?
- Propiedades de la notación O grande
- Notaciones comunes de O grande
- ¿Cómo determinar la notación O grande?
- Ejemplos matemáticos de análisis en tiempo de ejecución
- Ejemplos algorítmicos de análisis en tiempo de ejecución
- Clases de algoritmos con número de operaciones y tiempo de ejecución
- Comparación de la notación Big O, la notación Big Ω (Omega) y la notación Big θ (Theta)
- Preguntas frecuentes sobre la notación O grande
¿Qué es la notación O grande?
O grande , comúnmente conocido como Orden de , es una forma de expresar la límite superior de la complejidad temporal de un algoritmo, ya que analiza la peor de los casos situación del algoritmo. Proporciona un limite superior del tiempo que tarda un algoritmo en términos del tamaño de la entrada. Se denota como O(f(n)) , dónde f(n) es una función que representa el número de operaciones (pasos) que realiza un algoritmo para resolver un problema de tamaño norte .
Notación O grande se utiliza para describir el rendimiento o la complejidad de un algoritmo. En concreto, describe la peor de los casos en términos de tiempo o Complejidad espacial.
Punto importante:
- Notación O grande sólo describe el comportamiento asintótico de una función, no su valor exacto.
- El Notación O grande se puede utilizar para comparar la eficiencia de diferentes algoritmos o estructuras de datos.
Definición de notación O grande:
Dadas dos funciones f(n) y g(n) , Nosotros decimos eso f(n) es O(g(n)) si existen constantes c> 0 y norte 0 >= 0 tal que f(n) <= c*g(n) para todos norte>= norte 0 .
En términos más simples, f(n) es O(g(n)) si f(n) no crece más rápido que c*g(n) para todo n>= n0donde c y n0son constantes.
¿Por qué es importante la notación O grande?
La notación Big O es una notación matemática que se utiliza para describir la complejidad temporal o la eficiencia del peor de los casos de un algoritmo o la complejidad espacial del peor de los casos de una estructura de datos. Proporciona una forma de comparar el rendimiento de diferentes algoritmos y estructuras de datos, y de predecir cómo se comportarán a medida que aumente el tamaño de entrada.
La notación O grande es importante por varias razones:
- La notación Big O es importante porque ayuda a analizar la eficiencia de los algoritmos.
- Proporciona una manera de describir cómo tiempo de ejecución o requisitos de espacio de un algoritmo crecen a medida que aumenta el tamaño de entrada.
- Permite a los programadores comparar diferentes algoritmos y elegir el más eficiente para un problema específico.
- Ayuda a comprender la escalabilidad de los algoritmos y a predecir cómo funcionarán a medida que crezca el tamaño de la entrada.
- Permite a los desarrolladores optimizar el código y mejorar el rendimiento general.
Propiedades de la notación O grande:
A continuación se muestran algunas propiedades importantes de la notación O grande:
1. Reflexividad:
Para cualquier función f(n), f(n) = O(f(n)).
Ejemplo:
f(norte) = norte2, entonces f(n) = O(n2).
2. Transitividad:
Si f(n) = O(g(n)) y g(n) = O(h(n)), entonces f(n) = O(h(n)).
Ejemplo:
f(norte) = norte3, gramo(norte) = norte2, h(norte) = norte4. Entonces f(n) = O(g(n)) y g(n) = O(h(n)). Por lo tanto, f(n) = O(h(n)).
3. Factor constante:
Para cualquier constante c> 0 y funciones f(n) y g(n), si f(n) = O(g(n)), entonces cf(n) = O(g(n)).
freddie mercurio nacido
Ejemplo:
f(norte) = norte, gramo(norte) = norte2. Entonces f(n) = O(g(n)). Por lo tanto, 2f(n) = O(g(n)).
4. Regla de la suma:
Si f(n) = O(g(n)) y h(n) = O(g(n)), entonces f(n) + h(n) = O(g(n)).
Ejemplo:
f(norte) = norte2, gramo(norte) = norte3, h(norte) = norte4. Entonces f(n) = O(g(n)) y h(n) = O(g(n)). Por lo tanto, f(n) + h(n) = O(g(n)).
5. Regla del producto:
Si f(n) = O(g(n)) y h(n) = O(k(n)), entonces f(n) * h(n) = O(g(n) * k(n)) .
Ejemplo:
f(norte) = norte, gramo(norte) = norte2, h(norte) = norte3, k(norte) = norte4. Entonces f(n) = O(g(n)) y h(n) = O(k(n)). Por lo tanto, f(n) * h(n) = O(g(n) * k(n)) = O(n5).
6. Regla de composición:
Si f(n) = O(g(n)) y g(n) = O(h(n)), entonces f(g(n)) = O(h(n)).
Ejemplo:
f(norte) = norte2, gramo(norte) = norte, h(norte) = norte3. Entonces f(n) = O(g(n)) y g(n) = O(h(n)). Por lo tanto, f(g(n)) = O(h(n)) = O(n3).
Notaciones comunes de O grande:
La notación Big-O es una forma de medir la complejidad temporal y espacial de un algoritmo. Describe el límite superior de la complejidad en el peor de los casos. Analicemos los diferentes tipos de complejidades temporales:
1. Complejidad del tiempo lineal: gran complejidad O(n)
La complejidad del tiempo lineal significa que el tiempo de ejecución de un algoritmo crece linealmente con el tamaño de la entrada.
Por ejemplo, considere un algoritmo que atraviesa una matriz para encontrar un elemento específico :
Fragmento de código bool findElement(int arr[], int n, int key) { for (int i = 0; i < n; i++) { if (arr[i] == key) { return true; } } return false; }> 2. Complejidad del tiempo logarítmico: gran complejidad O (log n)
La complejidad del tiempo logarítmico significa que el tiempo de ejecución de un algoritmo es proporcional al logaritmo del tamaño de entrada.
Por ejemplo, un algoritmo de búsqueda binaria tiene una complejidad de tiempo logarítmica:
Fragmento de código int binarySearch(int arr[], int l, int r, int x) { if (r>= l) { int medio = l + (r - l) / 2; if (arr[mid] == x) return mid; if (arr[mid]> x) return binarioSearch(arr, l, mid - 1, x); devolver búsqueda binaria (arr, mid + 1, r, x); } devolver -1; }> 3. Complejidad del tiempo cuadrático: Big O(n)2) Complejidad
La complejidad del tiempo cuadrático significa que el tiempo de ejecución de un algoritmo es proporcional al cuadrado del tamaño de entrada.
Por ejemplo, una sencilla algoritmo de clasificación de burbujas tiene una complejidad de tiempo cuadrática:
Fragmento de código void bubbleSort(int arr[], int n) { for (int i = 0; i < n - 1; i++) { for (int j = 0; j < n - i - 1; j++) { if (arr[j]>arr[j + 1]) { intercambiar(&arr[j], &arr[j + 1]); } } } }> 4. Complejidad del tiempo cúbico: Big O(n)3) Complejidad
La complejidad del tiempo cúbico significa que el tiempo de ejecución de un algoritmo es proporcional al cubo del tamaño de entrada.
Por ejemplo, un ingenuo algoritmo de multiplicación de matrices tiene una complejidad de tiempo cúbica:
Fragmento de código void multiply(int mat1[][N], int mat2[][N], int res[][N]) { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { res[i][j] = 0; for (int k = 0; k < N; k++) res[i][j] += mat1[i][k] * mat2[k][j]; } } }> 5. Complejidad del tiempo polinomial: Big O(n)k) Complejidad
La complejidad del tiempo polinomial se refiere a la complejidad del tiempo de un algoritmo que se puede expresar como una función polinómica del tamaño de entrada. norte . en grande oh notación, se dice que un algoritmo tiene complejidad temporal polinomial si su complejidad temporal es En k ) , dónde k es una constante y representa el grado del polinomio.
Los algoritmos con complejidad de tiempo polinomial generalmente se consideran eficientes, ya que el tiempo de ejecución crece a un ritmo razonable a medida que aumenta el tamaño de la entrada. Ejemplos comunes de algoritmos con complejidad de tiempo polinomial incluyen complejidad del tiempo lineal O (n) , complejidad del tiempo cuadrático O (n 2 ) , y complejidad del tiempo cúbico O (n 3 ) .
6. Complejidad temporal exponencial: Big O(2)norte) Complejidad
La complejidad del tiempo exponencial significa que el tiempo de ejecución de un algoritmo se duplica con cada adición al conjunto de datos de entrada.
Por ejemplo, el problema de generando todos los subconjuntos de un conjunto es de complejidad temporal exponencial:
Fragmento de código void generateSubsets(int arr[], int n) { for (int i = 0; i < (1 << n); i++) { for (int j = 0; j < n; j++) { if (i & (1 << j)) { cout << arr[j] << ' '; } } cout << endl; } }> Complejidad del tiempo factorial: gran complejidad O(n!)
La complejidad del tiempo factorial significa que el tiempo de ejecución de un algoritmo crece factorialmente con el tamaño de la entrada. Esto se ve a menudo en algoritmos que generan todas las permutaciones de un conjunto de datos.
A continuación se muestra un ejemplo de un algoritmo de complejidad temporal factorial, que genera todas las permutaciones de una matriz:
Fragmento de código void permute(int* a, int l, int r) { if (l == r) { for (int i = 0; i <= r; i++) { cout << a[i] << ' '; } cout << endl; } else { for (int i = l; i <= r; i++) { swap(a[l], a[i]); permute(a, l + 1, r); swap(a[l], a[i]); // backtrack } } }> Si trazamos los ejemplos más comunes de notación O grande, tendríamos un gráfico como este:
¿Cómo determinar la notación O grande?
Notación O grande es una notación matemática utilizada para describir la comportamiento asintótico de una función a medida que su entrada crece infinitamente. Proporciona una forma de caracterizar la eficiencia de algoritmos y estructuras de datos.
Pasos para determinar la notación O grande:
1. Identifique el término dominante:
número aleatorio gen java
- Examine la función e identifique el término con el mayor orden de crecimiento a medida que aumenta el tamaño de la entrada.
- Ignore cualquier factor constante o términos de orden inferior.
2. Determine el orden de crecimiento:
- El orden de crecimiento del término dominante determina la notación O grande.
3. Escribe la notación O grande:
- La notación O grande se escribe como O(f(n)), donde f(n) representa el término dominante.
- Por ejemplo, si el término dominante es n^2, la notación O grande sería O(n^2).
4. Simplifique la notación (opcional):
- En algunos casos, el Marca grande O n se puede simplificar eliminando factores constantes o utilizando una notación más concisa.
- Por ejemplo, O(2norte) se puede simplificar a En).
Ejemplo:
Función: f(n) = 3n3+ 2n2+ 5n + 1
- Término dominante: 3n3
- Orden de crecimiento: cúbico (n3)
- Notación O grande: O (n3)
- Notación simplificada: O(n3)
Ejemplos matemáticos de análisis en tiempo de ejecución:
La siguiente tabla ilustra el análisis en tiempo de ejecución de diferentes órdenes de algoritmos a medida que aumenta el tamaño de entrada (n).
| norte | registro(n) | norte | norte * registro(norte) | n^2 | 2^n | ¡norte! |
|---|---|---|---|---|---|---|
| 10 | 1 | 10 | 10 | 100 | 1024 | 3628800 |
| 20 | 2.996 | 20 | 59.9 | 400 | 1048576 | 2.432902e+1818 |
Ejemplos algorítmicos de análisis en tiempo de ejecución:
La siguiente tabla clasifica los algoritmos según su complejidad de tiempo de ejecución y proporciona ejemplos para cada tipo.
| Tipo | Notación | Algoritmos de ejemplo |
|---|---|---|
| logarítmico | O(log n) | Búsqueda binaria |
| Lineal | En) | Búsqueda lineal |
| superlineal | O(n iniciar sesión n) | Ordenar en montón, ordenar por combinación |
| Polinomio | O(n^c) | Multiplicación de matrices de Strassen, clasificación por burbujas, clasificación por selección, clasificación por inserción, clasificación por cubos |
| Exponencial | O(c^n) | Torre de Hanoi |
| Factorial | ¡En!) | Expansión determinante por parte de menores, algoritmo de búsqueda de fuerza bruta para el problema del viajante |
Clases de algoritmos con número de operaciones y tiempo de ejecución:
A continuación se muestran las clases de algoritmos y sus tiempos de ejecución en una computadora que ejecuta 1 millón de operaciones por segundo (1 segundo = 10 6 μs = 10 3 ms) :
Clases de notación O grande | f(n) | Análisis Big O (número de operaciones) para n = 10 | Tiempo de ejecución (1 instrucción/μseg) |
|---|---|---|---|
constante | O(1) | 1 | 1 μs |
logarítmico | O(iniciar sesión) | 3.32 | 3 μs |
lineal | En) | 10 | 10 μs |
O (iniciar sesión) | O (iniciar sesión) | 33.2 | 33 μs |
cuadrático | En2) | 102 | 100 μs |
cúbico | En3) | 103 | 1 ms |
exponencial | o(2norte) | 1024 | 10 ms |
factorial | ¡En!) java está vacío | 10! | 3,6288 seg |
Comparación de la notación Big O, la notación Big Ω (Omega) y la notación Big θ (Theta):
A continuación se muestra una tabla que compara la notación Big O, la notación Ω (Omega) y la notación θ (Theta):
| Notación | Definición | Explicación |
|---|---|---|
| O grande (O) | f(n) ≤ C * g(n) para todo n ≥ n0 | Describe el límite superior del tiempo de ejecución del algoritmo en el peor de los casos . |
| Ω (Omega) | f(n) ≥ C * g(n) para todo n ≥ n0 | Describe el límite inferior del tiempo de ejecución del algoritmo en el mejor caso . |
| θ (theta) | C1* gramo(norte) ≤ f(norte) ≤ C2* g(n) para n ≥ n0 | Describe los límites superior e inferior del algoritmo. tiempo de ejecución . |
En cada notación:
- f(n) representa la función que se analiza, normalmente la complejidad temporal del algoritmo.
- g(n) representa una función específica que limita f(n) .
- C, C1, y C2 son constantes.
- norte 0 es el tamaño mínimo de entrada más allá del cual se mantiene la desigualdad.
Estas notaciones se utilizan para analizar algoritmos en función de su peor de los casos (Gran O) , mejor caso (Ω) , y caso promedio (θ) escenarios.
Preguntas frecuentes sobre la notación O grande:
Pregunta 1. ¿Qué es la notación O grande?
Respuesta: La notación Big O es una notación matemática que se utiliza para describir el límite superior de la complejidad temporal de un algoritmo en términos de cómo crece en relación con el tamaño de la entrada.
Pregunta 2. ¿Por qué es importante la notación O grande?
Respuesta: Nos ayuda a analizar y comparar la eficiencia de los algoritmos centrándonos en el peor de los casos y entendiendo cómo su rendimiento aumenta con el tamaño de la entrada.
Pregunta 3. ¿Cómo se calcula la notación O grande?
Respuesta: La notación Big O se determina identificando la operación dominante en un algoritmo y expresando su complejidad temporal en términos de n, donde n representa el tamaño de entrada.
Pregunta 4. ¿Qué significa O(1) en notación O grande?
Respuesta: O(1) significa complejidad de tiempo constante, lo que indica que el tiempo de ejecución de un algoritmo no cambia independientemente del tamaño de entrada.
Pregunta 5. ¿Cuál es el significado de las diferentes complejidades de Big O como O (log n) u O (n ^ 2)?
Respuesta: Diferentes complejidades como O(log n) u O(n^2) representan cómo el rendimiento de un algoritmo aumenta a medida que aumenta el tamaño de la entrada, lo que proporciona información sobre su eficiencia y escalabilidad.
Pregunta 6. ¿Se puede aplicar también la notación Big O a la complejidad del espacio?
Respuesta: Sí, la notación Big O también se puede utilizar para analizar y describir la complejidad espacial de un algoritmo, indicando cuánta memoria requiere en relación con el tamaño de entrada.
Artículo relacionado:
- Ejemplos de análisis Big-O
- Diseño y Análisis de Algoritmos
- Tipos de notaciones asintóticas en el análisis de complejidad de algoritmos
- Análisis de Algoritmos | Grande – Notación Ω (Grande-Omega)
- Análisis de Algoritmos | pequeñas notaciones o y omega pequeñas