Algun ingeniero informatico que me eche un cable

Archivado
Tengo que calcular la complejidad de un algoritmo y me encuentro con este bucle ,la cuestion es que se quee l bucle se ejecuta (n/4)+1,(el (n/4) es parte entera por defecto),la cuestion es como queda acotado el numero de iteraciones?(log4 n)+1??No se si hay que tomar logaritmos o que :-? ..
void funcion(int n){
        i=0;
        while(i<=n){
            i=i+4;
        }
}
zaius5 escribió:la cuestion es como queda acotado el numero de iteraciones?(log4 n)+1??

Ponte una variable contador y haz que aumente con el bucle:

void funcion(int n){
        int contador = 0;
        i=0;
        while(i<=n){
            i=i+4;
            contador++;
        }
}


Ala, ya tienes las iteraciones contadas [carcajad]

Pero vamos, el bucle se repite n/4 veces. Siendo n/4 una división entera (sin decimales).
El lazo se repite n/4 veces, luego es 1/4*n,

Al ser 1/4 constante la cota es O(n), es decir, el tiempo de ejecución aumenta linealmente con el tamaño del array.
demnim escribió:El lazo se repite n/4 veces, luego es 1/4*n,

Al ser 1/4 constante la cota es O(n), es decir, el tiempo de ejecución aumenta linealmente con el tamaño del array.


a o(n) no lo va a superar, eso es evidente, pero hay cotas mas cercanas.me explico:
para n=4, el bucle se recorre dos veces, no cuatro (n), para n = 8, 3 veces (menor o igual es la condición), de manera que efectivamente O((log4 n) +1) cumple como cota de forma mucho mas real que O(n).

Además, ¿donde está el array?
el_itinerante escribió:
demnim escribió:El lazo se repite n/4 veces, luego es 1/4*n,

Al ser 1/4 constante la cota es O(n), es decir, el tiempo de ejecución aumenta linealmente con el tamaño del array.


a o(n) no lo va a superar, eso es evidente, pero hay cotas mas cercanas.me explico:
para n=4, el bucle se recorre dos veces, no cuatro (n), para n = 8, 3 veces (menor o igual es la condición), de manera que efectivamente O((log4 n) +1) cumple como cota de forma mucho mas real que O(n).

Además, ¿donde está el array?


Tienes razón XD es lo que tiene leerlo en diagonal, pensé en el típico problema con un array y por eso lo dije.

No obstante creo que la cota es O(n) con la notación Big-O dado que es la cota superior asintótica,
en caso de que pidan la cota ajustada creo que sería (1/4 * n +1), el +1 es debido al <= que tiene el lazo while, aunque puedo estar equivocado :)
denin:
creo que tienes los conceptos algo bajos, al principio a mi también me parecía todo O(n), pero tampoco aprovaba :) :) , hasta que comprendí que lo que pasaba es que no tenía los conceptos claros.En genbetaDev han puesto un reportaje bastante clarito respecto a la complejidad computacional.
Zaius, para pasar de una cosa a la otra, ya no tiene nada que ver con algoritmia, sino con mates, mirate las propiedades de los logaritmos.
(mensaje borrado)
6 respuestas
Archivado
Volver a General