¿Por qué los informáticos / programadores usan la notación big-O en lugar de la función de tiempo de ejecución real?

Esta es una gran pregunta. En realidad, hay muchas formas diferentes en que el tiempo de ejecución puede ser, y en la práctica, expresado. La tendencia general es que existe una compensación entre la especificidad de la información obtenida del análisis y, por lo tanto, su practicidad inmediata . y cuánto puede generalizar ese resultado a entradas no vistas anteriormente, otros entornos informáticos, etc.

Hagamos un viaje en la escala móvil de lo más específico a lo más general:

Tiempo de ejecución exacto para un conjunto de datos en particular en una máquina en particular. Podríamos describir cuántos segundos tarda el algoritmo en un conjunto de datos específico, ejecutándose en un entorno específico.

Esto se conoce como un punto de referencia.

Pros:

  • El resultado se basa en evidencia experimental. Por lo tanto, no le preocupa que su teoría no tenga en cuenta ciertos efectos (por ejemplo, el almacenamiento en caché).
  • Proporciona comparaciones de manzanas con manzanas cuando necesita comparar dos implementaciones diferentes en el mismo conjunto de datos con todos los diferentes factores de hardware / software tomados en cuenta.

Contras:

  • Resultado específico del hardware / entorno.
  • No sé cómo se escalará su algoritmo.
  • No sé cómo su algoritmo depende del contenido de los datos.

Estudio empírico de tiempos de ejecución en diferentes tamaños de entrada y conjuntos de datos. Podemos probar muchos conjuntos de datos de diferentes tamaños, obtener una distribución y usar esto para predecir los tiempos de ejecución.

Esto se hace, hasta cierto punto, en pruebas de rendimiento.

Mejor que el enfoque anterior porque:

  • Al medir en una amplia gama de entradas, el modelo tiene cierto poder predictivo para nuevas entradas nunca antes vistas.
  • Da evidencia empírica de cómo el algoritmo escala con el tamaño de entrada y varía dentro del mismo tamaño de entrada.

Peor que el enfoque anterior porque:

  • No le proporciona un número exacto de cuánto tiempo llevará ese conjunto de datos específico que desea ejecutar .

Un recuento total de operaciones realizadas, ponderadas por su costo relativo (por ejemplo, la adición es más barata que la división) en la arquitectura en cuestión.

Mejor que el enfoque anterior porque:

  • Da una fórmula matemática para el tiempo de ejecución. La fórmula debe revelar el big-O junto con el tamaño de los factores constantes involucrados, así como términos significativos de orden inferior.
  • No se basa en evidencia empírica, por lo tanto, puede dar estimaciones significativas del peor de los casos. A partir del análisis del algoritmo se encontrarán entradas degeneradas que pueden no probarse, o que ocurren raramente en la práctica.

Peor que el enfoque anterior porque:

  • Si el costo relativo de las operaciones se estima incorrectamente, proporcionará predicciones incorrectas.
  • Es difícil tener en cuenta todos los efectos (por ejemplo, almacenamiento en caché, predicción de ramificación) en el modelo de cuánto costará cada operación.
  • No se basa en evidencia empírica.

Recuentos de cuántas de cada operación realizada. Cuántas adiciones, multiplicaciones, etc.

Vemos esto en las discusiones de varios algoritmos en forma de enunciados como “Multiplicar una matriz 4 × 4 toma X adiciones y multiplicaciones Y para completar, mientras que usar cuaterniones en su lugar toma W adiciones y multiplicaciones Z”.

Mejor que el enfoque anterior porque:

  • Algo independiente de la arquitectura de la computadora. Solo un poco, porque aún pueden ser interacciones difíciles de predecir, como los efectos del procesamiento superescalar, los riesgos de los datos, etc. Tampoco son totalmente independientes del compilador, ya que el compilador optimizará / reescribirá algunas de las instrucciones.

