¿El siguiente algoritmo tiene un número ilimitado de pasos?

Answer 1

En realidad, creo que el número de pasos de este algoritmo es [matemática] O (n \ log (n)) [/ matemática]. Cuando me refiero a la descripción en la pregunta como algoritmo, considero los pasos matemáticos distintos de las operaciones específicas del lenguaje. Por ejemplo, el bucle interno podría ejecutarse infinitamente si la división [matemática] i / 40 [/ matemática] en el primer bucle interno se considera división entera, como es el caso en muchos lenguajes de programación como: C, C ++ y Java.

Permítanos mostrar por qué el número de pasos es [matemática] O (n \ log (n)) [/ matemática]. Primero consideramos el algoritmo en dos partes de la siguiente manera ya que los dos bucles internos (líneas 5-7 y 9-13) no están fuertemente correlacionados:

func_e (n) {
i = 1;
mientras que (i <n) do {
x = 1;
mientras que (x <5) do {
x = x + i / 40;
}
j = i;
mientras que (j> = 1) do {
k = 2;
mientras que (k <= j + 1)
j = j / 6;
}
i = i + 1;
}
}

El primer bucle interno (líneas 5-7) siempre agrega incrementos de [matemática] i / 40 [/ matemática] comenzando desde uno hasta llegar a [matemática] 5 [/ matemática]. Entonces, la complejidad temporal de este bucle en una iteración dada [matemática] i [/ matemática] es [matemática] 4 / (i / 40) [/ matemática] que es [matemática] 160 / i [/ matemática].

Consideremos el segundo bucle interno (líneas 9-13). El valor de j es inicialmente i. comenzamos a dividir j entre seis hasta que se convierte en menos de uno. El número de iteraciones de este ciclo es [math] \ log_6 (i) [/ math].

Por lo tanto, sumando el número de pasos del algoritmo, tenemos lo siguiente:

[matemáticas] \ sum_ {i = 1} ^ {n} (160 / i + \ log_6 (i)) = O (n \ log (n)) [/ matemáticas] como [matemáticas] \ sum_ {i = 1} ^ {n} 1 / i = H (n) [/ math] es el número armónico [math] H (n) [/ math] donde [math] ln (n) \ leq H (n) \ leq ln (n ) +1 [/ matemáticas].