Ayuda Algorítmica y Complejidad

Front page Foros Offtopic Ayuda Algorítmica y Complejidad

Viendo 10 entradas - de la 1 a la 10 (de un total de 10)
  • Autor
    Entradas
  • #50884
    WorvastWorvast
    Miembro

    *los corchetes han sido sustituidos por «|» ya que el foro los quita por el tema de las etiquetas

    Creo un hilo para aumentar la visibilidad y mis posibilidades de no pringar ya una asignatura sean mayores, aquí hay gente que sabe programar y tal y no sé, antes de seguir yo dándome ostias solo pierdo 5 minutos y tal vez, por arte de magia, me salve el culo poner aquí mi duda aunque no tenga mucha relación, siempre hay que intentarlo todo antes de suspender.

    El caso, resumido, es el siguiente: Desde que suspenda una práctica estoy suspendido en Algorítmica, no he podido ir mucho a clase, por lo que no conozco a nadie allí, y la posibilidad de que me pasen la práctica hecha está descartada y los apuntes no son muy claros, aunque se entienden, y no soy capaz de terminar por mi mismo la práctica y para acabar la profe no contesta respuestas de este tipo por email, solo en las tutorias, que están puestas justo en las horas en las que tenemos que hacer las prácticas en el laboratorio, así ella puede ayudar, pero justo esas horas están puestas cuando yo no puedo ir a clase, por trabajo, así que estoy en situación de: o me las hago yo solito o me joden

    Tengo uno de las 3 cosas que hay que hacer, una aún no lo he sacado aunque esté a medias y otra no la entiendo, seguid leyendo los conocedores de Java y/o matemáticas

    El estudio de la complejidad temporal de un algoritmo no se centra sólo en el cálculo aproximado del tiempo de ejecución. En determinadas situaciones, interesa conocer el número de operaciones efectuadas de un tipo concreto en el peor caso, debido principalmente a que estas operaciones suelen ser más costosas.

    Las reglas para establecer el número de operaciones de un determinado tipo son similares a las enunciadas en las clases teóricas, contemplando solamente aquellas instrucciones relativas al tipo de operación en cuestión. Por ejemplo, supongamos que se quiere determinar el número de comparaciones que involucran a un elemento de un vector en el siguiente código:

    public static int busquedaDespuesDeAcumular(int[] vector, int clave){
    for (int i = 0; i < vector.length; i++){
    for (int j = i; j < vector.length; j++){
    vector|i| = vector|j|;
    }
    }
    for (int i=0; i < vector.length; i++){
    if (vector|i| == clave)
    return i;
    }
    return -1;
    }

    Como dentro de los dos primeros bucles anidados (líneas de 2 a 6) no se realizan comparaciones con un elemento del vector no los tendremos en cuenta. El bucle que va de la línea 7 a la 10, sí que implica comparaciones con un elemento del vector (línea 8). Por lo tanto, el número de comparaciones, en el peor caso, será igual al número de veces que se ejecuta este último bucle que va a coincidir con el número de elementos del vector.

    Otra posibilidad para determinar el número de operaciones de un determinado tipo consiste en introducir un contador en el código que se incrementa cada vez que se realiza una de dichas operaciones, tal y como se aprecia en el siguiente código

    public static int Comparaciones = 0;
    public static int busquedaDespuesDeAcumular(int[] vector, int clave){
    for (int i = 0; i < vector.length; i++){
    for (int j = i; j < vector.length; j++){
    vector|i| = vector|j|;
    }
    }
    for (int i=0; i < vector.length; i++){
    Comparaciones++;
    if (vector|i| == clave)
    return i;
    }
    return -1;
    }

    Se pide:

    1. Escribir 3 métodos en Java que efectúen respectivamente, en el peor caso, n, n.log(n) y un valor no polinómico de operaciones que involucren la comparación en un vector de n posiciones. Los métodos codificados no tienen porqué resolver algún problema en concreto.

    2. Comprobar por el método de los contadores de operaciones que los resultados son correctos para n=5, n=10 y n=15.

    Entonces esto trata de complejidad, por lo que yo supongo que cuando dice que cree 3 métodos que efectuen, en el peor caso, n, n log n y un valor no polinómico yo estoy seguro de que se refiere a 3 funciones que tengan una complejidad dicha, en ese caso, aquí el de complejidad N para buscar en un vector

    public static int busquedaN(int[] v, int valor){
    for (int i=0; i < v.length; i++){
    if (v|i| == valor)
    return i;
    }
    return -1;
    }

    Complejidad lineal O(n), osea, se ejecuta N veces

    La duda me llega a la hora de conseguir algo que compare con el O(n log n), aquí tengo un algoritmo de este tipo de complejidad, pero que no compara:

    int c, x; //O(1)
    for(int i= 0; i 0) //O(log n)
    {
    x = x % c; //O(1)
    c = c / 2; //O(1)
    }
    x = x + 2; //O(1)
    }

    Como veis el O(x) indica la complejidad, en este caso la complejidad es O(n) * O(log n) * O(1) = O(n log n)

    Esto viene del primer for, O(n), multiplicado por lo lo que mas complejidad tenga dentro, que es un for de O(log n) multiplicado por el que mas complejidad tenga dentro, un O(1)

    Supongo que este tampoco me preocupa mucho, algo con esta complejidad acabaré sacando, aunque si se os ocurre algo rápido, agradecido quedo.

    Y bueno, mi mayor problema viene con el de un valor no polinómico de veces, con esto no tengo ni idea de que hacer, he intentado dar explicaciones de todo lo que sé para ver si alguien que sepa que es un valor no polinómico y entienda un poquillo le brillaba la bombilla xD

    Tengo hasta mañana, que he estado pensando y pensando y nada hasta ahora que ya me veo apurado.

    #467936
    La VoisinLa Voisin
    Miembro

    1. Ordena un vector eficientemente.
    2. ???
    3. PROFIT!

    #467947
    WorvastWorvast
    Miembro

    No lo entiendo, ordenando un vector no te aseguras que consigues un algoritmo de complejidad O(n log n), posiblemente un algoritmo O(n^2), ya que generalmente se juega con dos for, pero conseguir un O(log n) implica introducir un valor descendente como condición en un bucle de manera no lineal, cosa que no veo muy útil generalmente, ni me asegura que en el peor caso sea O(n log n), como en el quick sort, que en el mejor caso es O(n log n) y en el peor O(n^2)

    #467950
    La VoisinLa Voisin
    Miembro

    @worvast dijo:
    No lo entiendo, ordenando un vector no te aseguras que consigues un algoritmo de complejidad O(n log n),

    Si que lo aseguras si lo haces bien, mira la wikipedia, que hay varios métodos.

    #467972
    WorvastWorvast
    Miembro

    Solo hay 2 métodos de ordenación estables que sean O(n log n) eh, Ordenamiento por mezcla y Ordenamiento con árbol binario, el resto o no son estables (no me vale) o no son O(n log n), de todas formas no hace falta que haga nada como explica el enunciado así que he hecho una chorrada ya.

    solo me falta lo del valor no polinómico, gracias a dios que la gente me ha ido contestado por twitter tal vez esto por aquí aunque no fueran anaiteros (Puse la url) y bueno, voy avanzando y hasta me han pasado apuntes.

    #467978
    La VoisinLa Voisin
    Miembro

    La «estabilidad» que dice en la wikipedia se refiere a si el algoritmo de ordenación no cambia de orden los elementos elementos que son iguales, no quiere decir que funcione a veces y a veces no, o que el ordenador te vaya a explotar.
    Aunque eso lo explica en el artículo de wikipedia que has mirado, deberías leertelo un poco más a fondo.

    De todas formas en el ejercicio sólo te pide un algoritmo con O(n logn). Con lo de tiempo no polinómico se refiere a un algoritmo de n^2 o superior, por ejemplo el gnomesort.

    #467991
    WorvastWorvast
    Miembro

    Se lo que es la estabilidad en un algoritmo, y directamente no tenemos permitido usar algoritmos inestables al no ser que la profesora lo diga, o los esté explicando, cuestión de ella.

    También me leí ese artículo a fondo, y si te preocupa menos, fue después de leerme los apuntes, así que casi todo lo sabía menos los diferentes tipos de algoritmos, que no los he dado todos obviamente

    Y ya lo sé, por eso en un principio no estaba buscando un algoritmo de ordenación, que son facilmente copiables de internet y seguramente revisado por la profesora, y buscaba cualquier chorrada en la que hubiera que comparar un vector, pero sin hacerle nada serio.

    A lo de no polinómico, gracías, pero, n^2 no es un polinomio? Bueno, como hablaba con miyagi, es un monomio, pero es que un monomio es un polinomio de grado 0. Luego viene todo el rollo de que tal vez si que se puedan diferenciar, bla bla, y la profesora se haya equivocado y lo haya liado un poco, pero no me equivoco no? En fin, haré la burbuja entonces para el n^2 que me vale y ya lo tengo hecho por ahí

    Gracias por todo

    #467995
    YggdrasilYggdrasil
    Miembro

    Con lo de no polinómico igual se refiere a O(2^n) o O(n!).

    #468029
    MrMiyagiMrMiyagi
    Miembro

    hombre! Contexto! Ahora no puedo, luego miro si puedo ayudar… aunque no creo :P

    #468091
    WorvastWorvast
    Miembro

    Eso deberías saberlo o suponerlo pero en cualquier caso nos referimos
    a una complejidad exponencial o factorial.

    A eso se refería con lo de «no polinómico», aunque a mi me sigue pareciendo poco claro lo de «no polinómico», será por el desconocimiento de esa palabra xD

Viendo 10 entradas - de la 1 a la 10 (de un total de 10)
  • Debes estar registrado para responder a este hilo.