Peor que el enfoque anterior porque:

  • Para comprender el tiempo de ejecución real, debe comprender qué tan lenta / rápida será cada operación en la arquitectura en cuestión.

Big-O

Un recuento total de operaciones realizadas, pero muestra solo el término de orden más alto y sin el factor constante.

Se utiliza en el análisis abstracto de algoritmos, donde necesitamos un modelo de cómputo en gran parte independiente de la arquitectura de la computadora, suponiendo una máquina clásica de acceso aleatorio de un solo subproceso.

Mejor que el enfoque anterior porque:

  • Independiente de la arquitectura de la computadora dentro de ciertos supuestos razonables.
  • Mayormente independiente del compilador.
  • Información fácil de digerir.

Peor que el enfoque anterior porque:

  • No revela los factores constantes involucrados con el algoritmo.
  • Es difícil comparar dos algoritmos que tienen el mismo big-O.

Puede pensar que este es el final de la línea, pero podemos seguir generalizando los resultados, a costa de hacerlos cada vez menos prácticos de inmediato.

Clasificación amplia según clases de complejidad.

Podemos preguntar si el algoritmo se ejecuta en tiempo polinómico, tiempo exponencial, etc.

Mejor que el enfoque anterior porque:

  • Debe ser independiente del compilador
  • Principalmente independiente del modelo de computación clásica (por ejemplo, máquina de Turing vs. máquina de acceso aleatorio). Cosas importantes como permitir la aleatorización, el paralelismo o la computación cuántica aún pueden cambiar la imagen.

Peor que el enfoque anterior porque:

  • Revela muy poca información práctica en términos de cuánto tiempo llevará ejecutar el programa.

Decidability

Podemos preguntar si la tarea en cuestión es incluso posible para un algoritmo. *

Mejor que el enfoque anterior porque:

  • Casi completamente independiente del modelo de computación, incluso para computadoras no clásicas.

Peor que el enfoque anterior porque:

  • Literalmente no revela nada, excepto si la tarea puede lograrse incluso mediante un algoritmo.

* Nota: entiendo que hay una distinción entre un problema y un algoritmo. La comparación no es perfecta aquí.

En general, es útil comprender la escalabilidad de un algoritmo.

O (1) significa que siempre costará lo mismo
O (n) significa que siempre habrá una cantidad incremental consistente de potencia de procesamiento para cada elemento nuevo
O ([matemática] n ^ 2 [/ matemática]) significa que los nuevos elementos siempre costarán cada vez más.

De una manera más tangible, le permite comprender el impacto de grandes conjuntos de datos en su algoritmo. Para una gran cantidad de código (paso único, lógica de decisión) muchas veces, todos los valores bajos de n son en su mayoría iguales. Cuando agregue un “para”, “mientras” o “hacer”, debe comprender la gran O para el algoritmo.

Usando su ejemplo, puede saber intuitivamente que en algún nivel de elementos para ordenar con clasificación de burbujas, el algoritmo se vuelve inútil. Eso te da una restricción sobre dónde puedes usarlo. PERO dependiendo de su contexto, Big-O puede ser irrelevante si el código circundante eclipsa el código que está agregando.

Por ejemplo, el uso de la clasificación de burbujas para ordenar los nombres de usuario por fuerza bruta, descifrar una contraseña hace que la Gran O de la clasificación de burbujas sea irrelevante. La elección de la clasificación del nombre de usuario debe estar limitada por la conveniencia (de una biblioteca o código preexistente) y la facilidad de mantenimiento (no traiga una biblioteca de clasificación súper rápida solo para ordenar la lista de nombres de usuario).

1) Normalmente debe analizar su algoritmo con mucho cuidado (como en la forma en que lo tiene a la derecha), luego determinar sus asintóticos si no está seguro. No estoy seguro si está entendiendo lo que la gente normalmente considera un análisis exacto. Lo que obtienes de este último no tiene constantes para cada operación (por ejemplo, c_1 es para la operación de suma, c_2 es ​​para un intercambio, etc.).

