Prerrequisito: Análisis de Algoritmos | Análisis O grande
En el artículo anterior , se discute el análisis del algoritmo utilizando la notación asintótica Big O. En este artículo, se discuten algunos ejemplos para ilustrar la notación de complejidad de tiempo de Big O y también aprender a calcular la complejidad de tiempo de cualquier programa.
Existen diferentes notaciones asintóticas en las que se miden las complejidades temporales de los algoritmos. Aquí, la notación ”O” (Gran O) se usa para obtener las complejidades del tiempo. La complejidad del tiempo estima el tiempo para ejecutar un algoritmo . Se calcula contando las operaciones elementales. Siempre es una buena práctica conocer el motivo del tiempo de ejecución de una manera que dependa únicamente del algoritmo y su entrada. Esto se puede lograr eligiendo una operación elemental, que el algoritmo realiza repetidamente, y definiendo la complejidad temporal T(N) como el número de tales operaciones que realiza el algoritmo dada una array de longitud N.
Ejemplo 1 :
La complejidad del tiempo para el ciclo con operaciones elementales : Suponiendo que estas operaciones toman tiempo unitario para su ejecución. Esta unidad de tiempo puede ser denotada por O(1) . Si el bucle se ejecuta N veces sin ninguna comparación. A continuación se muestra la ilustración de la misma:
C++
// C++ program to illustrate time
// complexity for single for-loop
#include <bits/stdc++.h>
using namespace std;
// Driver Code
int main()
{
int a = 0, b = 0;
int N = 4, M = 4;
// This loop runs for N time
for (int i = 0; i < N; i++) {
a = a + 10;
}
// This loop runs for M time
for (int i = 0; i < M; i++) {
b = b + 40;
}
cout << a << ' ' << b;
return 0;
}
Java
// Java program to illustrate time
// complexity for single for-loop
class GFG
{
// Driver Code
public static void main(String[] args)
{
int a = 0, b = 0;
int N = 4, M = 4;
// This loop runs for N time
for (int i = 0; i < N; i++)
{
a = a + 10;
}
// This loop runs for M time
for (int i = 0; i < M; i++)
{
b = b + 40;
}
System.out.print(a + " " + b);
}
}
// This code is contributed by rutvik_56
Python3
# Python program to illustrate time # complexity for single for-loop a = 0 b = 0 N = 4 M = 4 # This loop runs for N time for i in range(N): a = a + 10 # This loop runs for M time for i in range(M): b = b + 40 print(a,b) # This code is contributed by Shubham Singh
C#
// C# program to illustrate time
// complexity for single for-loop
using System;
class GFG
{
// Driver Code
public static void Main(string[] args)
{
int a = 0, b = 0;
int N = 4, M = 4;
// This loop runs for N time
for (int i = 0; i < N; i++)
{
a = a + 10;
}
// This loop runs for M time
for (int i = 0; i < M; i++)
{
b = b + 40;
}
Console.Write(a + " " + b);
}
}
// This code is contributed by pratham76.
Javascript
<script>
// Javascript program to illustrate time
// complexity for single for-loop
// Driver Code
let a = 0;
let b = 0;
let N = 4;
let M = 4;
// This loop runs for N time
for (let i = 0; i < N; i++) {
a = a + 10;
}
// This loop runs for M time
for (let i = 0; i < M; i++) {
b = b + 40;
}
document.write(a +' ' + b);
// This code is contributed by Shubham Singh
</script>
40 160
Explicación: La complejidad del tiempo aquí será O(N + M) . El bucle uno es un bucle for único que se ejecuta N veces y el cálculo en su interior lleva O(1) tiempo . De manera similar, otro bucle toma M veces combinando los diferentes bucles al sumarlos
es O( N + M + 1) = O( N + M) .
Ejemplo 2 :
Después de familiarizarse con las operaciones elementales y el bucle único. Ahora, para encontrar la complejidad del tiempo para bucles anidados, suponga que hay dos bucles con un número diferente de iteraciones. Se puede ver que, si el ciclo externo se ejecuta una vez, el interno se ejecutará M veces , dándonos una serie como M + M + M + M + M………….N veces , esto se puede escribir como N * M. A continuación se muestra la ilustración de la misma:
C++
// C++ program to illustrate time
// complexity for nested loop
#include <bits/stdc++.h>
using namespace std;
// Driver Code
int main()
{
int a = 0, b = 0;
int N = 4, M = 5;
// Nested loops
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
a = a + j;
// Print the current
// value of a
cout << a << ' ';
}
cout << endl;
}
return 0;
}
Java
// Java program to illustrate time
// complexity for nested loop
import java.io.*;
class GFG{
// Driver Code
public static void main (String[] args)
{
int a = 0;
int b = 0;
int N = 4;
int M = 5;
// Nested loops
for(int i = 0; i < N; i++)
{
for(int j = 0; j < M; j++)
{
a = a + j;
// Print the current
// value of a
System.out.print(a + " ");
}
System.out.println();
}
}
}
// This code is contributed by Shubham Singh
Python3
# Python program to illustrate time # complexity for nested loop # Driver Code a = 0 b = 0 N = 4 M = 5 # Nested loops for i in range(N): for j in range(M): a = a + j # Print the current # value of a print(a, end = " ") print() # This code is contributed by Shubham Singh
C#
// C# program to illustrate time
// complexity for nested loop
using System;
public class GFG
{
// Driver Code
public static void Main ()
{
int a = 0;
// int b = 0;
int N = 4;
int M = 5;
// Nested loops
for(int i = 0; i < N; i++)
{
for(int j = 0; j < M; j++)
{
a = a + j;
// Print the current
// value of a
Console.Write(a + " ");
}
Console.WriteLine();
}
}
}
// This code is contributed by Shubham Singh
Javascript
<script>
// Javascript program to illustrate time
// complexity for Nested loops
// Driver Code
let a = 0;
let b = 0;
let N = 4;
let M = 5;
// Nested loops
for (let i = 0; i < N; i++) {
for (let j = 0; j < M; j++) {
a = a + j;
// Print the current
// value of a
document.write(a +' ');
}
document.write('<br>');
}
// This code is contributed by Shubham Singh
</script>
0 1 3 6 10 10 11 13 16 20 20 21 23 26 30 30 31 33 36 40
Ejemplo 3 :
Después de obtener los problemas anteriores. Tengamos dos iteradores en los que el exterior se ejecuta N/2 veces, y sabemos que la complejidad temporal de un ciclo se considera O(log N) , si el iterador se divide/multiplica por una cantidad constante K , entonces la complejidad temporal se considera como O(log K N) . A continuación se muestra la ilustración del mismo:
C++
// C++ program to illustrate time
// complexity of the form O(log2 N)
#include <bits/stdc++.h>
using namespace std;
// Driver Code
int main()
{
int N = 8, k = 0;
// First loop run N/2 times
for (int i = N / 2; i <= N; i++) {
// Inner loop run log N
// times for all i
for (int j = 2; j <= N;
j = j * 2) {
// Print the value k
cout << k << ' ';
k = k + N / 2;
}
}
return 0;
}
Java
// Program to illustrate time
// complexity of the form O(log2 N)
import java.util.*;
class GFG {
// Driver Code
public static void main (String[] args)
{
int N = 8, k = 0;
// First loop run N/2 times
for (int i = N / 2; i <= N; i++) {
// Inner loop run log N
// times for all i
for (int j = 2; j <= N;
j = j * 2) {
// Print the value k
System.out.print(k + " ");
k = k + N / 2;
}
}
}
}
// This code is contributed by Shubham Singh
Python3
# Python program to illustrate time # complexity of the form O(log2 N) # Driver Code N = 8 k = 0 # First loop run N/2 times for i in range(N//2, N+1): # Inner loop run log N # times for all i j = 2 while j <= N: j = j * 2 # Print the value k print(k, end = ' ') k = k + N // 2 # This code is contributed by Shubham Singh
C#
// Program to illustrate time
// complexity of the form O(log2 N)
using System;
using System.Linq;
public class GFG{
// Driver Code
public static void Main ()
{
int N = 8, k = 0;
// First loop run N/2 times
for (int i = N / 2; i <= N; i++) {
// Inner loop run log N
// times for all i
for (int j = 2; j <= N;
j = j * 2) {
// Print the value k
Console.Write(k + " ");
k = k + N / 2;
}
}
}
}
// This code is contributed by Shubham Singh
Javascript
<script>
// Javascript program to illustrate time
// complexity of the form O(log2 N)
// Driver Code
var N = 8, k = 0;
// First loop run N/2 times
for (var i = parseInt(N / 2); i <= N; i++) {
// Inner loop run log N
// times for all i
for (var j = 2; j <= N;j = j * 2) {
// Print the value k
document.write(k +" ");
k = k + parseInt(N / 2);
}
}
//This code is contributed By Shubham Singh
</script>
0 4 8 12 16 20 24 28 32 36 40 44 48 52 56
Ejemplo 4 :
Ahora, entendamos el ciclo while e intentemos actualizar el iterador como una expresión. A continuación se muestra la ilustración de la misma:
C++
// C++ program to illustrate time
// complexity while updating the
// iteration
#include <bits/stdc++.h>
using namespace std;
// Driver Code
int main()
{
int N = 18;
int i = N, a = 0;
// Iterate until i is greater
// than 0
while (i > 0) {
// Print the value of a
cout << a << ' ';
a = a + i;
// Update i
i = i / 2;
}
return 0;
}
Java
// Java program to illustrate time
// complexity while updating the
// iteration
import java.io.*;
class GFG {
// Driver Code
public static void main (String[] args)
{
int N = 18;
int i = N, a = 0;
// Iterate until i is greater
// than 0
while (i > 0) {
// Print the value of a
System.out.print(a + " ");
a = a + i;
// Update i
i = i / 2;
}
}
}
// This code is contributed by Shubham Singh
Python3
# Python program to illustrate time # complexity while updating the # iteration # Driver Code N = 18 i = N a = 0 # Iterate until i is greater # than 0 while (i > 0): # Print the value of a print(a, end = ' ') a = a + i # Update i i = i // 2 # This code is contributed by Shubham Singh
C#
// Java program to illustrate time
// complexity while updating the
// iteration
using System;
public class GFG{
// Driver Code
public static void Main ()
{
int N = 18;
int i = N, a = 0;
// Iterate until i is greater
// than 0
while (i > 0) {
// Print the value of a
Console.Write(a + " ");
a = a + i;
// Update i
i = i / 2;
}
}
}
// This code is contributed by Shubham Singh
Javascript
<script>
// javaScript program to illustrate time
// complexity while updating the
// iteration
// Driver Code
function main()
{
var N = 18;
var i = N, a = 0;
// Iterate until i is greater
// than 0
while (i > 0) {
// Print the value of a
document.write(a +" ");
a = a + i;
// Update i
i = parseInt(i / 2);
}
}
main();
// This code is contributed by Shubham Singh
</script>
0 18 27 31 33
Explicación: La ecuación para el código anterior se puede dar como:
=> (N/2) K = 1 (para k iteraciones)
=> N = 2 k (tomando log en ambos lados)
=> k = log(N) base 2.
Por lo tanto, la complejidad temporal será
T(N) = O(registro N)
Ejemplo 5 : otra forma de encontrar la complejidad del tiempo es convertirlos en una expresión y usar lo siguiente para obtener el resultado requerido. Dada una expresión basada en el algoritmo, la tarea es resolver y encontrar la complejidad del tiempo. Esta metodología es más fácil ya que utiliza un cálculo matemático básico para expandir una fórmula dada para obtener una solución particular. A continuación se muestran los dos ejemplos para entender el método.
Pasos:
- Encuentre la solución para (N – 1) iteración /paso.
- Del mismo modo, calcule para el siguiente paso.
- Una vez que se familiarice con el patrón, busque una solución para el paso K.
- Encuentre la solución para N veces y resuelva para la expresión obtenida.
A continuación se muestra la ilustración de la misma:
Sea la expresión:
T(N) = 3*T(N – 1).T(N) = 3*(3T(N-2))
T(N) = 3*3*(3T(N – 3))Para k veces:
T(N) = (3^k – 1)*(3T(N – k))
Para N veces:
T(N) = 3^N – 1 (3T(N – N))
T(N) = 3^N – 1 *3(T(0))
T(N) = 3^N * 1
T(N) = 3^N
El tercer y más simple método es usar el Teorema de Master o calcular complejidades de tiempo. Para encontrar la complejidad del tiempo utilizando el Teorema de Master , consulte este artículo .
Para más detalles, consulte:
Diseño y Análisis de Algoritmos .
Publicación traducida automáticamente
Artículo escrito por manavgoswami001 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA