4
int misterio(int n) {
    int r = 0, x = 2;
    while (x < n) {
        r++;
        x = x * 2;
    }
    return r;
}

Considerando el valor de n es un potencia de 2, por ejemplo 256, 512, 1024, etc.

int x = misterio(256);

La complejidad es:

formula

pero no lo entiendo muy bien el porqué. Si alguien me ayuda se lo agradecería.

3
  • A ver si entiendo, quieres saber el por que de está función. Buscas una explicación del funcionamiento?
    – user166844
    Commented el 3 jul. 2020 a las 22:07
  • 1
    @gcoronel99, lo que busca es la complejidad del algoritmo en términos matemáticos. Es una muy buena pregunta si algún experto colabora seria genial.
    – Shassain
    Commented el 4 jul. 2020 a las 4:18
  • un buen lugar para leer sobre ello cs.us.es/~jalonso/cursos/i1m-19/temas/tema-28.html.
    – Shassain
    Commented el 4 jul. 2020 a las 4:25

2 respuestas 2

7

El algoritmo está basado en el ciclo while, entonces la complejidad dependerá de cuántas veces se ejecuta el ciclo dado n.

Dada la condición del ciclo while, se puede deducir que se ejecutará hasta que:

x >= n

Para saber cuántas veces se ejecutara, nos faltaría saber la relación entre los valores de x y la iteración realizada

iteración  x
0          2
1          4
2          8
3          16
4          32

De la tabla anterior se deduce que x = 2^(i+1) en dónde irepresenta el número de iteraciones realizadas.

Por lo tanto, resolvemos la desigualdad:

x >= n
2^(i+1) >= n 
i+1 >= log2(n)
i >= log2(n) - 1

Es decir, que el ciclo while tendrá a lo mucho log2(n)-1 iteraciones, por lo que esa es la complejidad del algoritmo.

2
  • Gracis por tu respuesta me ha gustado y es facil de enter asi. Hay alguna página web o libro que recomiendes para resolver este tipo de algorítmos como tu lo resuelves?
    – CCK
    Commented el 4 jul. 2020 a las 16:33
  • @CCK si la respuesta te ha sido útil y responde a tu pregunta, por favor considera votarla positiva y marcarla como aceptada.
    – ordago
    Commented el 6 jul. 2020 a las 15:14
1

En análisis de algoritmos se estudia el tiempo de ejecución en función del tamaño del problema a resolver, en este caso n.

Un buen algoritmo o programa es aquel que para cualquier tamaño (especialmente tamaños de problemas enormes) realiza muy pocos cálculos, lo que se traduce en un consumo menor de recursos: tiempo y memoria.

Ahora bien, medirlo es difícil, y en ocasiones el resultado depende de cuán preciso y formal quieras ser.

La técnica básica para calcular el tiempo teórico de ejecución es el conteo de instrucciones, en el que vas contando instrucciones teniendo en cuenta si hay condicionales (como if) o bucles (while o for).

En este sentido, puedes contar el número de iteraciones del bucle principal, que más o menos es lo que ha hecho Carlos Pozos, pero otras alternativas también son contar instrucciones según diferentes criterios.

int i = 25 * 2 + 1;

Esta línea de código, por ejemplo, se puede contar como:

  • 1 línea de código de tiempo constante: 1 unidad
  • 3 instrucciones de tiempo equivalente( multiplicación, suma y asignación): 3 unidades
  • 3 instrucciones que con tiempos diferentes, expresados en segundos: t_mult + t_add + t_w segundos

Escogida una de las maneras de contar el tiempo del programa o algoritmo, se procede a contar el tiempo.

Si contamos las líneas de código, por ejemplo, vemos que el tiempo es: 1 + t_while + 1

Teniendo en cuenta que las declaraciones de variables y el return las puedes contar como 1 unidad.

El tiempo del bucle principal viene dado por el número de iteraciones que se van a dar, que en este caso es log2(n) - 1, ya que la variable de control va aumentando en potencias de 2, y solo se entra al bucle cuando es menor que n.

Además, en cada iteración se ejecutan varias instrucciones (comprobación de condición de continuación del bucle, incremento, multiplicación y asignación), con tiempo 3 (4 si cuentas las expresiones como varias instrucciones, e incluso más si cuentas las lecturas de las variables). Y tenemos que tener en cuenta que tras la última iteración, se comprobará una vez más la condición del bucle para salir del mismo y devolver el resultado, por lo que el tiempo queda como:

t(n) = 1 + [(log2(n) - 1) * 3 + 1] + 1 = 3 * log2(n)

Ahora, con el tiempo calculado, podemos hablar de muchas cosas:

  • El tiempo de ejecución es una función de n, en concreto t(n) = 3 * log2(n)
  • El tiempo pertenece al orden de complejidad de ln(n) porque ln(n) es una cota superior para el tiempo de ejecución si lo multiplicamos por una constante (definición matemática)
  • El tiempo no va a ser menor que 3 * log2(n), por lo que también tiene a ln(n) como cota inferior, es decir, que t(n) pertenece a Omega(ln(n))
  • Como ln(n) es cota superior e inferior del tiempo de ejecución, podemos afirmar que el tiempo de ejecución tiene un orden exacto, llamado theta, de ln(n)
  • Además la o-pequeña del tiempo de ejecución va a ser 3 * log2(n)

Nota: en el orden complejidad no importan las constantes ni los términos distintos a los de mayor orden, por eso salen resultados iguales aunque se cuente con más o menos precisión. Lo único que cambiará es la o-pequeña. Ejemplo: una función t(n) = 3 * n + 23 pertenece al orden de complejidad lineal O(n). Como ves, se ha eliminado la constante 3, que multiplicaba a n, y el término (factor) 23, que es de menor orden.

Todo esto tiene que ver con el estudio de las notaciones asintóticas y teoría de conjuntos (el orden de complejidad es un conjunto, en este caso de funciones).

Siento no explicar con más detalle, pero este tema daría para una clase.

0

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.