Análisis de Algoritmos | Notación Big – Ω (Big-Omega)

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á la notación grande – Omega representada 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 existe una constante c > 0 y un número natural n ₀ tal que c*g(n) ≤ f(n) para todo n ≥ n ₀

Representación Matemática:

Ω(g) = {f(n): existen constantes positivas c y n ₀ tales que 0 ≤ c*g(n) ≤ f(n) para todo n ≥ n ₀ } 
Nota: Ω (g) es un conjunto

Representación grafica:

Representación grafica

En lenguaje simple, la notación Big – Omega(Ω) especifica el límite inferior asintótico (en el extremo) para una función f(n).

Siga los pasos a continuación para calcular Big – Omega (Ω) para cualquier programa:

1. Divida el programa en segmentos más pequeños.
2. Encuentre el número de operaciones realizadas para cada segmento (en términos del tamaño de entrada) asumiendo que la entrada dada es tal que el programa toma la menor cantidad de tiempo.
3. Sume todas las operaciones y simplifique, digamos que es f(n).
4. Elimine todas las constantes y elija el término de menor orden o cualquier otra función que sea siempre menor que f(n) cuando n tiende a infinito, digamos que es g(n) entonces, Big – Omega (Ω) de f( n) es Ω(g(n)).

Ejemplo: Considere un ejemplo para imprimir todos los pares posibles de una array . La idea es ejecutar dos bucles anidados para generar todos los pares posibles de la array dada.

El pseudocódigo es el siguiente:

int print(int a[], int n)
{
    for (int i = 0; i < n; i++) 
    {
        for (int j = 0; j < n; j++)
        {
            if(i != j)
                cout << a[i] << " " 
                     << a[j] << "\n";
        }
    }
}

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
  
// Function to print all possible pairs
int print(int a[], int n)
{
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i != j)
                cout << a[i] << " " << a[j] << "\n";
        }
    }
}
  
// Driver Code
int main()
{
  
    // Given array
    int a[] = { 1, 2, 3 };
  
    // Store the size of the array
    int n = sizeof(a) / sizeof(a[0]);
  
    // Function Call
    print(a, n);
  
    return 0;
}

// Java program for the above approach
import java.lang.*;
import java.util.*;
  
class GFG{
  
// Function to print all possible pairs
static void print(int a[], int n)
{
    for(int i = 0; i < n; i++) 
    {
        for(int j = 0; j < n; j++) 
        {
            if (i != j)
                System.out.println(a[i] + " " + a[j]);
        }
    }
}
  
// Driver code
public static void main(String[] args)
{
      
    // Given array
    int a[] = { 1, 2, 3 };
  
    // Store the size of the array
    int n = a.length;
  
    // Function Call
    print(a, n);
}
}
  
// This code is contributed by avijitmondal1998

# Python3 program for the above approach
  
# Function to print all possible pairs
def printt(a, n) :
      
    for i in range(n) :
        for j in range(n) :
            if (i != j) :
                print(a[i], "", a[j])
  
# Driver Code
  
# Given array
a = [ 1, 2, 3 ]
  
# Store the size of the array
n = len(a) 
  
# Function Call
printt(a, n)
  
# This code is contributed by splevel62.

// C# program for above approach
using System;
  
class GFG{
  
  
// Function to print all possible pairs
static void print(int[] a, int n)
{
    for(int i = 0; i < n; i++) 
    {
        for(int j = 0; j < n; j++) 
        {
            if (i != j)
                Console.WriteLine(a[i] + " " + a[j]);
        }
    }
}
  
  
// Driver Code
static void Main()
{
     // Given array
    int[] a = { 1, 2, 3 };
  
    // Store the size of the array
    int n = a.Length;
  
    // Function Call
    print(a, n);
}
}
  
// This code is contributed by sanjoy_62.

<script>
  
// JavaScript program for the above approach
  
// Function to print all possible pairs
function print(a, n)
{
    for(let i = 0; i < n; i++) 
    {
        for(let j = 0; j < n; j++) 
        {
            if (i != j)
                document.write(a[i] + " " + 
                               a[j] + "<br>");
        }
    }
}
  
// Driver Code
  
// Given array
let a = [ 1, 2, 3 ];
  
// Store the size of the array
let n = a.length;
  
// Function Call
print(a, n);
  
// This code is contributed by code_hunt
   
</script>

1 2
1 3
2 1
2 3
3 1
3 2

En este ejemplo, es evidente que la declaración de impresión se ejecuta n ² veces, por lo tanto, si se traza el gráfico de tiempo de ejecución frente a n, se obtendrá un gráfico parabólico, f(n ² ). Ahora, las funciones lineales g(n), las funciones logarítmicas g(log n), las funciones constantes g(1) son todas menores que una función parabólica cuando el rango de entrada tiende a infinito, por lo tanto, el peor tiempo de ejecución de este programa puede ser Ω (log n), Ω(n), Ω(1), o cualquier función g(n) que sea menor que n ² cuando n tiende a infinito. Vea la siguiente representación gráfica:
 

Cuándo usar la notación Big – Ω: La notación Big – Ω es la notación menos utilizada para el análisis de algoritmos porque puede hacer una declaración correcta pero imprecisa sobre el rendimiento de un algoritmo. Supongamos que una persona tarda 100 minutos en completar una tarea, utilizando la notación Ω, se puede afirmar que la persona tarda más de 10 minutos en realizar la tarea, esta afirmación es correcta pero no precisa ya que no menciona el límite superior de la tiempo tomado. De manera similar, usando la notación Ω podemos decir que el peor tiempo de ejecución para la búsqueda binaria es Ω(1), lo cual es cierto porque sabemos que la búsqueda binaria tomaría al menos un tiempo constante para ejecutarse.

Para más detalles, consulte:
Diseño y Análisis de Algoritmos .