2) Notará que el análisis exacto agrega poco o nada a la discusión la mayor parte del tiempo lo bueno que es un algoritmo depende de la función de crecimiento con respecto al tamaño de entrada. Los tiempos que tarda la máquina son constantes. Estas constantes no agregan mucho a la discusión cuando comparamos algoritmos. Un análisis exacto directo es útil cuando 2 algoritmos tienen el mismo orden asintótico en máquinas muy particulares. También vale la pena señalar que su segundo valor allí en realidad no es lo que creo que tendría un análisis exacto. ¿Dónde están las constantes de cuánto tiempo ocurren realmente las líneas (para que puedas conectarlas)? Tenga en cuenta que lo último que tiene allí es lo que haría en el análisis asintótico de todos modos, ya que está determinando con respecto al tamaño de entrada el número de pasos que utilizan el modelo RAM (suponiendo que algunas operaciones tomen O (1) tiempo).

3) El análisis exacto no contradice el análisis asintótico. Todo lo que obtenga del análisis exacto coincidirá con el análisis asintótico en términos de su orden.

De hecho, aconsejaría a los programadores (especialmente a los informáticos) que no usen la notación Big-Oh, sino la notación Big-Theta. Mucho más apretado. Aunque vale la pena señalar que la mayoría trabaja con la notación Big-Theta, pero escribe sus tiempos de ejecución en términos de Big-Oh.

En general, la complejidad big-O de un algoritmo o función es más fácil de entender que el tiempo de ejecución preciso. Si no necesita la precisión adicional, ¿por qué molestarse en hacer el trabajo para obtenerla?

La notación Big O (junto con Big-Theta y Big-Omega) son una forma abreviada conveniente para definir clases de problemas. La idea es tener alguna intuición sobre el tiempo de ejecución del programa para poder compararlos, por ejemplo, mergesort en O (nlogn) es mucho más rápido que el tipo de burbuja en O (n ^ 2). Si su objetivo es obtener el mejor algoritmo posible para su aplicación, necesita saber el tiempo de ejecución exacto, pero si solo está tratando de obtener una comprensión general del algoritmo, bigO es suficiente y más generalizable.

Las funciones de tiempo de ejecución reales proporcionan más información que la requerida para el análisis de tiempo de ejecución. En la mayoría de los casos, solo estamos interesados ​​en el ANÁLISIS DEL PEOR CASO. Mientras hacemos el análisis en tiempo de ejecución de un algoritmo, estamos interesados ​​en seguir la información.
1. Obtener un límite superior apropiado en tiempo de ejecución en el peor de los casos.
2. Obtener información sobre el orden / tasa de crecimiento del tiempo de ejecución T (n) de un
algoritmo, con crecimiento en la entrada (n), es decir, eficiencia del algoritmo para
entradas grandes
Para hacer esto, no necesitamos considerar términos y constantes de orden inferior

¿Por qué podemos ignorar los términos de orden inferior?
Los términos de orden inferior se ignoran porque para valores grandes de n, los de orden inferior son relativamente insignificantes.
Por ejemplo si [math] n = 100000000 [/ math],
entonces puedes ver eso
[matemática] n [/ matemática] es relativamente insignificante para [matemática] n ^ 2 [/ matemática]
De manera similar, [matemáticas] n ^ 2 [/ matemáticas] es relativamente insignificante para [matemáticas] n ^ 3 [/ matemáticas]

Las constantes involucradas (como 1/2 en este caso) dependen de los costos del estado de cuenta que (que varían de una máquina a otra, supongo).

ACTUALIZAR:
El objetivo principal del análisis de complejidad es obtener un límite superior del tiempo de ejecución (en la mayoría de las situaciones nos interesa el peor tiempo de ejecución), que está suficientemente dado por el término de orden más alto que también sin constante

Considerar

