En el análisis de algoritmos , las notaciones asintóticas se utilizan para evaluar el rendimiento de un algoritmo, en su mejores y peores casos . Este artículo analizará las notaciones Big – Theta representadas por una letra griega (Θ).
Definición: Sean g y f la función del conjunto de números naturales respecto de sí mismo. Se dice que la función f es Θ(g), si existen constantes c1, C2> 0 y un número natural n0tal que c1* gramo(norte) ≤ f(norte) ≤ c2* g(n) para todo n ≥ n0
Representación matemática:
Θ (g(n)) = {f(n): existen constantes positivas c1, C2y N0tal que 0 ≤ c1* gramo(norte) ≤ f(norte) ≤ c2* g(n) para todo n ≥ n0}
Nota: Θ(g) es un conjunto
La definición anterior significa que si f(n) es theta de g(n), entonces el valor f(n) siempre está entre c1 * g(n) y c2 * g(n) para valores grandes de n (n ≥ n).0). La definición de theta también requiere que f(n) no sea negativo para valores de n mayores que n.0.
clase abstracta en java
Representación grafica:
Representación grafica
En lenguaje sencillo, la notación Big – Theta(Θ) especifica límites asintóticos (tanto superiores como inferiores) para una función f(n) y proporciona la complejidad temporal promedio de un algoritmo.
Siga los pasos a continuación para encontrar la complejidad de tiempo promedio de cualquier programa:
- Divida el programa en segmentos más pequeños.
- Encuentre todos los tipos y cantidad de entradas y calcule la cantidad de operaciones que tardan en ejecutarse. Asegúrese de que los casos de entrada estén distribuidos equitativamente.
- Encuentre la suma de todos los valores calculados y divida la suma por el número total de entradas, digamos que la función de n obtenida es g (n) después de eliminar todas las constantes, luego en notación Θ se representa como Θ (g (n))
Ejemplo: Consideremos un ejemplo para encontrar si una clave existe en una matriz o no usando la búsqueda lineal . La idea es atravesar la matriz y verifique cada elemento si es igual a la clave o no.
enumerar métodos java
El pseudocódigo es el siguiente:
bool linearSearch(int a[], int n, int key) { for (int i = 0; i if (a[i] == key) return true; } return false; }>A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach> #include> using> namespace> std;> // Function to find whether a key exists in an> // array or not using linear search> bool> linearSearch(>int> a[],>int> n,>int> key)> {> >// Traverse the given array, a[]> >for> (>int> i = 0; i // Check if a[i] is equal to key if (a[i] == key) return true; } return false; } // Driver Code int main() { // Given Input int arr[] = { 2, 3, 4, 10, 40 }; int x = 10; int n = sizeof(arr) / sizeof(arr[0]); // Function Call if (linearSearch(arr, n, x)) cout << 'Element is present in array'; else cout << 'Element is not present in array'; return 0; }> |
>
>
Java
// Java program for the above approach> import> java.lang.*;> import> java.util.*;> class> GFG{> // Function to find whether a key exists in an> // array or not using linear search> static> boolean> linearSearch(>int> a[],>int> n,> >int> key)> {> > >// Traverse the given array, a[]> >for>(>int> i =>0>; i { // Check if a[i] is equal to key if (a[i] == key) return true; } return false; } // Driver code public static void main(String[] args) { // Given Input int arr[] = { 2, 3, 4, 10, 40 }; int x = 10; int n = arr.length; // Function Call if (linearSearch(arr, n, x)) System.out.println('Element is present in array'); else System.out.println('Element is not present in array'); } } // This code is contributed by avijitmondal1998> |
>
>
Python3
# Python3 program for the above approach> # Function to find whether a key exists in an> # array or not using linear search> def> linearSearch(a, n, key):> ># Traverse the given array, a[]> >for> i>in> range>(>0>, n):> ># Check if a[i] is equal to key> >if> (a[i]>=>=> key):> >return> True> > >return> False> # Driver Code> # Given Input> arr>=> 2>,>3>,>4>,>10>,>40> x>=> 10> n>=> len>(arr)> # Function Call> if> (linearSearch(arr, n, x)):> >print>(>'Element is present in array'>)> else>:> >print>(>'Element is not present in array'>)> > # This code is contributed by shivanisinghss2110> |
>
>
C#
// C# program for above approach> using> System;> class> GFG{> // Function to find whether a key exists in an> // array or not using linear search> static> bool> linearSearch(>int>[] a,>int> n,> >int> key)> {> > >// Traverse the given array, a[]> >for>(>int> i = 0; i { // Check if a[i] is equal to key if (a[i] == key) return true; } return false; } // Driver Code static void Main() { // Given Input int[] arr = { 2, 3, 4, 10, 40 }; int x = 10; int n = arr.Length; // Function Call if (linearSearch(arr, n, x)) Console.Write('Element is present in array'); else Console.Write('Element is not present in array'); } } // This code is contributed by sanjoy_62.> |
>
>
JavaScript
> // JavaScript program for the above approach> // Function to find whether a key exists in an> // array or not using linear search> function> linearSearch(a, n, key)> {> > >// Traverse the given array, a[]> >for>(>var> i = 0; i { // Check if a[i] is equal to key if (a[i] == key) return true; } return false; } // Driver code // Given Input var arr = [ 2, 3, 4, 10, 40 ]; var x = 10; var n = arr.length; // Function Call if (linearSearch(arr, n, x)) document.write('Element is present in array'); else document.write('Element is not present in array'); // This code is contributed by shivanisinghss2110> |
>
>
Producción
Element is present in array>
Complejidad del tiempo: En)
Espacio Auxiliar: O(1)
En un problema de búsqueda lineal, supongamos que todos los casos son distribuido uniformemente (incluido el caso en el que la clave no está en la matriz). Entonces, suma todos los casos (cuando la clave está presente en la posición 1, 2, 3, ……, n y no está presente, y divide la suma por n + 1.
Complejidad promedio del tiempo de caso =
⇒
⇒
⇒
(se eliminan las constantes)
objeto java
Cuándo utilizar la notación Grande – Θ: Big – Θ analiza un algoritmo con la precisión más precisa, ya que al calcular Big – Θ, se considera una distribución uniforme de diferentes tipos y longitudes de entradas, proporciona la complejidad temporal promedio de un algoritmo, que es más preciso al analizar, sin embargo, en la práctica. A veces resulta difícil encontrar el conjunto de entradas uniformemente distribuidas para un algoritmo; en ese caso, Notación O grande se utiliza que representa el límite superior asintótico de una función f.
Para obtener más detalles, consulte: Diseño y Análisis de Algoritmos .