Problemas misceláneos de la complejidad del tiempo

Requisito previo: notaciones asintóticas

Complejidad del tiempo: La
complejidad del tiempo es el tiempo que necesita un algoritmo expresado como una función del tamaño de un problema. También se puede definir como la cantidad de tiempo de computadora que necesita para ejecutar un programa hasta su finalización. Cuando resolvemos un problema de complejidad de tiempo, esta definición es la que más ayuda: 
«Es la cantidad de operaciones que realiza un algoritmo para completar su tarea con respecto al tamaño de entrada».

A continuación se presentan algunos problemas misceláneos de complejidad temporal que siempre se preguntan con frecuencia en diferentes tipos de cuestionarios.

1. ¿Cuál es la complejidad temporal del siguiente código?

void function(int n)
{
    int i = 1, s = 1;
    while (s < n) {
        s = s + i;
        i++;
    }
}
 
// This code is contributed by Shubham Singh

void function(int n)
{
    int i = 1, s = 1;
    while (s < n) {
        s = s + i;
        i++;
    }
}

public static void function(int n)
{
    int i = 1, s = 1;
    while (s < n) {
        s = s + i;
        i++;
    }
}
 
// This code is contributed by Shubham Singh

def function(n):
    i = 1
    s = 1
    while (s < n):
        s = s + i
        i+=1
     
# This code is contributed by Shubham Singh

public static void function(int n)
{
    int i = 1, s = 1;
    while (s < n) {
        s = s + i;
        i++;
    }
}
 
// This code is contributed by Shubham Singh

<script>
function functionn(int n)
{
    var i = 1;
    var s = 1;
    while (s < n) {
        s = s + i;
        i++;
    }
}
 
// This code is contributed by Shubham Singh
</script>

Solución –  
Complejidad temporal = O(√n).

Explicación – 
Podemos definir los términos ‘S’ según la relación S _i = S _i-1 + i. Sea k el número total de iteraciones realizadas por el programa 

 Cuando S >= n , el ciclo se detendrá en las k ^-ésimas iteraciones,
⇒ S>=n ⇒ S=n
⇒ 2 + 2 + 3 + 4 + ……+ k = n
⇒ 1 + (k * (k + 1) )/2 = n
⇒ k ² = n 
k = √n
Por lo tanto, la complejidad del tiempo es O(√n).

2. ¿Cuál es la complejidad temporal del siguiente código: 

void fun(int n)
{
    if (n < 5)
        cout << "GeeksforGeeks";
    else {
        for (int i = 0; i < n; i++) {
            cout << i;
        }
    }
}
 
// This code is contributed by Shubham Singh

void fun(int n)
{
    if (n < 5)
        printf("GeeksforGeeks");
    else {
        for (int i = 0; i < n; i++) {
            printf("%d", i);
        }
    }
}

public static void fun(int n)
{
    if (n < 5)
        System.out.print("GeeksforGeeks");
    else {
        for (int i = 0; i < n; i++) {
            System.out.print(i + " ");
        }
    }
}
 
// This code is contributed by Shubham Singh

def fun(n):
    if (n < 5):
        print("GeeksforGeeks", end ="")
    else:
        for i in range(n):
            print(i, end= " ")
             
# This code is contributed by Shubham Singh

public static void fun(int n)
{
    if (n < 5)
        Console.Write("GeeksforGeeks");
    else {
        for (int i = 0; i < n; i++) {
            Console.Write(i + " ");
        }
    }
}
 
// This code is contributed by Shubham Singh

<script>
function fun(n)
{
    if (n < 5)
        document.write("GeeksforGeeks");
    else {
        for (var i = 0; i < n; i++) {
            document.write(i + " ");
        }
    }
}
 
//This code is contributed by Shubham Singh
</script>

Solución – 
Complejidad de tiempo = O(1) en el mejor de los casos y O(n) en el peor de los casos.

Explicación:
este programa contiene condiciones if y else. Por lo tanto, hay 2 posibilidades de complejidad temporal. Si el valor de n es menor que 5, solo obtenemos GeeksforGeeks como salida y su complejidad temporal será O(1). 
Pero, si n>=5, el bucle for se ejecutará y la complejidad del tiempo se convierte en O(n), se considera el peor de los casos porque lleva más tiempo.

3. ¿Cuál es la complejidad temporal del siguiente código: 

void fun(int a, int b)
{
    while (a != b) {
        if (a > b)
            a = a - b;
        else
            b = b - a;
    }
}
 
// This code is contributed by Shubham Singh

void fun(int a, int b)
{
    while (a != b) {
        if (a > b)
            a = a - b;
        else
            b = b - a;
    }
}

public static void fun(int a, int b)
{
    while (a != b) {
        if (a > b)
            a = a - b;
        else
            b = b - a;
    }
}
 
// This code is contributed by Shubham Singh

def fun(a, b):
     
    while (a != b):
        if (a > b):
            a = a - b
        else:
            b = b - a
             
# This code is contributed by Shubham Singh

public static void fun(int a, int b)
{
    while (a != b) {
        if (a > b)
            a = a - b;
        else
            b = b - a;
    }
}
 
// This code is contributed by Shubham Singh

Solución –
Complejidad de tiempo = O(1) en el mejor de los casos y O(max(a, b)) en el peor de los casos.

Explicación:
si el valor de a y b es el mismo, entonces no se ejecutará el ciclo while. Por lo tanto, la complejidad del tiempo será O(1). 
Pero si a!=b, entonces se ejecutará el bucle while. Sea a=16 yb=5;