Código 1

  int i = 0, n = 1000000, x = 0, y = 0;
  para (i = 0; i 

Código 2

  int i = 0, n = 1000000, x = 0, y = 0;
  para (i = 0; i 

Entonces, aproximadamente el tiempo de ejecución de Code1 es [math] n ^ 2 + n [/ math]
y el tiempo de ejecución de Code2 es [matemática] n ^ 2 + 5n [/ matemática]

Considere un sistema que realiza [matemáticas] 10 ^ 8 [/ matemáticas] operaciones por segundo
entonces el código 1 será [matemático] 10 ^ 4 + 0.01 [/ matemático] segundos
y el Código 2 tomará [matemáticas] 10 ^ 4 + 0.05 [/ matemáticas] segundos
(Espero que mis matemáticas sean correctas 🙂)

Entonces podemos decir que el tiempo de ejecución de ambos códigos es [matemático] O (n ^ 2) [/ matemático]
O ambos códigos tomarán alrededor de [matemática] 10 ^ 4 [/ matemática] segundos

¿Por qué podemos ignorar las constantes del término de orden superior?

Ignoramos el coeficiente constante del término principal, ya que los factores constantes son menos significativos que la tasa de crecimiento para determinar la eficiencia computacional para entradas grandes
-Introducción a los Algoritmos 2da Ed, sección 2.2

Considere tres algoritmos que resuelven el mismo problema A1, A2, A3
Después de descuidar los términos de menor orden tenemos
[matemáticas] T (n) _ {A1} = x ^ 3 [/ matemáticas] [verde]
[matemáticas] T (n) _ {A2} = 5 * (x ^ 3) [/ matemáticas] [rojo]
[matemáticas] T (n) _ {A3} = 17 * (x ^ 3) [/ matemáticas] [azul]


La diferencia en la tasa de crecimiento de estas tres funciones no es significativa
para n grande (su función de tiempo de ejecución de A3 alcanzará el infinito 17 veces más rápido que A1)

Entonces podemos representar todas las funciones de tipo [math] c * (n ^ 3) [/ math] con un mismo conjunto [math] O (n ^ 3) [/ math].

Por último, no debemos olvidar que la notación Big O no proporciona un tiempo de ejecución exacto de la función. Es una forma de asignar una función para establecer / clase.
Cuando decimos [matemáticas] T (5 * n ^ 2) = O (n ^ 2) [/ matemáticas], en realidad queremos decir [matemáticas] T (5 * n ^ 2) \ en O (n ^ 2) [/ matemáticas], porque satisface la propiedad

[matemáticas] 0 \ leq 5 * n ^ 2 \ leq c * n ^ 2 [/ matemáticas] para algunas c positivas
y [math] \ forall n> n_0 [/ math]
Y utilizamos la notación Big O porque proporciona la información necesaria para el análisis en tiempo de ejecución.

Algunas razones por las que siento que la notación O grande se utiliza como punto de referencia principal para evaluar algoritmos basados ​​en la complejidad del tiempo y el espacio son:

  1. Simplicidad: determinar la complejidad exacta hasta la precisión de determinar los coeficientes exactos de los términos individuales en la función de crecimiento sería trivial y no alteraría los tiempos de ejecución en el orden de potencias de 10s y, por lo tanto, determinarlo se vuelve trivial. Sin mencionar los coeficientes, pero incluso el crecimiento de términos de menor orden no afecta la función de crecimiento esta vez, independientemente del tamaño de entrada. Por ejemplo, intentemos comprender con la ayuda de un ejemplo:
  1. [matemática] T (n) = 4n ^ 2 + 4n + 1 [/ matemática] donde n es el tamaño de la entrada. Para nuestro entendimiento, n sea igual a 1276540. Sustituyendo en [matemática] T (n) [/ matemática] como [matemática] T (1276540) = 6.518 * 10 ^ {12} [/ matemática] y sustituyendo el mismo valor por [matemática] n [/ math] en la ecuación [math] 4n ^ 2 [/ math] me daría lo mismo.
  • Factores independientes del algoritmo: existen dependencias externas para calcular las funciones de crecimiento de tiempo, como el procesador utilizado, el sistema operativo, el compilador, etc. Por ejemplo, las operaciones basadas en matrices se pueden acelerar mediante la paralelización en las GPU. Lea https://graphics.stanford.edu/pa
  • Algoritmos de clasificación: en esencia, la notación O grande es como un método para clasificar fácilmente los algoritmos y, en adelante, ayuda a eliminar los menos eficientes y, a veces, determinar una función de crecimiento exacta requiere un cierto fondo matemático.
    1. Por ejemplo, para calcular la complejidad temporal de la determinación de [math] i ^ {th} [/ math] Fibonacci no., Que es un problema de recurrencia con las siguientes condiciones iniciales: [math] F_0 = 0 [/ math ], [matemáticas] F_1 = 1 \ & F_n = F_ {n-1} + F_ {n-2} [/ matemáticas]. La intuición simple sugeriría que al construir un árbol de recursión para el problema, podemos descubrir que asintóticamente este problema tendría una complejidad temporal de [matemáticas] O (2 ^ n) [/ matemáticas] mientras que para determinar la función de crecimiento exacta requerimos el uso de funciones generadoras que, aunque simples, requerirían más tiempo que la intuición. Lea https://www.math.cmu.edu/~af1p/T

    Considere que está ejecutando 2 algoritmos, digamos A y B, con el mismo propósito. Deje que A termine la tarea en tiempo TA (n) y B la termine en tiempo TB (n), donde n es el tamaño de entrada. Para demostrar que el algoritmo A es mejor que B, debemos demostrar que
    TA (n)

    Podemos determinar sus tiempos de ejecución para un tamaño de entrada n0, y si vemos que TA (n0) 0, podemos ver que el algoritmo A es realmente más rápido que el algoritmo B, independientemente del tamaño de entrada. Pero no tenemos idea del tamaño de entrada, y una función no siempre es menor o igual que otra función en todo el conjunto de tamaños de entrada. Aquí es donde el análisis asintótico nos ayuda.

    El análisis asintótico elimina todas las dependencias como hardware, sistema operativo, compilador y varios otros factores, y nos da una relación puramente en el tamaño de entrada n. Hay varias clases de asintóticas, como la gran O, la gran theta, la gran Omega, la pequeña O y la pequeña Omega. Cada uno de estos puede usarse para calcular una relación entre el tiempo de ejecución de un algoritmo (para la complejidad del tiempo) con su tamaño de entrada n. Todos los demás factores son ignorados.

    Dependerá de su implementación y de dónde esté ejecutando el código. Entonces, [matemáticas] n * (n + 1) / 2 [/ matemáticas] también está mal.

    Siempre hay algunas constantes asociadas. Si se pregunta si deberíamos escribir [matemáticas] O (n * (n + 1) / 2) [/ matemáticas] en lugar de [matemáticas] O (n ^ 2) [/ matemáticas], recuerde que
    [matemática] O ((n ^ 2) / 2 + n / 2) [/ matemática] es lo mismo que [matemática] O (n ^ 2) [/ matemática]. Es decir, [matemáticas] O ((n ^ 2) / 2 + n / 2) == O (n ^ 2) [/ matemáticas] es cierto.

    Porque cuando n es grande (teóricamente hablando, cuando n -> ~), el orden inferior es solo una molestia.

    Recuerda las matemáticas de la secundaria
    {Límite n -> ~} (n ^ 2 + n + 1) / n ^ 2 = 1

    Eso es solo un ejemplo de cómo el orden inferior es una molestia cuando n es grande

    Pero cuando n es pequeño, ¿por qué necesita preocuparse por la eficiencia del algoritmo en primer lugar (aparte de apaciguar a los molestos jefes y compañeros de equipo)?