Teoría de los límites inferior y superior

La teoría de los límites inferior y superior proporciona una forma de encontrar el algoritmo de menor complejidad para resolver un problema. Antes de comprender la teoría, primero, echemos un breve vistazo a lo que son los límites inferior y superior. 

• Límite Inferior – 
  Sea L(n) el tiempo de ejecución de un algoritmo A(por ejemplo), entonces g(n) es el Límite Inferior de A si existen dos constantes C y N tales que L(n) >= C*g (n) para n > N. El límite inferior de un algoritmo se muestra mediante la notación asintótica llamada Big Omega (o simplemente Omega). 
   
• Límite superior: 
  sea U(n) el tiempo de ejecución de un algoritmo A(digamos), entonces g(n) es el límite superior de A si existen dos constantes C y N tales que U(n) <= C*g (n) para n > N. El límite superior de un algoritmo se muestra mediante la notación asintótica llamada Big Oh(O) (o simplemente Oh).

1. Teoría del límite inferior: 
De acuerdo con la teoría del límite inferior, para un límite inferior L(n) de un algoritmo, no es posible tener ningún otro algoritmo (para un problema común) cuya complejidad temporal sea menor que L(n) para entrada aleatoria. Además, cada algoritmo debe tomar al menos L(n) tiempo en el peor de los casos. Nótese que L(n) aquí es el mínimo de todos los algoritmos posibles, de máxima complejidad. 
El límite inferior es muy importante para cualquier algoritmo. Una vez que lo calculamos, podemos compararlo con la complejidad real del algoritmo y, si su orden es el mismo, podemos declarar nuestro algoritmo como óptimo. Entonces, en esta sección, discutiremos técnicas para encontrar el límite inferior de un algoritmo. 

Tenga en cuenta que nuestro motivo principal es obtener un algoritmo óptimo, que es el que tiene su límite superior igual que su límite inferior (U (n) = L (n)). Merge Sort es un ejemplo común de un algoritmo óptimo.

Límite inferior trivial: 
es el método más fácil para encontrar el límite inferior. Los límites inferiores que se pueden observar fácilmente en función de la cantidad de entradas tomadas y la cantidad de salidas producidas se denominan Límite inferior trivial. 

Ejemplo: Multiplicación de array nxn, donde, 

Input: For 2 matrices we will have 2n2 inputs
Output: 1 matrix of order n x n, i.e.,  n2 outputs 

En el ejemplo anterior, es fácilmente predecible que el límite inferior es O(n ² ). 

Modelo computacional: 
el método es para todos aquellos algoritmos que se basan en la comparación. Por ejemplo, al ordenar, tenemos que comparar los elementos de la lista entre ellos y luego ordenarlos en consecuencia. Similar es el caso de la búsqueda y, por lo tanto, podemos implementar lo mismo en este caso. Ahora veremos algunos ejemplos para entender su uso.

Búsqueda ordenada: 
es un tipo de búsqueda en la que la lista ya está ordenada.
Ejemplo-1: Búsqueda lineal  
Explicación: 
en la búsqueda lineal, comparamos la clave con el primer elemento, si no coincide, la comparamos con el segundo elemento, y así sucesivamente hasta que comprobamos el elemento n. De lo contrario, terminaremos con un fracaso. 

Ejemplo-2: Búsqueda binaria  
Explicación: 
en la búsqueda binaria, verificamos el elemento central con la clave, si es mayor, buscamos la primera mitad; de lo contrario, verificamos la segunda mitad y repetimos el mismo proceso. 
El siguiente diagrama es una ilustración de la búsqueda binaria en una array que consta de 4 elementos 
 

Cálculo del límite inferior: el número máximo de comparaciones es n. Sea k niveles en el árbol. 

1. El número de Nodes será 2 ^k -1
2. El límite superior de no de Nodes en cualquier búsqueda basada en comparación de un elemento en la lista de tamaño n será n ya que hay un máximo de n comparaciones en el peor de los casos 2 ^k -1
3. Cada nivel tomará 1 comparación por lo tanto no. de comparaciones k≥|log ₂ n|

Por lo tanto, el límite inferior de cualquier búsqueda basada en la comparación de una lista de n elementos no puede ser inferior a log(n). Por lo tanto, podemos decir que la búsqueda binaria es óptima ya que su complejidad es Θ (log n).

