algorithm - for - big o notation pdf
¿Determinar los tiempos de ejecución grandes-O de estos diferentes bucles? (1)
Vamos a repasar esto de uno en uno.
Parte (a)
int x=0; //constant
for(int i=4*n; i>=1; i--) //runs n times, disregard the constant
x=x+2*i;
Mi respuesta: O (n)
¡Sí! Eso es correcto. El bucle se ejecuta O (n) veces y funciona O (1) por iteración.
Parte B)
int z=0;
int x=0;
for (int i=1; i<=n; i=i*3){ // runs n/3 times? how does it effect final answer?
z = z+5;
z++;
x = 2*x;
}
Mi respuesta: O (n)
No exactamente. Piensa en los valores de i medida que avanza el bucle. Tomará la serie de valores 1, 3, 9, 27, 81, 243, ..., 3 k . Ya que i estoy triplicando en cada iteración, asume poderes sucesivos de tres.
El bucle claramente solo funciona con O (1) por iteración, por lo que la pregunta principal aquí es cuántas iteraciones totales habrá. El bucle se detendrá cuando i > n . Si permitimos que k sea una iteración arbitraria del bucle, el valor de i en la iteración k será 3 k . El bucle se detiene cuando 3 k > n, lo que sucede cuando k> registro 3 n. Por lo tanto, el número de iteraciones es solo O (log n), por lo que la complejidad total es O (log n).
Parte (c)
int y=0;
for(int j=1; j*j<=n; j++) //runs O(logn)? j <= (n)^1/2
y++; //constant
Mi respuesta: O (logn)
No exactamente. Tenga en cuenta que j sigue creciendo de forma lineal, pero el bucle se ejecuta siempre que j 2 ≤ n. Esto significa que tan pronto como j exceda de √ n, el bucle se detendrá. Por lo tanto, solo habrá O (√n) iteraciones del bucle, y dado que cada una funciona con O (1), el trabajo total realizado es O (√n).
Parte (d)
int b=0; //constant
for(int i=n; i>0; i--) //n times
for(int j=0; j<i; j++) // runs n+ n-1 +...+ 1. O(n^2)
b=b+5;
Mi respuesta: O (n ^ 3)
No exactamente. En realidad estás contando doblemente mucho del trabajo que tienes que hacer. Tienes razón en que el bucle interno ejecutará n + (n-1) + (n-2) + ... + 1 veces, que es O (n 2 ) veces, pero ya estás resumiendo en todas las iteraciones del bucle exterior. No es necesario multiplicar ese valor por O (n) una vez más. La respuesta más precisa sería O (n 2 ).
Parte (e)
int y=1;
int j=0;
for(j=1; j<=2n; j=j+2) //runs n times
y=y+i;
int s=0;
for(i=1; i<=j; i++) // runs n times
s++;
Mi respuesta: O (n)
¡Sí! Exactamente correcto.
Parte (f)
int b=0;
for(int i=0; i<n; i++) //runs n times
for(int j=0; j<i*n; j++) //runs n^2 x n times?
b=b+5;
Mi respuesta: O (n ^ 4)
Una vez más, creo que estás contando demasiado. El bucle interno ejecutará 0 + n + 2n + 3n + 4n + ... + n (n-1) = n (0 + 1 + 2 + ... + n - 1) veces, por lo que el trabajo total realizado es O (n 3 ). No debe multiplicarse por el número de veces que se ejecuta el bucle externo porque ya está sumando todas las iteraciones. El tiempo de ejecución más preciso sería O (n 3 ).
Parte (g)
int x=0;
for(int i=1; i<=n; i=i*3){ //runs 1, 3, 9, 27...for values of i.
if(i%2 != 0) //will always be true for values above
for(int j=0; j<i; j++) // runs n times
x++;
}
Mi respuesta: O (nx log base 3 n?)
El bucle externo aquí se ejecutará O (log n) veces, pero veamos cuánto trabajo hace el bucle interno. Tienes razón en que la sentencia if siempre se evalúa como verdadera. Esto significa que el bucle interno hará 1 + 3 + 9 + 27 + ... + 3 log 3 n trabajo. Sin embargo, esta suma se resuelve en (3 log 3 n + 1 - 1) / 2 = (3n + 1) / 2. Por lo tanto, el trabajo total realizado aquí es solo O (n).
Parte (h)
int t=0;
for(int i=1; i<=n; i++) //runs n times
for(int j=0; j*j<4*n; j++) //runs O(logn)
for(int k=1; k*k<=9*n; k++) //runs O(logn)
t++;
Mi respuesta: nx logn x log n = O (n log n ^ 2)
No exactamente. Mira el segundo bucle. Esto realmente se ejecuta O (√n) veces usando la misma lógica que una de las partes anteriores. Ese tercer bucle interno también se ejecuta O (√n) veces, por lo que el trabajo total realizado será O (n 2 ).
Parte (i)
int a = 0;
int k = n*n;
while(k > 1) //runs n^2
{
for (int j=0; j<n*n; j++) //runs n^2
{ a++; }
k = k/2;
}
Mi respuesta: O (n ^ 4)
No exactamente. El bucle externo comienza con k inicializado en n 2 , pero observe que k se divide en dos en cada iteración. Esto significa que el número de iteraciones del bucle externo será log (n 2 ) = 2 log n = O (log n), por lo que el bucle externo se ejecuta solo O (log n) veces. Ese bucle interno no funciona con O (n 2 ), por lo que el tiempo de ejecución total es O (n 2 log n).
Parte (j)
int i=0, j=0, y=0, s=0;
for(j=0; j<n+1; j++) //runs n times
y=y+j; //y equals n(n+1)/2 ~ O(n^2)
for(i=1; i<=y; i++) // runs n^2 times
s++;
Mi respuesta: O (n ^ 3)
Cerca, pero no del todo! El primer bucle se ejecuta en el tiempo O (n) y en el momento en que se realiza, el valor de j es Θ (n 2 ). Esto significa que el segundo bucle se ejecuta para el tiempo Θ (n 2 ), por lo que el tiempo total empleado es Θ (n 2 ).
Parte (k)
int i=1, z=0;
while( z < n*(n+1)/2 )//arithmetic series, runs n times
{
z+=i; i++;
}
Mi respuesta: O (n)
¡Eso es correcto!
Parte (l)
Eso es extraño, no hay parte (l).
Parte (m)
int a = 0;
int k = n*n*n;
while(k > 1) //runs O(logn) complexity
{
for (int j=0; j<k; j++) //runs n^3 times
{ a--; }
k = k/2;
}
Mi respuesta: O (n ^ 3 log n)
Cerca, pero no del todo. Tiene razón en que el bucle externo ejecuta O (registro n) veces y que el bucle interno no funciona con O (n 3 ) en la primera iteración. Sin embargo, observe el número de iteraciones del bucle interno más de cerca:
n 3 + n 3 / 2+ n 3/4 + n 3/8 + ...
= n 3 (1 + 1/2 + 1/4 + 1/8 + ...)
≤ 2n 3
Por lo tanto, el trabajo total realizado aquí es en realidad solo O (n 3 ), aunque hay log n iteraciones.
Pregunta 4
Tus respuestas son todas correctas, excepto estas:
f) Verdadero
Esto es realmente falso. La expresión de la izquierda es
(3/2) n 3/2 + 5n 2 + lg n
que no es Ω (n 2 √n) = Ω (n 5/2 )
Para (j), tenga en cuenta que log n 6 = 6 log n. ¿Eso ayuda?
Para (k), pregunte si ambos lados son O y entre sí. ¿Qué encuentras?
Para (l), use el hecho de que a log b c = c log b a . ¿Eso ayuda?
¡Espero que esto ayude!
Tengo una serie de preguntas en las que necesito comentarios y respuestas. Voy a comentar sobre lo que pienso, esto no es una tarea, sino una preparación para mi examen.
Mi principal problema es determinar las iteraciones de un bucle para diferentes casos. ¿Cómo trataría de tratar de resolver eso?
Evaluar el tiempo de ejecución.
Q2.
for(int i =0 ; i < =n ; i++) // runs n times
for(int j =1; j<= i * i; j++) // same reasoning as 1. n^2
if (j % i == 0)
for(int k = 0; k<j; k++) // runs n^2 times? <- same reasoning as above.
sum++;
Respuesta correcta: N × N2 × N = O (N ^ 4)
Para las siguientes preguntas a continuación, no tengo las respuestas correctas.
Q3. una)
int x=0; //constant
for(int i=4*n; i>=1; i--) //runs n times, disregard the constant
x=x+2*i;
Mi respuesta: O (n)
b) Supongamos por simplicidad que n = 3 ^ k
int z=0;
int x=0;
for (int i=1; i<=n; i=i*3){ // runs n/3 times? how does it effect final answer?
z = z+5;
z++;
x = 2*x;
}
Mi respuesta: O (n)
c) Supongamos por simplicidad que n = k ^ 2,
int y=0;
for(int j=1; j*j<=n; j++) //runs O(logn)? j <= (n)^1/2
y++; //constant
Mi respuesta: O (logn)
re)
int b=0; //constant
for(int i=n; i>0; i--) //n times
for(int j=0; j<i; j++) // runs n+ n-1 +...+ 1. O(n^2)
b=b+5;
Mi respuesta: O (n ^ 3)
(mi)
int y=1;
int j=0;
for(j=1; j<=2n; j=j+2) //runs n times
y=y+i;
int s=0;
for(i=1; i<=j; i++) // runs n times
s++;
Mi respuesta: O (n)
(F)
int b=0;
for(int i=0; i<n; i++) //runs n times
for(int j=0; j<i*n; j++) //runs n^2 x n times?
b=b+5;
Mi respuesta: O (n ^ 4)
(g) Supongamos, para simplificar, que n = 3k, para algún entero k positivo.
int x=0;
for(int i=1; i<=n; i=i*3){ //runs 1, 3, 9, 27...for values of i.
if(i%2 != 0) //will always be true for values above
for(int j=0; j<i; j++) // runs n times
x++;
}
Mi respuesta: O (nx log base 3 n?)
(h) Supongamos, para simplificar, que n = k2, para algún entero k positivo.
int t=0;
for(int i=1; i<=n; i++) //runs n times
for(int j=0; j*j<4*n; j++) //runs O(logn)
for(int k=1; k*k<=9*n; k++) //runs O(logn)
t++;
Mi respuesta: nx logn x log n = O (n log n ^ 2)
(i) Supongamos, para simplificar, que n = 2s, para algunos enteros positivos s.
int a = 0;
int k = n*n;
while(k > 1) //runs n^2
{
for (int j=0; j<n*n; j++) //runs n^2
{ a++; }
k = k/2;
}
Mi respuesta: O (n ^ 4)
(j)
int i=0, j=0, y=0, s=0;
for(j=0; j<n+1; j++) //runs n times
y=y+j; //y equals n(n+1)/2 ~ O(n^2)
for(i=1; i<=y; i++) // runs n^2 times
s++;
Mi respuesta: O (n ^ 3)
(k) int i = 1, z = 0; while (z <n * (n + 1) / 2) {// series aritméticas, se ejecuta n veces z + = i; i ++; }
Mi respuesta: O (n)
(m) Supongamos, para simplificar, que n = 2s, para algunos enteros positivos s.
int a = 0;
int k = n*n*n;
while(k > 1) //runs O(logn) complexity
{
for (int j=0; j<k; j++) //runs n^3 times
{ a--; }
k = k/2;
}
Mi respuesta: O (n ^ 3 log n)
Pregunta 4
http://i.stack.imgur.com/zMkt7.jpg
- a) Verdadero, ya que está delimitado por n ^ 2
- b) Falso: f (n) no es estrictamente más pequeño que g (n)
- c) Verdadero
- d) Verdadero: unido por n ^ 10
- e) Falso - f (n) no estrictamente más pequeño que g (n)
- f) Verdadero
- g) Verdadero
- h) falso - ya que no es igual a O (nlogn)
- i) verdadero
- j) no estoy seguro
- k) no estoy seguro
- l) no estoy seguro, ¿cómo debo intentar esto? *
Gracias por adelantado.