En el análisis de algoritmos , las notaciones asintóticas se utilizan para evaluar el rendimiento de un algoritmo, en sus mejores y peores casos . Este artículo discutirá las notaciones Big – Theta representadas por una letra griega (Θ).
Definición: Sean g y f la función del conjunto de los números naturales a sí mismo. Se dice que la función f es Θ(g), si existen constantes c 1 , c 2 > 0 y un número natural n 0 tal que c 1 * g(n) ≤ f(n) ≤ c 2 * g(n ) para todo n ≥ n 0
Representación Matemática:
Θ (g(n)) = {f(n): existen constantes positivas c 1 , c 2 y n 0 tales que 0 ≤ c 1 * g(n) ≤ f(n) ≤ c 2 * g(n) para todo n ≥ n 0 }
Nota: Θ(g) es un conjunto
La definición anterior significa que, si f(n) es theta de g(n), entonces el valor de 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 negativa para valores de n mayores que n 0 .
Representación grafica:
Representación grafica
En un lenguaje sencillo, la notación Big – Theta(Θ) especifica los límites asintóticos (tanto superior como inferior) para una función f(n) y proporciona la complejidad de tiempo 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.
- Encuentra todos los tipos y número de entradas y calcula el número de operaciones que tardan en ejecutarse. Asegúrese de que los casos de entrada estén igualmente distribuidos.
- 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: considere un ejemplo para averiguar si una clave existe en una array o no mediante la búsqueda lineal . La idea es recorrer la array y verificar cada elemento si es igual a la clave o no.
El pseudocódigo es el siguiente:
bool linearSearch(int a[], int n, int key)
{
for (int i = 0; i < n; 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 <bits/stdc++.h>
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 < n; 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 < n; 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 < n; 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
<script>
// 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 < n; 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
</script>
Element is present in array
En un problema de búsqueda lineal, supongamos que todos los casos están distribuidos uniformemente (incluido el caso en que la clave está ausente en la array). 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 de tiempo de caso promedio =
⇒
⇒
⇒
(se eliminan las constantes)
Cuándo usar la notación Big – Θ: 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 de tiempo promedio de un algoritmo, que es más preciso durante el análisis, sin embargo, en la práctica a veces se vuelve difícil encontrar el conjunto uniformemente distribuido de entradas para un algoritmo, en ese caso, se usa la notación Big-O que representa el límite superior asintótico de una función f.
Para más detalles, consulte:
Diseño y Análisis de Algoritmos .
Publicación traducida automáticamente
Artículo escrito por UtkarshPandey6 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA