Pregunta Cálculo de complejidad de tiempo


Actualmente estoy trabajando en algunas preguntas del examen y me quedé atascado en este punto. Me dieron que un algoritmo de Quicksort tiene una complejidad de tiempo de O(nlog(n)). Para un tamaño de entrada particular, el tiempo para ordenar la lista es de 4 minutos. La pregunta procede a preguntar cuánto tiempo tardará en ordenar una lista del doble del tamaño, en el mismo sistema.

Ya he descartado que el tiempo no es 8 minutos (dos veces el tamaño de entrada = dos veces la duración, razonamiento muy muy equivocado).

Algunos trabajando lo hice:

Trabajando A

  • 4 = nlog(n)
  • 4 = log(n^n)
  • 16 = n^n
  • Básicamente me quedé atrapado en este punto.

Trabajando B

  • X = 2nlog(2n) >> 2n ya que el doble de la entrada
  • X = 2n(1 + log(n))
  • X = 2n + 2nlog(n) >> nlog(n) estaba 4 minutos
  • X = 2n + 2(4) = 2n + 8
  • Una vez más me quedé atascado en este punto.

7
2018-01-31 17:08


origen


Respuestas:


Creo que lo primero que notamos sobre este problema es que, dado que tomó 4 minutos ordenar los números, n debe ser bastante grande Por ejemplo, acabo de utilizar la solución rápida para ordenar mil millones de números en mi computadora, y tardé algo menos de 3 minutos. Asi que n es probablemente de aproximadamente mil millones (dar o tomar un orden de magnitud).

Dado que n es enorme, es razonable aproximar este tiempo de ejecución como c*n*lg(n) por alguna constante c, ya que los términos de orden inferior de la expansión del tiempo de ejecución no deberían ser demasiado relevantes para un tamaño tan grande n. Si duplicamos n, obtenemos el siguiente multiplicador de tiempo de ejecución en comparación con el tiempo de ejecución original:

[Runtime(2n)] / [Runtime(n)]
[c * (2n) * lg(2n)] / [c * n * lg(n)]
2 * lg(2n) / lg(n)
2 * log_n(2n)
2 * (1 + log_n(2))

Aquí, lg() es el logaritmo bajo una base arbitraria y log_n() es la base de registro n.

Primero, ya que asumimos n es grande, una manera posible de proceder sería aproximar log_n(2) como 0, por lo que el multiplicador de tiempo de ejecución se aproximaría a 2 y el tiempo de ejecución total se aproximaría a 8 minutos.

Alternativamente, ya que probablemente sepamos n dentro de un orden de magnitud, otra posibilidad sería aproximar el multiplicador para un valor probable de n:

  • Si n = 100 millones, entonces aproximaríamos el multiplicador a 2.075 y el tiempo de ejecución total a 8.30 minutos.
  • Si n = 1 mil millones, entonces aproximaríamos el multiplicador a 2,067 y el tiempo de ejecución total a 8,27 minutos.
  • Si n = 10 mil millones, entonces aproximaríamos el multiplicador a 2,060 y el tiempo de ejecución total a 8,24 minutos.

Tenga en cuenta aquí que los grandes cambios en nuestra aproximación de n produce cambios bastante pequeños en la aproximación del tiempo de ejecución total.

Vale la pena señalar que, si bien esto se ve bien en el papel, en la práctica las consideraciones arquitectónicas pueden hacer que los tiempos de ejecución de la vida real sean muy diferentes de los que hemos calculado aquí. Por ejemplo, si el algoritmo induce un montón de paginación después de duplicar el tamaño de los datos, el tiempo de ejecución podría ser mucho, mucho mayor que los ~ 8 minutos que hemos aproximado aquí.


6
2018-01-31 19:58



No es posible calcular el tiempo absoluto sin conocer el valor de n.
Toma esto a través de algunos valores empíricos.
Supongamos que 'k' es el tiempo necesario para una sola operación

If, n = 2, k.n.log(n) = 4   => k.2.1 = 4   => k = 2
  if n is doubled, k.2n.log(2n) = 2.4.2 => 16 minutes

If, n = 4, k.n.log(n) = 4   => k.4.2 = 4   => k = 1/2
  if n is doubled, k.2n.log(2n) = 1/2.8.3 => 12 minutes

If, n = 64, k.n.log(n) = 4   => k.64.6 = 4   => k = 1/96
  if n is doubled, k.2n.log(2n) = 1/96.128.7 => 9.33 minutes

Así que a medida que n aumenta, el tiempo necesario se acerca al doble del tiempo (8 minutos)


5
2018-01-31 18:07



La información provista es incompleto.

Prueba: 