Clasificación: 
el siguiente diagrama es un ejemplo de un árbol formado en combinaciones de clasificación con 3 elementos.

Ejemplo: para n elementos, encontrar el límite inferior utilizando el modelo de cálculo. 

Explicación: 
para n elementos, ¡tenemos un total de n! combinaciones (Nodes hoja). (Consulte el diagrama, ¡las combinaciones totales son 3! o 6) Además, está claro que el árbol formado es un árbol binario. Cada nivel en el diagrama indica una comparación. Sea k niveles => 2 ^k es el número total de Nodes hoja en un árbol binario completo, por lo que en este caso tenemos n!≤2 ^k .

Como k en el ejemplo anterior es el número de comparaciones, por lo tanto, según el límite inferior del modelo computacional = k.  

Now we can say that,
n!≤2T(n)
Thus, 
T(n)>|log n!| 
=> n!<=nn
Thus,
log n!<=log nn
Taking ceiling function on both sides, we get
|-log nn-|>=|-log n!-|
Thus complexity becomes Θ(lognn) or Θ(nlogn) 

Usando la teoría del enlace inferior para resolver el problema algebraico:

• Programa de línea recta: 
  el tipo de programa creado sin bucles ni estructuras de control se denomina programa de línea recta. Por ejemplo,

//summing to nos
Sum(a, b)
{
    //no loops and no control structures
    c:= a+b;
    return c;
}

• Problema algebraico: 
  los problemas relacionados con el álgebra, como resolver ecuaciones, desigualdades, etc., se incluyen en los problemas algebraicos. Por ejemplo, resolver la ecuación ax ² +bx+c con programación simple.

Algo_Sol(a, b, c, x)
{
    //1 assignment
    v:=a*x;
 
    //1 assignment
    v:=v+b;
 
    //1 assignment
    v:=v*x;
 
    //1 assignment
    ans:=v+c;
    return ans;
}   

La complejidad para resolver aquí es 4 (excluyendo la devolución). 
El ejemplo anterior nos muestra una forma sencilla de resolver una ecuación para un polinomio de 2 grados, es decir, 4, por lo que para el polinomio de grado n ^tendremos una complejidad de O(n ² ). 

Demostremos a través de un algoritmo. 

Ejemplo: x+a ₀ es un polinomio de grado n.

pow(x, n)
  {
    p := 1;
   
    //loop from 1 to n
    for i:=1 to n
        p := p*x;
 
    return p;
  }
 
polynomial(A, x, n)
  {
     int p, v:=0;
     for i := 0 to n
   
         //loop within a loop from 0 to n
         v := v + A[i]*pow(x, i);
     return v;
  }

Bucle dentro de un bucle => complejidad = O(n ² );
Ahora, para encontrar un algoritmo óptimo, necesitamos encontrar el límite inferior aquí (según la teoría del límite inferior). Según la teoría del límite inferior, el algoritmo óptimo para resolver el problema anterior es el que tiene una complejidad O (n). Demostremos este teorema usando cotas inferiores.

Teorema: Demostrar que el algoritmo óptimo para resolver un polinomio de grado es O(n) 
Prueba: La mejor solución para reducir el algoritmo es hacer que este problema sea menos complejo dividiendo el polinomio en varios problemas de línea recta.

=> anxn+an-1xn-1+an-2xn-2+...+a1x+a0 
can be written as 
((..(anx+an-1)x+..+a2)x+a1)x+a0
Now, the algorithm will be as,
v=0
v=v+an
v=v*x
v=v+an-1
v=v*x
...
v=v+a1
v=v*x
v=v+a0 

polynomial(A, x, n)
     {
      int p, v=0;
 
      // loop executed n times
      for i = n to 0
             v = (v + A[i])*x;
 
         return v;
      }

La complejidad de este código es O(n). Esta forma de resolver tales ecuaciones se llama método de Horner. Aquí es donde funciona la teoría del límite inferior y da la complejidad del algoritmo óptimo como O(n). 
2. Teoría del límite superior: 
De acuerdo con la teoría del límite superior, para un límite superior U(n) de un algoritmo, siempre podemos resolver el problema como máximo en un tiempo U(n). El tiempo que tarda un algoritmo conocido en resolver un problema con la entrada del caso peor nos da el límite superior.