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

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.

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)?