Requisito previo - Notaciones asintóticas , Propiedades de las notaciones asintóticas , Análisis de algoritmos
1. Notación O grande (O):
Se define como límite superior y el límite superior de un algoritmo es la mayor cantidad de tiempo requerida (el peor de los casos de rendimiento).
Notación O grande se utiliza para describir el límite superior asintótico .
Matemáticamente, si f(n) describe el tiempo de ejecución de un algoritmo; f(n) es O(g(n)) si existe una constante positiva C y n0 tal que,
0 <= f(n) = n0
norte = usado para dar una función al límite superior.
Si una función es En) , es automáticamente O (n-cuadrado) también.
Ejemplo gráfico para O grande:
arquitectura java
2. Notación Omega grande (Ω):
Se define como límite inferior y el límite inferior de un algoritmo es la menor cantidad de tiempo requerida (la forma más eficiente posible, en otras palabras, el mejor de los casos).
Al igual que oh notación proporcionar un límite superior asintótico , Oh notación proporciona límite inferior asintótico .
Dejar f(n) definir el tiempo de ejecución de un algoritmo;
f(n) se ha dicho Ω(g(n)) si existe una constante positiva C y (n0) tal que
0 <= Cg(n) = n0
conversión de tipos y conversión de tipos en java
norte = utilizado para dar un límite inferior en una función
Si una función es Ω(n-cuadrado) es automaticamente Oh(n) también.
Ejemplo gráfico para Omega grande (Ω):
3. Notación Theta grande (Θ):
Se define como el límite más estricto y el límite más estricto es el mejor de todos los peores tiempos que puede tomar el algoritmo.
Dejar f(n) definir el tiempo de ejecución de un algoritmo.
f(n) se ha dicho Θ(g(n)) si f(n) es O(g(n)) y f(n) es Ω(g(n)).
Matemáticamente,
0 <= f(n) = n0
0 <= C2g(n) = n0Combinando ambas ecuaciones, obtenemos:
encontrar mi iphone android0 <= C2g(n) <= f(n) = n0
La ecuación simplemente significa que existen constantes positivas C1 y C2 tales que f(n) está entre C2 g(n) y C1g(n).
Ejemplo gráfico de Gran Theta (Θ) :
Diferencia entre Big oh, Big Omega y Big Theta:
| S.No. | O grande | Gran Omega ( Oh) | gran theta (t) |
|---|---|---|---|
| 1. | Es como (<=) La tasa de crecimiento de un algoritmo es menor o igual a un valor específico. | Es como (>=) La tasa de crecimiento es mayor o igual a un valor específico. | es como (==) lo que significa que la tasa de crecimiento es igual a un valor específico. |
| 2. | El límite superior del algoritmo está representado por la notación O grande. Sólo la función anterior está delimitada por Big O. El límite superior asintótico viene dado por la notación Big O. | El límite inferior del algoritmo está representado por la notación Omega. El límite inferior asintótico viene dado por la notación Omega. | La delimitación de funciones desde arriba y desde abajo se representa mediante notación theta. El comportamiento asintótico exacto se realiza mediante esta notación theta. |
| 3. | O grande – Límite superior | Gran Omega (Ω) – Límite inferior | Gran Theta (Θ) – Apretado |
| 4. | Se define como límite superior y el límite superior de un algoritmo es la mayor cantidad de tiempo requerida (el peor de los casos de rendimiento). | Se define como límite inferior y el límite inferior de un algoritmo es la menor cantidad de tiempo requerida (la forma más eficiente posible, en otras palabras, el mejor de los casos). | Se define como el límite más estricto y el límite más estricto es el mejor de todos los peores tiempos que puede tomar el algoritmo. |
| 5. | Matemáticamente: Big Oh es 0 <= f(n) = n0 | Matemáticamente: Big Omega es 0 <= Cg(n) = n0 | Matemáticamente: Big Theta es 0 <= C2g(n) <= f(n) = n0 |
Para obtener más detalles, consulte: Diseño y Análisis de Algoritmos .