Complejidad del tiempo y complejidad del espacio

Generalmente, siempre hay más de una forma de resolver un problema en informática con diferentes algoritmos. Por lo tanto, es muy necesario utilizar un método para comparar las soluciones con el fin de juzgar cuál es la más óptima. El método debe ser:

• Independiente de la máquina y su configuración, en la que se ejecuta el algoritmo.
• Muestra una correlación directa con el número de entradas.
• Puede distinguir dos algoritmos claramente sin ambigüedad.

Se utilizan dos métodos de este tipo, la complejidad del tiempo y la complejidad del espacio, que se analizan a continuación:

Complejidad de tiempo: La complejidad de tiempo de un algoritmo cuantifica la cantidad de tiempo que tarda un algoritmo en ejecutarse en función de la longitud de la entrada. Tenga en cuenta que el tiempo de ejecución es una función de la longitud de la entrada y no del tiempo de ejecución real de la máquina en la que se ejecuta el algoritmo.

Para calcular la complejidad del tiempo en un algoritmo, se supone que se toma un tiempo constante c para ejecutar una operación, y luego se calculan las operaciones totales para una longitud de entrada en N. Considere un ejemplo para comprender el proceso de cálculo: suponga que un problema es encontrar si existe un par (X, Y) en una array, A de N elementos cuya suma es Z. La idea más simple es considerar cada par y comprobar si cumple o no la condición dada.

El pseudocódigo es el siguiente:

int a[n];
for(int i = 0;i < n;i++)
  cin >> a[i]
  

for(int i = 0;i < n;i++)
  for(int j = 0;j < n;j++)
    if(i!=j && a[i]+a[j] == z)
       return true

return false

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 find a pair in the given
// array whose sum is equal to z
bool findPair(int a[], int n, int z)
{
    // Iterate through all the pairs
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
 
            // Check if the sum of the pair
            // (a[i], a[j]) is equal to z
            if (i != j && a[i] + a[j] == z)
                return true;
 
    return false;
}
 
// Driver Code
int main()
{
    // Given Input
    int a[] = { 1, -2, 1, 0, 5 };
    int z = 0;
    int n = sizeof(a) / sizeof(a[0]);
 
    // Function Call
    if (findPair(a, n, z))
        cout << "True";
    else
        cout << "False";
    return 0;
}

// Java program for the above approach
import java.lang.*;
import java.util.*;
 
class GFG{
 
// Function to find a pair in the given
// array whose sum is equal to z
static boolean findPair(int a[], int n, int z)
{
     
    // Iterate through all the pairs
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
         
            // Check if the sum of the pair
            // (a[i], a[j]) is equal to z
            if (i != j && a[i] + a[j] == z)
                return true;
 
    return false;
}
 
// Driver code
public static void main(String[] args)
{
     
    // Given Input
    int a[] = { 1, -2, 1, 0, 5 };
    int z = 0;
    int n = a.length;
     
    // Function Call
    if (findPair(a, n, z))
        System.out.println("True");
    else
        System.out.println("False");
}
}
 
// This code is contributed by avijitmondal1998

# Python3 program for the above approach
 
# Function to find a pair in the given
# array whose sum is equal to z
def findPair(a, n, z) :
     
    # Iterate through all the pairs
    for i in range(n) :
        for j in range(n) :
 
            # Check if the sum of the pair
            # (a[i], a[j]) is equal to z
            if (i != j and a[i] + a[j] == z) :
                return True
 
    return False
 
# Driver Code
 
# Given Input
a = [ 1, -2, 1, 0, 5 ]
z = 0
n = len(a)
 
# Function Call
if (findPair(a, n, z)) :
    print("True")
else :
    print("False")
     
    # This code is contributed by splevel62.

// C# program for above approach
using System;
 
class GFG{
 
// Function to find a pair in the given
// array whose sum is equal to z
static bool findPair(int[] a, int n, int z)
{
     
    // Iterate through all the pairs
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
         
            // Check if the sum of the pair
            // (a[i], a[j]) is equal to z
            if (i != j && a[i] + a[j] == z)
                return true;
 
    return false;
}
 
// Driver Code
static void Main()
{
     // Given Input
    int[] a = { 1, -2, 1, 0, 5 };
    int z = 0;
    int n = a.Length;
     
    // Function Call
    if (findPair(a, n, z))
        Console.WriteLine("True");
    else
        Console.WriteLine("False");
}
}
 
// This code is contributed by sanjoy_62.

<script>
 
// JavaScript program for the above approach
 
