cheat - python sorted complexity
Tiempo lineal vs tiempo cuadrático (4)
A menudo, algunas de las respuestas mencionan que una solución dada es lineal , o que otra es cuadrática .
¿Cómo marcar la diferencia / identificar qué es qué?
¿Alguien puede explicar esto, de la manera más fácil posible, para los que, como yo, que todavía no saben?
Deben estar refiriéndose a la complejidad en tiempo de ejecución también conocida como notación Big O. Este es un tema extremadamente grande para abordar. Comenzaría con el artículo en wikipedia: https://en.wikipedia.org/wiki/Big_O_notation
Cuando estaba investigando este tema, una de las cosas que aprendí a hacer es graficar el tiempo de ejecución de mi algoritmo con diferentes conjuntos de datos de tamaño. Cuando grafiques los resultados, notarás que la línea o curva se puede clasificar en uno de varios órdenes de crecimiento.
Comprender cómo clasificar la complejidad del tiempo de ejecución de un algoritmo le dará un marco para comprender cómo se escalará su algoritmo en términos de tiempo o memoria. Le dará la posibilidad de comparar y clasificar los algoritmos de forma flexible entre sí.
No soy un experto, pero esto me ayudó a comenzar por el agujero del conejo.
Aquí hay algunos órdenes típicos de crecimiento:
- O (1) - tiempo constante
- O (log n) - logarítmica
- O (n) - tiempo lineal
- O (n ^ 2) - cuadrático
- O (2 ^ n) - exponencial
- O (n!) - factorial
Si el artículo de wikipedia es difícil de tragar, recomiendo encarecidamente ver algunas conferencias sobre el tema en la Universidad de iTunes y examinar los temas del análisis de algoritmos, la notación de grandes O, las estructuras de datos e incluso el recuento de operaciones.
¡Buena suerte!
No especifica, pero al mencionar una solución , es posible que esté preguntando acerca de la convergencia cuadrática y lineal. Para este fin, si tiene un algoritmo que es iterativo y genera una secuencia de aproximaciones a un valor convergente, entonces tiene una convergencia cuadrática cuando puede mostrar que
x(n) <= c * x(n-1)^2
para alguna constante positiva c . Es decir, el error en la solución en la iteración n+1 es menor que el cuadrado del error en la iteración n . Vea esto para una introducción más completa para definiciones más generales de tasa de convergencia http://en.wikipedia.org/wiki/Rate_of_convergence
Por lo general, discute sobre un algoritmo en términos de su tamaño de entrada n (si la entrada es una matriz o una lista). Una solución lineal a un problema sería un algoritmo cuyo tiempo de ejecución se escala linealmente con n , por lo que x*n + y , donde x e y son números reales. n aparece con un máximo exponente de 1: n = n^1 .
Con una solución cuadrática, n aparece en un término con 2 como el exponente más alto, por ejemplo, x*n^2 + y*n + z .
Para n arbitraria, la solución lineal crece en tiempo de ejecución mucho más lento que la cuadrática.
Para más información, busque https://en.wikipedia.org/wiki/Big_O_notation .
Un método es lineal cuando el tiempo que toma aumenta linealmente con el número de elementos involucrados. Por ejemplo, un bucle for que imprime los elementos de una matriz es aproximadamente lineal:
for x in range(10):
print x
porque si imprimimos el rango (100) en lugar del rango (10), el tiempo de ejecución es 10 veces mayor. Verá muy a menudo eso escrito como O (N), lo que significa que el tiempo o el esfuerzo computacional para ejecutar el algoritmo es proporcional a N.
Ahora, digamos que queremos imprimir los elementos de dos para bucles:
for x in range(10):
for y in range(10):
print x, y
Por cada x, voy 10 veces y en bucle. Por este motivo, todo el proceso pasa por impresiones 10x10 = 100 (puede verlas simplemente ejecutando el código). Si en lugar de usar 10, uso 100, ahora el método hará 100x100 = 10000. En otras palabras, el método es O (N * N) u O (N²), ya que cada vez que aumenta el número de elementos, el esfuerzo o tiempo de cálculo aumentará como el cuadrado del número de puntos.