Para este caso, el ciclo while se ejecutó 8 veces (a/2⇒16/2⇒8). 
Si a=5 yb=16, entonces también el bucle se ejecutará 8 veces. Entonces podemos decir que la complejidad del tiempo es O(max(a/2,b/2))⇒O(max(a, b)) , se considera el peor de los casos porque toma más tiempo.

4. ¿Cuál es la complejidad temporal del siguiente código: 

void fun(int n)
{
  for(int i=0;i*i<n;i++)
    cout<<"GeeksforGeeks";
}
 
// This code is contributed by Shubham Singh

void fun(int n)
{
  for(int i=0;i*i<n;i++)
    printf("%s","GeeksforGeeks");
}

Solución – 
Complejidad temporal = O(√n).

Explicación –
Sea k el no. de iteración del bucle.

⇒ El ciclo se detendrá cuando i * i >=n ie, i*i=n
⇒ i*i=n ⇒ k ² = n
⇒ k =√n
Por lo tanto, la complejidad del tiempo es O(√n).

5. ¿Cuál es la complejidad temporal del siguiente código: 

void fun(int n, int x)
{
    for (int i = 1; i < n; i = i * x) //or for(int i = n; i >=1; i = i / x)
        cout << "GeeksforGeeks";
}
 
//This code is contributed by Shubham Singh

void fun(int n, int x)
{
    for (int i = 1; i < n; i = i * x) //or for(int i = n; i >=1; i = i / x)
        print("GeeksforGeeks");
}

Solución – 
Complejidad del tiempo = O(log _x n).

Explicación – 
Sea k el no. de iteración del bucle.

⇒ El bucle se detendrá cuando i>=n ⇒ x ^k = n
⇒ x ^k = n (Tome el registro de ambos lados)
⇒ k=log _x n
⇒ Por lo tanto, la complejidad del tiempo es O (log _x n).

6. ¿Cuál es la complejidad temporal del siguiente código: 

void fun(int n)
{
    for (int i = 0; i < n / 2; i++)
        for (int j = 1; j + n / 2 <= n; j++)
            for (int k = 1; k <= n; k = k * 2)
                cout << "GeeksforGeeks";
}

Solución –
Complejidad temporal = O(n ² log ₂ n).

Explicación – 
Complejidad de tiempo de 1 ^st for loop = O(n/2) ⇒ O(n).
Complejidad de tiempo del ^2º ciclo for = O(n/2) ⇒ O(n).
Complejidad de tiempo de 3 ^rd for loop = O(log ₂ n). (consulte el número de pregunta – 5)
Por lo tanto, la complejidad temporal de la función se convertirá en O (n ² log ₂ n).

7. ¿Cuál es la complejidad temporal del siguiente código: 

void fun(int n)
{
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j = j + i)
            cout << "GeeksforGeeks";
}

Solución – Complejidad de tiempo = O(nlogn).

Explicación – 
Complejidad de tiempo del primer ciclo for = O(n). El segundo bucle se ejecuta n/i veces para cada valor de i  ^.
Su complejidad temporal es O(∑ ⁿ _i=1 n/i) ⇒ O(logn).
Por lo tanto, complejidad temporal de la función = O(nlogn).

 8. ¿Cuál es la complejidad temporal del siguiente código:        

void fun(int n)
{
    for (int i = 0; i <= n / 3; i++)
        for (int j = 1; j <= n; j = j + 4)
            cout << "GeeksforGeeks";
}

Solución –   Complejidad temporal = O(n ² ).

Explicación – 
Complejidad de tiempo del primer ciclo for = O(n/3) ⇒ O(n).
Complejidad temporal del segundo ciclo for = O(n/4) ⇒ O(n).
Por lo tanto, la complejidad temporal de la función será O(n ² ) .

9. ¿Cuál es la complejidad temporal del siguiente código:   

void fun(int n)
{
    int i = 1;
    while (i < n) {
        int j = n;
        while (j > 0) {
            j = j / 2;
        }
        i = i * 2;
    }
}
 
//This code is contributed by Shubham Singh

void fun(int n)
{
    int i = 1;
    while (i < n) {
        int j = n;
        while (j > 0) {
            j = j / 2;
        }
        i = i * 2;
    }
}

Solución –   Complejidad temporal = O(log ² n).

Explicación: 
en cada iteración, i se convierte en dos veces (TC = O (logn)) y j se convierte en la mitad (TC = O (logn)). Entonces, la complejidad del tiempo se convertirá en O (log ² n).
Podemos convertir este ciclo while en un ciclo for.
    for( int i = 1; i < n; i = i * 2)
    for( int j=n ; j > 0; j = j / 2).

La complejidad del tiempo del bucle for anterior también es O (log ² n).

10. Considere el siguiente código C, ¿cuál es el número de comparaciones realizadas en la ejecución del bucle?

void fun(int n)
{
    int j = 1;
    while (j <= n) {
        j = j * 2;
    }
}

Solución – 
ceil(log ₂ n)+1.

Explicación –
Sea k el no. de iteración del bucle. Después del k-ésimo paso, el valor de j es 2 ^k . Por lo tanto, k=log ₂ n. Aquí, usamos el techo de log ₂ n , porque log ₂ n puede estar en decimal. Ya que estamos haciendo una comparación más para salir del bucle.
Entonces, la respuesta es ceil(log ₂ n)+1.