// Function to find a pair in the given
// array whose sum is equal to z
function findPair(a, n, z)
{
     
    // Iterate through all the pairs
    for(let i = 0; i < n; i++)
        for(let j = 0; j < n; j++)
         
            // Check if the sum of the pair
            // (a[i], a[j]) is equal to z
            if (i != j && a[i] + a[j] == z)
                return true;
 
    return false;
}
 
// Driver Code
 
// Given Input
let a = [ 1, -2, 1, 0, 5 ];
let z = 0;
let n = a.length;
 
// Function Call
if (findPair(a, n, z))
    document.write("True");
else
    document.write("False");
     
// This code is contributed by code_hunt
 
</script>

False

Suponiendo que cada una de las operaciones en la computadora toma aproximadamente un tiempo constante, sea c . La cantidad de líneas de código ejecutadas en realidad depende del valor de Z . Durante los análisis del algoritmo, se considera principalmente el peor de los casos, es decir, cuando no hay un par de elementos con una suma igual a Z. En el peor de los casos, 

• Se requieren N*c operaciones para la entrada.
• El bucle exterior i loop se ejecuta N veces.
• Para cada i , el bucle interior j loop se ejecuta N veces.

Entonces, el tiempo total de ejecución es N*c + N*N*c + c . Ahora ignore los términos de orden inferior ya que los términos de orden inferior son relativamente insignificantes para una entrada grande, por lo tanto, solo se toma el término de orden superior (sin constante), que es N*N en este caso. Se usan diferentes notaciones para describir el comportamiento límite de una función, pero dado que se toma el peor de los casos, se usará la notación O grande para representar la complejidad del tiempo.

Por lo tanto, la complejidad temporal es O(N ² ) para el algoritmo anterior. Tenga en cuenta que la complejidad del tiempo se basa únicamente en la cantidad de elementos en la array A , es decir, la longitud de entrada, por lo que si la longitud de la array aumenta, el tiempo de ejecución también aumentará.

El orden de crecimiento es cómo el tiempo de ejecución depende de la longitud de la entrada. En el ejemplo anterior, es claramente evidente que el tiempo de ejecución depende cuadráticamente de la longitud de la array. El orden de crecimiento ayudará a calcular el tiempo de ejecución con facilidad.

Otro ejemplo: calculemos la complejidad temporal del siguiente algoritmo:

count = 0
for (int i = N; i > 0; i /= 2)
  for (int j = 0; j < i; j++)
    count++;

int count = 0 ;
for (int i = N; i > 0; i /= 2)
    for (int j = 0; j < i; j++)
        count++;
 
//This code is contributed by Shubham Singh

count = 0
i = N
while(i > 0):
  for j in range(i):
    count+=1
  i /= 2
   
  # This code is contributed by subhamsingh10

int count = 0 ;
for (int i = N; i > 0; i /= 2)
    for (int j = 0; j < i; j++)
        count++;
 
// This code is contributed by Shubham Singh

let count = 0
for(let i = N; i > 0; i /= 2)
    for(let j = 0; j < i; j++)
        count += 1;
  
// This code is contributed by Shubham Singh

Este es un caso complicado. A primera vista, parece que la complejidad es O(N * log N) . N para el bucle j’s y log(N) para el bucle i’s . Pero está mal. Veamos por qué.

Piense en cuántas veces se ejecutará count++ . 

• Cuando i = N , se ejecutará N veces.
• Cuando i = N/2 , se ejecutará N/2 veces.
• Cuando i = N/4 , se ejecutará N/4 veces.
• Y así.

El número total de veces que se ejecutará count++ es N + N/2 + N/4+…+1= 2 * N . Entonces la complejidad del tiempo será O(N) .

Algunas complejidades de tiempo generales se enumeran a continuación con el rango de entrada para el que se aceptan en la programación competitiva: 

Complejidad espacial: la complejidad espacial de un algoritmo cuantifica la cantidad de espacio que ocupa un algoritmo para ejecutarse en función de la longitud de la entrada. Considere un ejemplo: suponga un problema para encontrar la frecuencia de los elementos de la array .

El pseudocódigo es el siguiente: 

int freq[n];
int a[n];

for(int i = 0; i<n; i++)
{
   cin>>a[i];
   freq[a[i]]++;
}  

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 count frequencies of array items
void countFreq(int arr[], int n)
{
    unordered_map<int, int> freq;
 
    // Traverse through array elements and
    // count frequencies
    for (int i = 0; i < n; i++)
        freq[arr[i]]++;
 
    // Traverse through map and print frequencies
    for (auto x : freq)
        cout << x.first << " " << x.second << endl;
}
 