Deje que la complejidad algorítmica sea O(nlogn). Esto significa el tiempo tomado, t = c*nlogn.

Por lo tanto, tenemos las siguientes ecuaciones:

  • 4 = c*n*logn 
  • t = c*(n2)*log(n2), dónde t es la respuesta requerida
  • n2 = 2*n2 

Número de variables = 4 (n, n2, t, c)
Cantidad de ecuaciones únicas = 3
Como necesitamos al menos 4 ecuaciones para 4 variables, la información proporcionada es incompleta.


5
2018-01-31 18:13



Esto suena como una pregunta de examen absolutamente terrible, probablemente escrita por alguien que no tiene una comprensión profunda de lo que realmente es la notación Big-O. Hay mucho mal con eso, mucho de lo cual ya se ha abordado en otras respuestas.

El mayor problema es que la notación Big-O no te proporciona ninguna relación directa con el tiempo real. Arroja una gran cantidad de información que se necesitaría para responder la pregunta real que se hace.

Las otras respuestas aquí han señalado que la pregunta no le da ninguna indicación de cuántos elementos había en el conjunto original de entradas, solo que hay dos veces más en el segundo conjunto, y esa información es crítica para dar una respuesta . Pero hay un par de cosas que no mencionaron ...

Primero, Big-O ignora los gastos generales del algoritmo. Podría ser el caso de que el algoritmo utilizado en realidad requiera 3,5 minutos para la configuración, independientemente de la cantidad de entradas que reciba, y que para el conjunto original de entradas, el tiempo de procesamiento real fue de solo unos 30 segundos. Eso va a afectar seriamente el cálculo del tiempo tomado para cualquier cantidad arbitraria de entradas.

Pero por mala que sea esa omisión, Big-O lo lleva aún más lejos.

Mira esta cita de Wikipedia:

En el uso típico, la definición formal de notación O no se usa directamente; más bien, la notación O para una función f se deriva de las siguientes reglas de simplificación:

  • Si f (x) es una suma de varios términos, se conserva el que tiene la mayor tasa de crecimiento, y todos los demás se omiten.
  • Si f (x) es un producto de varios factores, se omiten las constantes (términos del producto que no dependen de x).

Lo que esto significa es que el cálculo del tiempo puede incluir múltiples términos que finalmente se descartan. ¿Qué pasa si el algoritmo toma c * (n + n * log(n)) tiempo para completar, sin gastos generales? En la notación Big-O todavía está O(nlogn).

La única respuesta que es realmente posible para la pregunta del examen es "un tiempo superior a 4 minutos". No podemos saber nada más que eso sin mucha más información. Específicamente:

  • ¿Cuál es el costo?
  • ¿Cuál es el costo de tiempo por operación?
  • ¿De cuántos artículos estamos hablando?
  • ¿Qué otros términos se han eliminado?

2
2018-02-01 00:08



Me gusta el razonamiento de @ Amitoj, pero lo generalizaría.

Dejar n0 = la cantidad de elementos que da como resultado un tiempo de ejecución de 4 minutos, y n1 = 2 * n0. Entonces nosotros tenemos

c = 4 mins / (n0 * log n0)

Estamos tratando de encontrar

t = c * n1 * log n1
  = 4 mins / (n0 * log n0) * n1 * log n1
  = 4 mins * (n1 / n0) * (log n1 / log n0)

n1 / n0 es siempre = 2.

Como n0 => infinito, el límite de log n1 / log n0 va a 1.

Entonces, sí, a medida que n0 se hace más grande, el límite de t es 4 mins * 2 = 8 mins.


1
2018-01-31 20:26



Todas las respuestas, excepto Anmol Singh Jaggi estan equivocados.

En primer lugar, es fácil ver que esta información no es suficiente para obtener una respuesta. Y esta es la razón por la cual:

Todo lo que necesitas hacer es resolver una ecuación. Si la complejidad de tiempo de su algoritmo es O (n logn), entonces la primera ecuación que tiene es:

enter image description here

dónde n en el tamaño de tu lista. Si quieren que encuentres cuánto tiempo tardarás en terminar el algoritmo para un tamaño dos veces mayor, básicamente quieren encontrar x:

enter image description here

Entonces, básicamente, necesitas resolver un sistema de 2 ecuaciones con 3 desconocidas. Esto tiene 0 respuestas (no en nuestro caso) o una cantidad infinita de respuestas.


Ahora debes asumir tu c1. Si c1 = 1, entonces

enter image description here

Sustituyendo n en la segunda ecuación que obtienes: x = 13.5. Así que 13 y medio minuto.


Pero una vez más, en esta respuesta asumimos que c1 es igual a 1, si tienes otro factor constante, obtendrás otra respuesta.


1
2018-01-31 22:38