algorithm - rapper - O(n log n) vs O(n): diferencias prácticas en la complejidad del tiempo
big o notation java (5)
n log n > n - pero esto es como una relación pseudo-linear . Si n=1 billion , log n ~ 30;
entonces n log n será 30 billion , que es 30 X n , orden de n . Me pregunto si esta diferencia de complejidad de tiempo entre n log n and n es significativa en la vida real.
Por ejemplo: una quick select para encontrar el elemento kth en una matriz sin clasificar es O(n) usando el algoritmo de selección rápida.
Si ordeno la matriz y encuentro el elemento kth, es O(n log n) . Para ordenar una matriz con 1 trillion elementos, seré 60 times más lento si lo hago quicksort y lo quicksort . A mí me parece que no es una gran diferencia, pero necesito la opinión de expertos aquí.
Darth Vader tiene razón. Siempre depende. También es importante recordar que las complejidades son asintóticas, el peor de los casos (generalmente) y que las constantes se eliminan. Cada uno de estos es importante tener en cuenta.
Entonces, podría tener dos algoritmos, uno de los cuales es O (n) y uno de los cuales es O (nlogn), y por cada valor hasta el número de átomos en el universo y más allá (hasta un valor finito de n), El algoritmo O (nlogn) supera al algoritmo O (n). Podría deberse a que dominan los términos de orden inferior, o podría deberse a que en el caso promedio, el algoritmo O (nlogn) es en realidad O (n), o porque el número real de pasos es algo así como 5,000,000n versus 3nlogn.
Depende.
Estaba trabajando en Amazon, había un método, que era hacer una búsqueda lineal en una lista. Podríamos usar una Hashtable y buscar en O (1) en comparación con O (n).
Sugerí el cambio, y no fue aprobado. Debido a que la entrada era pequeña, realmente no haría una gran diferencia.
Sin embargo, si la entrada es grande, entonces haría una diferencia.
En otra compañía, donde los datos / entradas eran enormes, el uso de un árbol, comparado con la lista, marcó una gran diferencia. Así que depende de los datos y la arquitectura de la aplicación.
Siempre es bueno conocer sus opciones y cómo puede optimizar.
El propósito principal de la notación Big-O es permitirte realizar estimaciones como las que hiciste en tu publicación, y decidir por ti mismo si dedicar tu esfuerzo a codificar un algoritmo generalmente más avanzado vale la pena por los ciclos de CPU adicionales que vas a utilizar. Compra con ese código de mejora. Dependiendo de las circunstancias, puede obtener una respuesta diferente, incluso cuando su conjunto de datos es relativamente pequeño:
- Si está ejecutando en un dispositivo móvil, y el algoritmo representa una parte significativa del tiempo de ejecución, reducir el uso de la CPU se traduce en extender la vida útil de la batería.
- Si se ejecuta en un entorno competitivo de todo o nada, como un sistema de comercio de alta frecuencia, una microoptimización puede diferenciar entre ganar dinero y perder dinero.
- Cuando su perfil muestra que el algoritmo en cuestión domina el tiempo de ejecución en un entorno de servidor, el cambio a un algoritmo más rápido puede mejorar el rendimiento de todos sus clientes.
Otra cosa que oculta la notación Big-O es el factor de multiplicación constante. Por ejemplo, Quick Select tiene un multiplicador muy razonable, lo que hace que el ahorro de tiempo al emplearlo en conjuntos de datos extremadamente grandes valga la pena el problema de implementarlo.
Otra cosa que debes tener en cuenta es la complejidad del espacio. Muy a menudo, los algoritmos con complejidad de tiempo O(N*Log N) tendrían una complejidad de espacio O(Log N) . Esto puede presentar un problema para conjuntos de datos extremadamente grandes, por ejemplo, cuando una función recursiva se ejecuta en un sistema con una capacidad de pila limitada.
Hay ocasiones en las que trabajará con miles de millones de elementos (y más), donde la diferencia será sin duda significativa.
Hay otras ocasiones en las que trabajará con menos de mil elementos, en cuyo caso la diferencia probablemente no será tan significativa.
Si tiene una idea decente de cómo se verán sus datos, debe tener una idea decente de cuál elegir desde el principio, pero la diferencia entre O (n) y O (n log n) es lo suficientemente pequeña como para que sea mejor Comience con el que sea más simple, evalúelo y solo intente mejorarlo si ve que es demasiado lento.
Sin embargo, tenga en cuenta que O (n) en realidad puede ser más lento que O (n log n) para cualquier valor dado de n (especialmente, pero no necesariamente, para valores pequeños de n) debido a los factores constantes involucrados, ya que big-O ignora esos (solo considera lo que sucede cuando n tiende a infinito), por lo tanto, si está considerando únicamente la complejidad del tiempo, lo que cree que puede ser una mejora, en realidad puede ralentizar las cosas.
PriorityQueue Ordena cada elemento que agrega cada vez que usa Collections.sort () ordenará todos los elementos de una sola vez. Pero si tiene un problema en el que desea obtener el elemento más grande lo antes posible, use PriorityQueue por otra parte si necesita realizar algunos cálculos pero requiere que el elemento se clasifique y luego usar ArrayList with Collections. Lo mejor es ordenar