Justificación para descuidar factores constantes en Big O

20

Muchas veces, si las complejidades tienen constantes como 3n, descuidamos esta constante y decimos O (n) y no O (3n). No puedo entender cómo podemos descuidar un cambio tan triple. ¡Algo varía 3 veces más rápido que otro! ¿Por qué descuidamos este hecho?

complexity-theory asymptotics landau-notation gpuguy
fuente

La semántica de "can" es importante. En la práctica, generalmente no podemos descuidar tales cambios, pero eso (es decir, describir el rendimiento del algoritmo en el mundo real) no es para lo que está hecha la notación de Landau. Formalismos más precisos hacen existir.

Raphael

22

Para racionalizar cómo las notaciones asintóticas ignoran los factores constantes, generalmente pienso en esto: la complejidad asintótica no es para comparar el rendimiento de diferentes algoritmos, es para comprender cómo se escala el rendimiento de los algoritmos individuales con respecto al tamaño de entrada.

Por ejemplo, decimos que una función que toma $3n$ pasos es , porque, en términos generales, para entradas lo suficientemente grandes, duplicar el tamaño de la entrada no será más del doble del número de pasos dados. De manera similar, significa que duplicar el tamaño de entrada cuadruplicará, como máximo, el número de pasos, y significa que duplicar el tamaño de entrada aumentará el número de pasos como máximo de manera constante. $O(n)$ $O(n^2)$ $O(\log n)$

Es una herramienta para decir qué algoritmos escalan mejor, no cuáles son absolutamente más rápidos.

Patrick87
fuente

11

Primero, como ya explicaron otras respuestas, , o para decirlo en palabras, una función es si y solo si es . significa que existe un punto y un factor tal que para todos , $O(3n) = O(n)$ $O(3n)$ $O(n)$ $f = O(3n)$ $N$ $C_3$ $n \ge N$ . Ahora elija : para todos , , entonces . La prueba de lo contrario es similar. $f(n) \le C_3 \cdot 3n$ $C_1 = 3 C_3$ $n \ge N$ $f(n) \le C_1 \cdot n$ $f = O(n)$

Ahora a la razón por la cual esta es la herramienta correcta. Observe que cuando medimos la complejidad de un algoritmo, no damos una unidad. No contamos los segundos, o las instrucciones de la máquina: contamos algunos pasos elementales no especificados que toman un tiempo limitado. Hacemos eso porque ejecutar el mismo algoritmo en una máquina diferente cambiaría el tiempo necesario por instrucción: multiplique la frecuencia del reloj por y el tiempo de ejecución va de a $3$ $f(n)$ $f(n)/3$ . Si implementamos el mismo algoritmo en un idioma diferente, o en un sistema diferente, el tiempo que toma cada paso elemental puede ser diferente, pero nuevamente eso es demasiado detalle: casi nunca nos importan tales diferencias.

Cuando le interesan los tiempos precisos, la complejidad asintótica no es relevante: la complejidad asintótica le dice qué sucede para los tamaños de entrada muy grandes, que pueden ser o no los tamaños de entrada reales con los que está tratando.

Gilles 'SO- deja de ser malvado'
fuente

También tenga en cuenta que Sedgewick en su "Introducción al análisis de algoritmos" aboga por usar o(g)como la medida correcta, es decir, tener

como la forma de describir tiempos de ejecución (aún en términos de operaciones elementales dominantes si lo desea, pero incluyendo el factor constante que molesta a OP).

lim_{n \to \infty} \frac{g (n)}{T (n)} = 1

$\lim_{n \rightarrow \infty} \frac{g(n)}{T(n)} = 1$

vonbrand

2

@vonbrand ¿Sedgewick realmente dice eso? La definición habitual de

es que

(es decir, la fracción al revés y el límite es cero, no unidad).