// Driver Code
int main()
{
    // Given array
    int arr[] = { 10, 20, 20, 10, 10, 20, 5, 20 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    // Function Call
    countFreq(arr, n);
    return 0;
}

// Java program for the above approach
import java.util.*;
class GFG{
 
  // Function to count frequencies of array items
  static void countFreq(int arr[], int n)
  {
    HashMap<Integer,Integer> freq = new HashMap<>();
 
    // Traverse through array elements and
    // count frequencies
    for (int i = 0; i < n; i++) {
      if(freq.containsKey(arr[i])){
        freq.put(arr[i], freq.get(arr[i])+1);
      }
      else{
        freq.put(arr[i], 1);
      }
    }
 
    // Traverse through map and print frequencies
    for (Map.Entry<Integer,Integer> x : freq.entrySet())
      System.out.print(x.getKey()+ " " +  x.getValue() +"\n");
  }
 
  // Driver Code
  public static void main(String[] args)
  {
    // Given array
    int arr[] = { 10, 20, 20, 10, 10, 20, 5, 20 };
    int n = arr.length;
 
    // Function Call
    countFreq(arr, n);
  }
}
 
// This code is contributed by gauravrajput1

# Python program for the above approach
 
# Function to count frequencies of array items
def countFreq(arr, n):
    freq = dict()
     
    # Traverse through array elements and
    # count frequencies
    for i in arr:
        if i not in freq:
            freq[i] = 0
        freq[i]+=1
         
    # Traverse through map and print frequencies
    for x in freq:
        print(x, freq[x])
 
# Driver Code
 
# Given array
arr =  [10, 20, 20, 10, 10, 20, 5, 20 ]
n = len(arr)
 
# Function Call
countFreq(arr, n)
 
# This code is contributed by Shubham Singh

// C# program for the above approach
 
using System;
using System.Collections.Generic;
 
public class GFG {
 
    // Function to count frequencies of array items
    static void countFreq(int[] arr, int n)
    {
        Dictionary<int, int> freq
            = new Dictionary<int, int>();
 
        // Traverse through array elements and count
        // frequencies
        for (int i = 0; i < n; i++) {
            if (freq.ContainsKey(arr[i])) {
                freq[arr[i]] += 1;
            }
            else {
                freq.Add(arr[i], 1);
            }
        }
 
        // Traverse through dictionary and print frequencies
        foreach(KeyValuePair<int, int> x in freq)
        {
            Console.WriteLine(x.Key + " " + x.Value);
        }
    }
 
    static public void Main()
    {
 
        // Given array
        int[] arr = { 10, 20, 20, 10, 10, 20, 5, 20 };
        int n = arr.Length;
 
        // Function Call
        countFreq(arr, n);
    }
}
 
// This code is contributed by lokeshmvs21

<script>
// Javascript program for the above approach
 
// Function to count frequencies of array items
function countFreq(arr, n) {
    let freq = new Map();
    arr.sort((a, b) => a - b)
 
    // Traverse through array elements and
    // count frequencies
    for (let i = 0; i < n; i++) {
        if (freq.has(arr[i])) {
            freq.set(arr[i], freq.get(arr[i]) + 1)
        } else {
            freq.set(arr[i], 1)
        }
    }
 
 
    // Traverse through map and print frequencies
    for (let x of freq)
        document.write(x[0] + " " + x[1] + "<br>");
}
 
// Driver Code
 
// Given array
let arr = [10, 20, 20, 10, 10, 20, 5, 20];
let n = arr.length;
 
// Function Call
countFreq(arr, n);
 
// This code is contributed by Saurabh Jaiswal
</script>

5 1
10 3
20 4

Aquí se utilizan dos arrays de longitud N y la variable i en el algoritmo, por lo que el espacio total utilizado es N * c + N * c + 1 * c = 2N * c + c , donde c es una unidad de espacio tomada. Para muchas entradas, la constante c es insignificante y se puede decir que la complejidad del espacio es O(N) .

También existe el espacio auxiliar, que es diferente de la complejidad del espacio. La principal diferencia es donde la complejidad del espacio cuantifica el espacio total utilizado por el algoritmo, el espacio auxiliar cuantifica el espacio adicional que se utiliza en el algoritmo además de la entrada dada. En el ejemplo anterior, el espacio auxiliar es el espacio utilizado por la array freq[] porque no forma parte de la entrada dada. Entonces, el espacio auxiliar total es N * c + c, que es solo O (N) .