Muchos estudiantes se confunden al comprender el concepto de complejidad del tiempo, pero en este artículo lo explicaremos con un ejemplo muy simple.
P. Imagine una clase de 100 estudiantes en la que le dio su bolígrafo a una persona. Tienes que encontrar ese bolígrafo sin saber a quién se lo regalaste.
A continuación se muestran algunas formas de encontrar el bolígrafo y cuál es el orden O.
- En 2 ): Vas y le preguntas al primero de la clase si tiene el bolígrafo. Además, le preguntas a esta persona sobre las otras 99 personas en el salón de clases si tienen ese bolígrafo y así sucesivamente,
Esto es lo que llamamos O(n2). - En): Ir y preguntar a cada estudiante individualmente es O(N).
- O(log n): Ahora divido la clase en dos grupos y luego pregunto: ¿Está en el lado izquierdo o en el lado derecho del salón de clases? Luego tomo ese grupo y lo divido en dos y vuelvo a preguntar, y así sucesivamente. Repita el proceso hasta que le quede un estudiante que tenga su bolígrafo. Esto es lo que quieres decir con O (log n).
Puede que necesite hacer:
- El En 2 ) busca si sólo un estudiante sabe en qué estudiante está escondido el bolígrafo .
- El En) si Un estudiante tenía el bolígrafo y solo ellos lo sabían. .
- El O(log n) buscar si todos los estudiantes sabían , pero sólo me lo diría si adivinara el lado correcto.
Lo anterior oh -> se llama Grande – oh que es una notación asintótica. Hay otros notaciones asintóticas como theta y Omega .
NOTA: Nos interesa la tasa de crecimiento a lo largo del tiempo con respecto a los insumos tomados durante la ejecución del programa.
¿La complejidad temporal de un algoritmo/código es la misma que el tiempo de ejecución del código?
La complejidad temporal de un algoritmo/código es no igual al tiempo real requerido para ejecutar un código en particular, pero al número de veces que se ejecuta una declaración. Podemos probar esto usando el comando de tiempo .
Por ejemplo: Escriba código en C/C++ o cualquier otro lenguaje para encontrar el máximo entre N números, donde N varía entre 10, 100, 1000 y 10000. Para sistemas operativos basados en Linux (Fedora o Ubuntu), use los siguientes comandos:
notas a pie de página de rebajas
Para compilar el programa: programa gcc.c – o programa
Para ejecutar el programa: hora ./programa
Obtendrá resultados sorprendentes, es decir:
- Para N = 10: puede obtener un tiempo de 0,5 ms,
- Para N = 10.000: puede obtener un tiempo de 0,2 ms.
- Además, obtendrá diferentes tiempos en diferentes máquinas. Incluso si no obtendrá los mismos tiempos en la misma máquina para el mismo código, la razón detrás de esto es la carga actual de la red.
Entonces, podemos decir que el El tiempo real requerido para ejecutar el código depende de la máquina. (ya sea que esté usando Pentium 1 o Pentium 5) y también considera la carga de la red si su máquina está en LAN/WAN.
¿Qué se entiende por complejidad temporal de un algoritmo?
Ahora bien, surge la pregunta: si la complejidad del tiempo no es el tiempo real necesario para ejecutar el código, entonces ¿qué es?
La respuesta es:
En lugar de medir el tiempo real requerido para ejecutar cada declaración en el código, La complejidad del tiempo considera cuántas veces se ejecuta cada declaración.
Ejemplo 1: Considere el siguiente código simple para imprimir hola mundo
C++ #include using namespace std; int main() { cout << 'Hello World'; return 0; } // This code is contributed by vikash36905.> C #include int main() { printf('Hello World'); return 0; }> Java import java.io.*; class GFG { public static void main(String[] args) { System.out.print('Hello World'); } } // This code is contributed by vikash36905.> Python3 print('Hello World') # This code is contributed by akashish__> C# using System; public class GFG{ static public void Main (){ // Code Console.WriteLine('Hello World'); } } // This code is contributed by lokesh> JavaScript console.log('Hello World') // This code is contributed by nilha72xi.> Producción
Hello World>
Complejidad del tiempo: En el código anterior, Hello World se imprime solo una vez en la pantalla.
Entonces, la complejidad del tiempo es constante: O(1) es decir, cada vez que se requiere una cantidad constante de tiempo para ejecutar el código, sin importar qué sistema operativo o qué configuración de máquina esté utilizando.
Espacio Auxiliar :O(1)
Ejemplo 2:
manejo de cadenas en c++C++
#include using namespace std; int main() { int i, n = 8; for (i = 1; i <= n; i++) { cout << 'Hello World !!!
'; } return 0; } // This code is contributed by vikash36905.> C #include void main() { int i, n = 8; for (i = 1; i <= n; i++) { printf('Hello World !!!
'); } }> Java class GFG { public static void main(String[] args) { int i, n = 8; for (i = 1; i <= n; i++) { System.out.printf('Hello World !!!
'); } } } // This code is contributed by Rajput-Ji> Python3 # Python code n = 8 for i in range(1, n + 1): print('Hello World !!!') # This code is contributed by lokesh> C# using System; public class GFG { public static void Main(String[] args) { int i, n = 8; for (i = 1; i <= n; i++) { Console.Write('Hello World !!!
'); } } } // This code contributed by Rajput-Ji> JavaScript let i, n = 8; for (i = 1; i <= n; i++) { console.log('Hello World !!!'); }> Producción
Hello World !!! Hello World !!! Hello World !!! Hello World !!! Hello World !!! Hello World !!! Hello World !!! Hello World !!!>
Complejidad del tiempo: En el código anterior ¡¡¡Hola mundo!!! solo esta impreso n veces en la pantalla, ya que el valor de n puede cambiar.
Entonces, la complejidad del tiempo es lineal: O(n) es decir, cada vez, se requiere una cantidad lineal de tiempo para ejecutar el código.
Espacio Auxiliar: O(1)
Ejemplo 3:
C++ #include using namespace std; int main() { int i, n = 8; for (i = 1; i <= n; i=i*2) { cout << 'Hello World !!!
'; } return 0; } // This code is contributed by Suruchi Kumari> C #include void main() { int i, n = 8; for (i = 1; i <= n; i=i*2) { printf('Hello World !!!
'); } } // This code is contributed by Suruchi Kumari> Java class GFG { public static void main(String[] args) { int i, n = 8; for (i = 1; i <= n; i=i*2) { System.out.println('Hello World !!!'); } } } // This code is contributed by Suruchi Kumari> Python3 n = 8 # for (i = 1; i <= n; i=i*2) { for i in range(1, n+1, 2): print('Hello World !!!') # This code is contributed by akashish__> C# using System; public class GFG{ static public void Main (){ // Code int i, n = 8; for (i = 1; i <= n; i=i*2) { Console.Write('Hello World !!!
'); } } } // This code is contributed by lokeshmvs21.> JavaScript for (i = 1; i <= 8; i=i*2) { console.log('Hello World !!!'); } // This code is contributed by nilha7xi.> Producción
Hello World !!! Hello World !!! Hello World !!! Hello World !!!>
Complejidad del tiempo: O(registro2(norte))
Espacio Auxiliar: O(1)
Ejemplo 4:
C++ #include #include using namespace std; int main() { int i, n = 8; for (i = 2; i <= n; i=pow(i,2)) { cout << 'Hello World !!!
'; } return 0; } // This code is contributed by Suruchi Kumari> C #include #include void main() { int i, n = 8; for (i = 2; i <= n; i=pow(i,2)) { printf('Hello World !!!
'); } } // This code is contributed by Suruchi Kumari> Java import java.lang.Math; class GFG { public static void main(String args[]){ int i, n = 8; for (i = 2; i <= n; i=(int)Math.pow(i,2)) { System.out.println('Hello World !!!'); } } }> Python3 n = 8 i = 2 for j in range(2,n+1): if(i>= n): break print('Hello World !!!') i *= i # Este código es una contribución de akashish__> C# using System; using System.Collections.Generic; public class GFG { static public void Main() { int i, n = 8; for (i = 2; i <= n; i = (int)Math.Pow(i, 2)) { Console.WriteLine('Hello World !!!'); } } } // This code is contributed by akashish__> JavaScript for (let i = 2; i <= 8; i=Math.pow(i,2)) { console.log('Hello World !!!'); } // This code is contributed by nilha7xi.> Producción
Hello World !!! Hello World !!!>
Complejidad del tiempo: O(registro(registro n))
Espacio Auxiliar: O(1)
¿Cómo encontrar la complejidad temporal de un algoritmo?
Ahora veamos algunos otros ejemplos y el proceso para encontrar la complejidad temporal de un algoritmo:
Ejemplo: Consideremos un modelo de máquina que tiene las siguientes especificaciones:
- Procesador único
- 32 bits
- Ejecución secuencial
- 1 unidad de tiempo para operaciones aritméticas y lógicas.
- 1 unidad de tiempo para declaraciones de cesión y devolución
P1. Encuentre la suma de 2 números en la máquina anterior:
Para cualquier máquina, el pseudocódigo para sumar dos números será algo como esto:
C++ // Pseudocode : Sum(a, b) { return a + b } #include using namespace std; int sum(int a,int b) { return a+b; } int main() { int a = 5, b = 6; cout< C Pseudocode : Sum(a, b) { return a + b }> Java // Pseudocode : Sum(a, b) { return a + b } import java.io.*; class GFG { public static int sum(int a, int b) { return a + b; } public static void main(String[] args) { int a = 5, b = 6; System.out.println(sum(a, b)); } } // This code is contributed by akashish__> Python3 # Pseudocode : Sum(a, b) { return a + b } a = 5 b = 6 def sum(a,b): return a+b # function call print(sum(a,b))> C# // Pseudocode : Sum(a, b) { return a + b } using System; public class GFG { public static int sum(int a, int b) { return a + b; } static public void Main() { int a = 5, b = 6; Console.WriteLine(sum(a, b)); } } // This code is contributed by akashish__> JavaScript // Pseudocode : Sum(a, b) { return a + b } function sum(a, b) { return a + b; } let a = 5, b = 6; console.log(sum(a, b)); // This code is contributed by akashish__> Producción
11>
Complejidad del tiempo:
- El código anterior tomará 2 unidades de tiempo (constante):
- uno para operaciones aritméticas y
- uno para devolución. (según las convenciones anteriores).
- Por lo tanto, el costo total para realizar la operación de suma ( ) = 1 + 1 = 2
- Complejidad del tiempo = O(2) = O(1) , ya que 2 es constante
Espacio Auxiliar: O(1)
P2. Encuentra la suma de todos los elementos de una lista/matriz
El pseudocódigo para hacerlo se puede dar como:
C++ #include using namespace std; int list_Sum(int A[], int n) // A->matriz y // n->número de elementos en la matriz { int suma = 0; para (int i = 0; i<= n - 1; i++) { sum = sum + A[i]; } return sum; } int main() { int A[] = { 5, 6, 1, 2 }; int n = sizeof(A) / sizeof(A[0]); cout << list_Sum(A, n); return 0; } // This code is contributed by akashish__> C Pseudocode : list_Sum(A, n) // A->matriz y // n->número de elementos en la matriz { suma = 0 para i = 0 a n-1 suma = suma + A[i] devolver suma }> Java // Java code for the above approach import java.io.*; class GFG { static int list_Sum(int[] A, int n) // A->matriz y // n->número de elementos en la matriz { int suma = 0; para (int i = 0; i<= n - 1; i++) { sum = sum + A[i]; } return sum; } public static void main(String[] args) { int[] A = { 5, 6, 1, 2 }; int n = A.length; System.out.println(list_Sum(A, n)); } } // This code is contributed by lokeshmvs21.> Python3 # A function to calculate the sum of the elements in an array def list_sum(A, n): sum = 0 for i in range(n): sum += A[i] return sum # A sample array A = [5, 6, 1, 2] # Finding the number of elements in the array n = len(A) # Call the function and print the result print(list_sum(A, n))>
C# using System; public class GFG { public static int list_Sum(int[] A, int n) // A->matriz y // n->número de elementos en la matriz { int suma = 0; para (int i = 0; i<= n - 1; i++) { sum = sum + A[i]; } return sum; } static public void Main() { int[] A = { 5, 6, 1, 2 }; int n = A.Length; Console.WriteLine(list_Sum(A, n)); } } // This code is contributed by akashish__> JavaScript function list_Sum(A, n) // A->matriz y // n->número de elementos en la matriz { let sum = 0; para (sea i = 0; i<= n - 1; i++) { sum = sum + A[i]; } return sum; } let A = [ 5, 6, 1, 2 ]; let n = A.length; console.log(list_Sum(A, n)); // This code is contributed by akashish__> Producción
14>
Para comprender la complejidad temporal del código anterior, veamos cuánto tiempo llevará cada declaración:
int list_Sum(int A[], int n) { int sum = 0; // cost=1 no of times=1 for(int i=0; i C Pseudocode : list_Sum(A, n) { total =0 // cost=1 no of times=1 for i=0 to n-1 // cost=2 no of times=n+1 (+1 for the end false condition) sum = sum + A[i] // cost=2 no of times=n return sum // cost=1 no of times=1 }> Java public class ListSum { // Function to calculate the sum of elements in an array static int listSum(int[] A, int n) { int sum = 0; // Cost = 1, executed 1 time for (int i = 0; i < n; i++) { // Cost = 2, executed n+1 times (+1 for // the end false condition) sum = sum + A[i]; // Cost = 2, executed n times } return sum; // Cost = 1, executed 1 time } // Main method for testing public static void main(String[] args) { int[] array = {1, 2, 3, 4, 5}; int length = array.length; int result = listSum(array, length); System.out.println('Sum: ' + result); } }> Python3 def list_sum(A): sum = 0 for i in range(len(A)): sum = sum + A[i] return sum>
C# using System; class Program { // Function to calculate the sum of elements in a list static int ListSum(int[] A) { int sum = 0; // Initialize sum to 0 // Loop to iterate through the array elements for (int i = 0; i < A.Length; i++) { sum = sum + A[i]; // Accumulate the sum } return sum; // Return the calculated sum } // Driver code static void Main() { // Example usage int[] array = { 1, 2, 3, 4, 5 }; int result = ListSum(array); Console.WriteLine(result); } }> JavaScript function listSum(A) { let sum = 0; // Initialize sum to 0 // Loop to iterate through the array elements for (let i = 0; i < A.length; i++) { sum = sum + A[i]; // Accumulate the sum } return sum; // Return the calculated sum } // Example usage let array = [1, 2, 3, 4, 5]; let result = listSum(array); console.log(result);> Por lo tanto, el costo total para realizar la operación de suma.
Suma=1 + 2 * (n+1) + 2 * n + 1 = 4n + 4 = C1 * n + C2 = O(n)
látex derivado parcial
Por lo tanto, la complejidad temporal del código anterior es En)
P3. Encuentra la suma de todos los elementos de una matriz.
Para éste, la complejidad es una ecuación polinómica (ecuación cuadrática para una matriz cuadrada)
- Matriz de tamaño n*n => Tsum = a.n 2 + b.n + c
- Dado que Tsum está en orden de n2, por lo tanto Complejidad del tiempo = O(n 2 )
#include using namespace std; int main() { int n = 3; int m = 3; int arr[][3] = { { 3, 2, 7 }, { 2, 6, 8 }, { 5, 1, 9 } }; int sum = 0; // Iterating over all 1-D arrays in 2-D array for (int i = 0; i < n; i++) { // Printing all elements in ith 1-D array for (int j = 0; j < m; j++) { // Printing jth element of ith row sum += arr[i][j]; } } cout << sum << endl; return 0; } // contributed by akashish__> Java /*package whatever //do not write package name here */ import java.io.*; class GFG { public static void main(String[] args) { int n = 3; int m = 3; int arr[][] = { { 3, 2, 7 }, { 2, 6, 8 }, { 5, 1, 9 } }; int sum = 0; // Iterating over all 1-D arrays in 2-D array for (int i = 0; i < n; i++) { // Printing all elements in ith 1-D array for (int j = 0; j < m; j++) { // Printing jth element of ith row sum += arr[i][j]; } } System.out.println(sum); } } // akashish__> Python3 n = 3 m = 3 arr = [[3, 2, 7], [2, 6, 8], [5, 1, 9]] sum = 0 # Iterating over all 1-D arrays in 2-D array for i in range(n): # Printing all elements in ith 1-D array for j in range(m): # Printing jth element of ith row sum += arr[i][j] print(sum) # This code id contributed by shivhack999>
C# using System; class MainClass { static void Main(string[] args) { int n = 3; int m = 3; int[, ] arr = { { 3, 2, 7 }, { 2, 6, 8 }, { 5, 1, 9 } }; int sum = 0; // Iterating over all 1-D arrays in 2-D array for (int i = 0; i < n; i++) { // Printing all elements in ith 1-D array for (int j = 0; j < m; j++) { // Printing jth element of ith row sum += arr[i, j]; } } Console.WriteLine(sum); } }> JavaScript let n = 3; let m = 3; let arr = [[3, 2, 7], [2, 6, 8], [5, 1, 9]]; let sum = 0; // Iterating over all 1-D arrays in 2-D array for (let i = 0; i < n; i++) { // Printing all elements in ith 1-D array for (let j = 0; j < m; j++) { // Printing jth element of ith row sum += arr[i][j]; } } console.log(sum);> Producción
43>
Complejidad del tiempo: En M)
El programa recorre en iteración todos los elementos de la matriz 2D utilizando dos bucles anidados. El bucle exterior se repite n veces y el bucle interior se repite m veces para cada iteración del bucle exterior. Por tanto, la complejidad temporal del programa es O (n*m).
Espacio Auxiliar: En M)
El programa utiliza una cantidad fija de espacio auxiliar para almacenar la matriz 2D y algunas variables enteras. El espacio requerido para la matriz 2D es nm enteros. El programa también utiliza una única variable entera para almacenar la suma de los elementos. Por lo tanto, la complejidad espacial auxiliar del programa es O (nm + 1), que se simplifica a O (n*m).
En conclusión, la complejidad temporal del programa es O (nm) y la complejidad del espacio auxiliar también es O (nm).
Entonces, de los ejemplos anteriores, podemos concluir que el tiempo de ejecución aumenta con el tipo de operaciones que realizamos utilizando las entradas.
¿Cómo comparar algoritmos?
Para comparar algoritmos, definamos algunas medidas objetivas:
- Tiempos de ejecución: No es una buena medida ya que los tiempos de ejecución son específicos de una computadora en particular.
- El número de declaraciones ejecutadas: No es una buena medida, ya que el número de declaraciones varía según el lenguaje de programación y el estilo del programador individual.
- Solución ideal: Supongamos que expresamos el tiempo de ejecución de un algoritmo dado como una función del tamaño de entrada n (es decir, f (n)) y comparamos estas diferentes funciones correspondientes a los tiempos de ejecución. Este tipo de comparación es independiente del tiempo de la máquina, el estilo de programación, etc.
Por lo tanto, se puede utilizar una solución ideal para comparar algoritmos.
Artículos relacionados:
- Complejidad temporal y complejidad espacial
- Análisis de Algoritmos | Conjunto 1 (Análisis asintótico)
- Análisis de Algoritmos | Conjunto 2 (peor, promedio y mejores casos)
- Análisis de Algoritmos | Conjunto 3 (notaciones asintóticas)
- Análisis de Algoritmos | Conjunto 4 (Análisis de bucles)
- Análisis de algoritmo | Conjunto 5 (Introducción al Análisis Amortizado)
- Problemas diversos de la complejidad del tiempo
- Preguntas de práctica sobre análisis de complejidad del tiempo
- Conociendo la complejidad de la programación competitiva