c++ - resueltos - manual de programacion android pdf

Mientras eliminamos la constante en gran notación O, ¿importa en situaciones de la vida real?

Question

Si bien entiendo que la gran notación O simplemente describe la tasa de crecimiento de un algoritmo, no estoy seguro si hay alguna diferencia en la eficiencia en la vida real entre los siguientes algoritmos O (n).

Para imprimir el valor de un nodo en una lista enlazada k lugares desde el final de la lista.

Dado un nodo:

/* Link list node */
struct node
{
  int data;
  struct node* next;
};

Solución 1 O (n)

Esta solución recorre la lista dos veces, una para encontrar la longitud de la lista y la segunda para llegar al final de la lista - N.

void printNthFromLast(struct node* head, int n)
{
    int len = 0, i;
    struct node *temp = head;


    // 1) Count the number of nodes in Linked List
    while (temp != NULL)
    {
        temp = temp->next;
        len++;
    }

    // Check if value of n is not more than length of the linked list
    if (len < n)
      return;

    temp = head;

    // 2) Get the (n-len+1)th node from the begining
    for (i = 1; i < len-n+1; i++)
    {
       temp = temp->next;
    }
    printf ("%d", temp->data);

    return;
}

Solución 2 O (n)

Esta solución solo itera sobre la lista una vez. El puntero ref_ptr avanza, y un segundo puntero (main_ptr) lo sigue k lugares detrás. Cuando ref_ptr llega al final de la lista, main_ptr debería estar apuntando al nodo correcto (k coloca desde el final de la lista).

void printNthFromLast(struct node *head, int n)
{
  struct node *main_ptr = head;
  struct node *ref_ptr = head;

  int count = 0;
  if(head != NULL)
  {
    while( count < n )
     {
        if(ref_ptr == NULL)
        {
           return;
        }
        ref_ptr = ref_ptr->next;
        count++;
     }

     while(ref_ptr != NULL)
     {
        main_ptr = main_ptr->next;
        ref_ptr  = ref_ptr->next;
     }
  }
}

La pregunta es: aunque ambas soluciones son O (n) y dejan de lado la gran notación O, ¿es la segunda solución más eficiente que la primera para una lista muy larga, ya que solo se repite en la lista una vez?

Answer 1

Creo que, desde mi punto de vista, la diferencia entre dos rutinas que son O (n) y O (n), por ejemplo, no es realmente el punto de la notación O. Las diferencias clave son entre O (n ^ 2) y O (n), por ejemplo. [n ^ 2 es por supuesto n al cuadrado]

Entonces, en general, la potencia, p, para O (n ^ p) es fundamental en la forma en que la eficiencia de una rutina se ajusta al tamaño.

Entonces, al observar las dos rutinas que tiene, puede haber diferencias en el rendimiento entre ellas, pero en una primera aproximación se comportarán de manera similar a medida que aumenta el tamaño del conjunto de datos.

Un ejemplo de código donde la escala es clave es la Transformada de Fourier, donde algunos métodos dan O (n ^ 2) y otros dan O (n log n).

Answer 2

Este es el tipo de pregunta que las personas hacen cuando pasan de la academia a la práctica.

Ciertamente, la O grande es importante si es probable que sus conjuntos de datos sean muy grandes, donde "muy grande" es para que usted decida. A veces, el tamaño del conjunto de datos es una preocupación principal. Ciertamente no siempre.

Independientemente de los datos grandes o no, siempre hay factores constantes que pueden marcar la diferencia entre segundos y horas. Definitivamente te preocupas por ellos.

Lo que generalmente no se enseña en la escuela es cómo encontrar grandes factores de aceleración. Por ejemplo, en programas de software perfectamente bien escritos, las grandes aceleraciones pueden estar al acecho, como en este ejemplo .

La clave para conseguir las aceleraciones es no perderse ninguna . El solo hecho de encontrar algunos, pero no todos, no es lo suficientemente bueno, y la mayoría de las herramientas tienen puntos ciegos enormes . Ese enlace te señala un método que los programadores experimentados han aprendido.

Answer 3

La constante ciertamente importa, y en muchos casos uno puede inclinarse a decir "es lo único que importa" .

Muchas situaciones y problemas hoy en día involucran algo que tiene una latencia extraordinariamente larga: fallas de caché, fallas de páginas, lecturas de discos, paradas de GPU, transferencias DMA. En comparación con estos, a veces no importa en absoluto si tiene que hacer unos pocos miles o unas diez mil iteraciones adicionales.

El poder de ALU ha aumentado de forma sistemática mucho más que el ancho de banda de la memoria (y, lo que es más importante, la latencia), o el acceso a otros dispositivos, como discos, durante las últimas dos décadas. En las GPU, esto es incluso más pronunciado que en las CPU (para cuando DMA y ROP se vuelven 2-3 veces más rápidas, la ALU se ha vuelto 15-20 veces más rápida)

Un algoritmo con complejidad O (log N) (por ejemplo, una búsqueda binaria) que causa un fallo de una sola página puede ser fácilmente varios miles de veces más lento que un algoritmo O (N) (por ejemplo, una búsqueda lineal) que evita este fallo.

