¿Cuáles son las complejidades de los siguientes dos algoritmos y la frecuencia de ocurrencia de cada paso?

Answer 1

Cuando observa este tipo de problemas, observa qué aporta cada parte del código. Si tiene algo dentro de un ciclo, su complejidad se multiplica por la complejidad del ciclo.

Si tiene un ciclo que se ejecuta y finaliza, entonces otro ciclo que se ejecuta, suma sus complejidades (lo que significa que obtendrá la mayor de las dos complejidades).

# 1: tienes un bucle externo y un bucle interno. Mira cuántas veces se puede ejecutar el bucle externo.

Si n es positivo, el bucle externo se ejecutará una vez. j comienza como n, luego se divide por 3. El resultado es menor que n, por lo que el ciclo ya no se ejecuta. Como el número de bucles no varía con n, lo ignoraremos para descubrir la complejidad. Comenzamos como O (1), y esto no aporta nada, así que seguimos siendo O (1).

Si n es negativo, es una historia diferente. j comienza como n, luego se divide por 3. El valor nunca más es menor que n, por lo que el bucle externo se ejecuta para siempre. Este es probablemente un problema con la definición del problema. Eso significa que esto ya no es un algoritmo, porque no se garantiza que termine en un tiempo finito.

Pero ignorando eso y volviendo a la tierra positiva, el ciclo interno se ejecuta una vez, donde j == n. Se repite n veces. Eso contribuye n. Si nuestra complejidad hubiera sido O (n ^ 2), ahora sería O (n ^ 3). Pero era solo O (1), por lo que ahora es O (n), que es el resultado final. (Pero todavía no es un algoritmo y esta no es realmente una respuesta válida).

# 2: Para n = 2, el ciclo comienza a suceder.

EDITAR:
El número de veces que el ciclo pasa al # 2 es log (n), ya que se multiplica cada vez. (Originalmente dije que era proporcional a n. Leí mal el * como un +.) Gracias Jeff Little.

Answer 2

Suponiendo que n es positivo, las complejidades son O (N) y O (log n).

Problema # 1.
j = n O (1)
while (j> = n) {O (1) *
Para (i = 1; i X = X +1} O (N)
j = j / 3} O (1)

Problema # 2.
i = 2 O (1)
mientras que (i i = 2 * i O (log N)
X = X + 1} O (log N)

* el ciclo while solo se llamará una vez para n positivo.
** J va de 1 a N
*** doblo cada ciclo, así que el último será 2 ^ k **** donde k = log2 (N)
**** k porque O (k-1) = O (k). Los errores uno por uno no importan para la notación O grande.

Answer 3

#problema 1:
aquí inicialmente el valor de j es igual a n.
En for loop, i va de 1 a j, que es igual a n. entonces para el ciclo se rompe y j se convierte en n / 3, que es menor que n, por lo que el ciclo while también se rompe.
Así que n iteraciones totales.
Complejidad O (n)

#problema 2:
Aquí, cuando me vuelvo igual o mayor que n, el bucle se rompe y cada vez me vuelvo dos veces más que la última vez, por lo que la iteración total = n / 2
La complejidad debe ser O (n / 2), pero 1/2 es constante, por lo que podemos contarla a partir de la notación O grande
Entonces complejidad: O (n)

Answer 4

¿Debo contactar a Soly Mathew-Biju o Gene Awyzio y pedirles las respuestas a sus preguntas?

Nunca he visto una pregunta con más tarea que esta. Elimínelo de inmediato y obtenga ayuda en Wollongong.