T (n) \in o (g (n)

$T(n)\in o(g(n)$

lim_{n \to \infty} (T (n) / g (n)) = 0

$\lim_{n\to\infty}(T(n)/g(n))=0$

David Richerby

3

Recordemos la definición de Big-O:

si existe tal que para todo . $f(n)\in O(g(n))$ $c>0$ $f(n)\le cg(n)$ $n$

Bajo esta definición, tenemos que para cada constante . El propósito de la notación es exactamente simplificar las expresiones de esta manera. De hecho, crece 3 veces más rápido que , pero ambos son lineales. Si esto está justificado o no, eso depende del contexto. Pero si acepta utilizar la notación , entonces, por definición, esto es válido. $dn\in O(n)$ $d$ $O$ $3n$ $n$ $O$

Shaull
fuente

2

Esto proporciona una gran explicación de Big-O, pero no explica por qué utilizamos esta definición.

jmite

Como escribí, el propósito es simplificar nuestras vidas. Ya sea porque no sabemos el costo exacto de una operación atómica, o porque nos importa la notación asintótica. No encuentro el POR QUÉ una pregunta matemática interesante, sino más bien filosófica. Podríamos, técnicamente, prescindir de él. Simplemente haría las cosas realmente feas y difíciles de trabajar.

Shaull

3

La notación O grande es un medio libre de unidad para medir la variación del rendimiento, por lo tanto, impermeable a los costos relativos de las primitivas computacionales.

En pocas palabras: la notación Big O es un tipo de medida relativamente libre de unidades (en oposición a la medida absoluta). Solo puede medir la variación del rendimiento, no el rendimiento absoluto, para el cual las constantes son muy importantes. La ventaja es que esto lo hace en gran medida independiente de la implementación, al permitir un análisis más simple que puede ignorar los costos relativos de las operaciones elementales, siempre que estos costos tengan límites superiores e inferiores fijos positivos. Pero la consecuencia es que los factores constantes no tienen sentido . Aún así, incluso para su propósito previsto, el análisis de la complejidad asintótica puede ser cuestionado por otros motivos y debe considerarse con cuidado. Por ejemplo, el tamaño de entrada sin formato puede no ser el parámetro correcto a considerar.

Un primer comentario es que su pregunta no está formulada con precisión. Cuando descuidas la constante en , de hecho hay un "cambio de tres veces", pero ambos varían al mismo ritmo, y no puedes afirmar que "[una] cosa varía 3 veces más rápidamente que la otra". $3$ $3n$

Una buena razón para ignorar la constante en la notación de Landau es que no tenemos una unidad en la que podamos confiar. Cuando alguien dice que A vive dos veces más lejos de ti que B, esto tiene significado independientemente de cualquier unidad. Podemos estar de acuerdo, aunque midas distancias en pulgadas mientras yo lo hago en años luz. Pero la medición de la distancia absoluta requiere unidades específicas, y su formulación numérica depende de la unidad elegida.

El tiempo real que tarda un algoritmo depende del tiempo de ejecución de las operaciones elementales, que depende mucho de la máquina. Puede contar el número de operaciones elementales, pero no hay razón para creer que todas tomen el mismo tiempo, y siempre es posible combinar varias operaciones en una sola, o por el contrario descomponer una operación en operaciones más pequeñas, de modo que el número de operaciones no es realmente significativo, a menos que esté de acuerdo con una máquina virtual de referencia. Ser una referencia independiente es una ventaja.

Otra vista de la ventaja del enfoque es que todo lo que le importa en el análisis es contar el número de operaciones elementales, siempre que su costo tenga un límite superior y un límite inferior positivo. No tiene que preocuparse por el costo individual.

Sin embargo, el precio a pagar por esa ventaja es que la evaluación del costo de cómputo se da con una unidad no especificada, y el tiempo de cómputo, por ejemplo, podría ser nanosegundos o milenios; ni siquiera tratamos de saberlo. En otras palabras, los factores constantes no tienen sentido, ya que cambiar las unidades es inseparable del cambio del factor constante , y no se utilizan unidades de referencia.

Como señaló Patrick87 , esto es suficiente para comprender cómo se escala un algoritmo con respecto al tamaño de entrada, pero no dará una medida absoluta de rendimiento, salvo depender de una unidad de referencia. Se puede deshacer una máquina abstracta de referencia común cuando uno realmente desea comparar el rendimiento de algoritmos distintos, pero es más difícil asegurarse de que la comparación no esté sesgada por los detalles de realización. En la complejidad asintótica, este riesgo se evita porque compara el algoritmo consigo mismo.

De todos modos, solo un programador ingenuo dependería exclusivamente de la complejidad asintótica para elegir un algoritmo. Existen muchos otros criterios, incluida la constante no contada y el costo real de las operaciones elementales. Además, la complejidad del peor de los casos puede ser un indicador deficiente, porque la fuente de la peor complejidad del caso puede ocurrir raramente, y en fragmentos de la entrada lo suficientemente pequeños como para que tenga un impacto limitado. Por ejemplo, los analizadores generales de las gramáticas adyacentes a los árboles tienen una complejidad teórica , y son bastante utilizables en la práctica. El peor caso que conozco es la inferencia de tipo polimórfico Damas-Hindley-Milner $O(n^6)$ algoritmo utilizado para ML, que tiene una complejidad exponencial en el peor de los casos. Pero eso no parece molestar a los usuarios de ML ni evitar la escritura de programas muy grandes en ML. Hay más que la constante que importa. En realidad, el análisis asintótico relaciona una medida del costo de un cálculo con alguna medida de la complejidad de la entrada. Pero el tamaño bruto puede no ser la medida correcta.

La complejidad es como la capacidad de decisión, puede ser teóricamente mala, pero eso puede ser irrelevante para la mayoría del espacio de datos ... a veces. El análisis de complejidad asintótica es una herramienta buena y bien diseñada, con sus ventajas y limitaciones, como todas las herramientas. Con o sin explicitar la constante, que puede no tener sentido, es necesario usar el juicio.

babou
fuente

2

Las otras respuestas proporcionan excelentes explicaciones de por qué, de acuerdo con la definición de Big-O, $O(n)=O(3n)$ .

En cuanto a por qué realmente hacemos esto en CS, es para que tengamos una descripción compacta de la eficiencia de un algoritmo. Por ejemplo, puede haber un algoritmo que tenga una instrucción if, donde una rama ejecuta instrucciones y la otra ejecuta $n$ $3n$ instrucciones. Esto significa que el número exacto cambia para cada entrada, incluso para entradas de la misma longitud. Podríamos encontrar un número para cada entrada, pero el uso de la notación big-O nos da una medida de la complejidad del tiempo que se cumple para TODAS las entradas.

Esto es mucho más útil para adivinar qué tan rápido será un algoritmo. De lo contrario, tendríamos que ver una función masiva por partes, que sería muy difícil de entender.

La otra razón principal es que estas mediciones son independientes del hardware. Los diferentes compiladores y arquitecturas cambiarán el mismo código en conjuntos de instrucciones muy diferentes. Sin embargo, si sabemos que el número de instrucciones es lineal, exponencial, etc., entonces tenemos una idea de la velocidad de los algoritmos que se mantiene, independientemente de la computadora real en la que la compilamos o ejecutamos.

jmite
fuente

1

$f(n)=O(g(n))$ $\limsup\limits_{n\to\infty} \frac{f(n)}{g(n)}<+\infty$ .

$g(n)=n$ $g(n)=3n$ , y viceversa.

$O(n^2)=O(.00005321n^2+1000000000n+10^{46803})$ $f$ $=$

yo'
fuente

2

=

$=$

O (. . .)

$O(...)$ makes sense as set of functions in which case the first should be using

\in

$\in$ , but the second is fine as it means the standard equality of sets.

Jan Hudec

@Jan Yes, but then you ought write

f \in O (g)

$f\in O(g)$ or

f \in O (n \to n^{2})

$f\in O(n\to n^2)$ . It makes senseto write

f^{'} (x) = h (x)

$f'(x)=h(x)$ because you can evaluate the derivative in every

x

$x$ seperately (

x

$x$ can be considered extern to the

=

$=$ sign). But here, you consider the whole function, therefore

n

$n$ is interne to the

=

$=$ /

\in

$\in$ sign.

yo'

Generalmente considero

f (n)

$f(n)$ como ser explícito sobre

f

$f$ siendo función de un argumento.

Jan Hudec

Por lo general, también lo hago, sabiendo que también es un abuso de notación;)

yo'

-1

Let me explain you simply. Let us take n = 100000. Now, what is 3n? It is 300000 (Yeah, it is 3 folds of n) But what is n^2 ? 10000000000. ( it is 1 lakh folds of n)..Compare n^2 with n. 3 is negligible when we compare with 1 lakh. so, we can remove it.

Think if n is some billions or trillions. In this case, again we are going to compare 3 with some billions or trillions. Now, you know why we can neglect 3.

user87002
fuente

2

Three years is still a longer time than one year.

Yuval Filmus

I don't see how this answers the question in any helpful way. It certainly doesn't add anything over the existing, years-old answers.

Raphael

Justificación para descuidar factores constantes en Big O

Respuestas:

La notación O grande es un medio libre de unidad para medir la variación del rendimiento, por lo tanto, impermeable a los costos relativos de las primitivas computacionales.