Las tablas hash son O (1) pero se ha demostrado repetidamente que son más lentas que otros algoritmos con mayor complejidad. Las listas enlazadas generalmente tienen la misma (o mejor) complejidad algorítmica en comparación con los vectores. Sin embargo, un vector casi siempre superará significativamente a una lista, debido a que las listas hacen más asignaciones y tienen más fallas de caché. A menos que los objetos sean enormes, incluso tener que mover alrededor de unos pocos miles de elementos en un vector para insertar algo en el medio es generalmente más rápido que una asignación de nodo único e inserción en una lista.

El hash de cuco fue famoso hace poco tiempo hace una década porque es O (1) con un máximo garantizado en el peor de los casos (acceso a 2 artículos). Resultó que era muy inferior en la práctica porque tenía dos fallas de caché prácticamente garantizadas en cada acceso.

La iteración de una matriz bidimensional de una manera u otra (filas primero / columnas primero) es exactamente idéntica en complejidad, e incluso en el número de operaciones. Una, sin embargo, tiene una constante que es mil veces más grande y se ejecutará mil veces más lenta.

Answer 4

La constante solo importa si el orden es el mismo , y las operaciones son comparables en complejidad. Si no son del mismo orden, entonces se garantiza que el que tenga el orden superior tardará más tiempo una vez que tenga una n suficientemente grande. A veces, n debe ser más grande que su conjunto de datos típico, y la única forma de elegir el algoritmo más eficiente es hacer una evaluación comparativa.

Answer 5

Sí, podría hacer una diferencia. No revisé tu código para ver si era correcto, pero considera esto:

La primera solución recorre la lista una vez hasta el final y otra vez hasta n. La segunda solución recorre la lista una vez, pero usa ->next() en un segundo puntero n veces. Así que básicamente deberían llamar ->next() aproximadamente la misma cantidad de veces (tal vez + -1 o así).

Independientemente de su ejemplo, no es de eso de lo que se trata la gran notación O. Se trata de dar una aproximación a cómo se escala un algoritmo si la cantidad de datos aumenta. Si tiene un algoritmo O(n) y reduce su tiempo de ejecución en un 10% (independientemente de cómo lo haga), por supuesto que es un beneficio. Pero si duplica los datos, su tiempo de ejecución aún se duplicará, y de eso se trata la notación O(n) . (Un algoritmo O(n^2) , por ejemplo, tendrá su tiempo de ejecución escalado por un factor de 4 si duplica los datos).

Answer 6

Sí. En el ejemplo específico donde ocurre el mismo trabajo, es probable que un solo bucle sea más eficiente que el bucle sobre un conjunto de datos dos veces. Pero la idea de O(2n) ~ O(n) es que 2 ns vs 1 ns realmente no importan. Big O funciona mejor para mostrar cómo se puede escalar un fragmento de código, por ejemplo, si hizo el bucle O(n^2) entonces la diferencia de O(n) frente a O(2n) es mucho menor que O(n) frente a O(n^2) .

Si su lista vinculada contiene terrabytes de datos, entonces podría valer la pena reducirla a la iteración de un solo bucle. Una métrica O grande, en este caso puede no ser suficiente para describir su peor caso; sería mejor que programe el código y considere las necesidades de la aplicación.

Otro ejemplo es el software integrado, donde 1 ms frente a 2 ms podría ser la diferencia entre un lazo de control de 500 Hz y un circuito de control de 1 kHz.

La lección aprendida es que depende de la aplicación.

Answer 7

Si bien en su ejemplo particular, es demasiado cercano para decirlo, ya que las optimizaciones del compilador, el almacenamiento en caché, las tasas de acceso a los datos y muchos otros problemas complican las cosas, para responder a su pregunta del título "Si bien la constante en la notación O grande, ¿importa en la vida real situaciones "es fácil:

Sí.

Imagina que tenemos una función F que consume mucho tiempo y que, para una entrada determinada, siempre produce la misma salida.

Tenemos un bucle que debe ejecutarse N veces. En este bucle, usamos el valor de retorno de F varias veces para calcular algo.

La (s) entrada (s) a F son siempre las mismas para una iteración dada de este bucle.

Tenemos dos posibles implementaciones de este bucle en mente.

1. Implementación # 1:

   loop:
       set inputs to something;
       value = F(inputs);
       do something with value;
       do something else with value;
       do something else else with value;
   done

2. Implementación # 2:

   loop:
       set inputs to something;
       value = F(inputs);
       do something with value;
       value = F(inputs);
       do something else with value;
       value = F(inputs);
       do something else else with value;
   done

Ambas implementaciones se repiten el mismo número de veces. Ambos obtienen el mismo resultado. Obviamente, la implementación # 2 es menos eficiente, ya que hace más trabajo por iteración.

En este ejemplo trivial, el compilador puede notar que F siempre devuelve el mismo valor para la misma entrada, y puede notar que lo llamamos con las mismas entradas cada vez, pero para cualquier compilador, podemos construir un ejemplo que haga el equivalente de O(C*n) vs O(n) donde C realmente importa en la práctica.