sheet problems examples data complexity cheat big asymptotic algorithm complexity-theory

algorithm - problems - big-o notation java



Big-oh vs big-theta (8)

Posible duplicado:
¿Cuál es la diferencia entre Θ (n) y O (n)?

Me parece que cuando las personas hablan informalmente de la complejidad de los algoritmos, hablan sobre big-oh. Pero en situaciones formales, a menudo veo a big-theta con el ocasional big-oh arrojado. Sé matemáticamente cuál es la diferencia entre los dos, pero en inglés, en qué situación sería usar big-oh cuando te refieres a big-theta be incorrecto, o viceversa (un algoritmo de ejemplo sería apreciado)

Bono: ¿por qué las personas aparentemente siempre usan big-oh cuando hablan informalmente?

Bono: ¿por qué las personas aparentemente siempre usan big-oh cuando hablan informalmente?

Porque en grande-oh, este ciclo:

for i = 1 to n do something in O(1) that doesn''t change n and i and isn''t a jump

es O(n), O(n^2), O(n^3), O(n^1423424) . big-oh es solo un límite superior, lo que hace que sea más fácil de calcular porque no tiene que encontrar un límite apretado.

Sin embargo, el ciclo anterior es solo big-theta(n) .

¿Cuál es la complejidad del tamiz de eratosthenes ? Si dijeras O(n log n) , no estarías equivocado, pero tampoco sería la mejor respuesta. Si dijeras big-theta(n log n) , estarías equivocado.

Aquí hay muchas buenas respuestas, pero noté que faltaba algo. La mayoría de las respuestas parecen implicar que la razón por la cual las personas usan Big O sobre Big Theta es un problema de dificultad, y en algunos casos esto puede ser cierto. A menudo, una prueba que conduce a un resultado Big Theta es mucho más complicado que uno que da como resultado Big O. Por lo general, esto es cierto, pero no creo que esto tenga una gran relación con el uso de un análisis sobre el otro.

Cuando hablamos de complejidad podemos decir muchas cosas. La gran complejidad del tiempo O simplemente nos dice qué algoritmo se garantiza que se ejecute dentro, un límite superior. Big Omega se discute con mucha menos frecuencia y nos dice el tiempo mínimo que se garantiza que un algoritmo se ejecute, un límite inferior. Ahora, Big Theta nos dice que ambos números son, de hecho, los mismos para un análisis dado. Esto nos dice que la aplicación tiene un tiempo de ejecución muy estricto, que solo puede desviarse por un valor asintóticamente menor que nuestra complejidad. Muchos algoritmos simplemente no tienen límites superiores e inferiores que sean asintóticamente equivalentes.

En cuanto a su pregunta usando Big O en lugar de Big Theta, técnicamente siempre sería válida, mientras que usar Big Theta en lugar de Big O solo sería válido cuando Big O y Big Omega fueran iguales. Por ejemplo, sorting de inserción tiene una complejidad de tiempo de Big О at n ^ 2, pero su mejor escenario pone su Big Omega en n. En este caso, no sería correcto decir que su complejidad de tiempo es Big Theta de n o n ^ 2 ya que son dos límites diferentes y deben tratarse como tales.

Big-O es un límite superior.

Big-Theta es un límite apretado, es decir, límite superior e inferior.

Cuando las personas solo se preocupan por qué es lo peor que puede pasar, Big-O es suficiente; es decir, dice que "no puede ser mucho peor que esto". Cuanto más estricto sea el límite, mejor, por supuesto, pero un límite apretado no siempre es fácil de calcular.

Ver también

Preguntas relacionadas

La siguiente cita de Wikipedia también arroja algo de luz:

Informalmente, especialmente en ciencias de la computación, a menudo se permite abusar de la notación Big O para describir un límite apretado asintótico donde el uso de la notación Big Theta podría ser más apropiado en un contexto dado.

Por ejemplo, cuando se considera una función T(n) = 73n 3 + 22n 2 + 58 , todos los siguientes son generalmente aceptables, pero la rigidez del límite (es decir, las viñetas 2 y 3 a continuación) suele ser muy preferible a la laxitud del límite ( es decir, viñeta 1 a continuación).

  1. T(n) = O(n 100 ) , que es idéntico a T(n) ∈ O(n 100 )
  2. T(n) = O(n 3 ) , que es idéntico a T(n) ∈ O(n 3 )
  3. T(n) = Θ(n 3 ) , que es idéntico a T(n) ∈ Θ(n 3 )

Las declaraciones equivalentes en inglés son, respectivamente:

  1. T(n) crece asintóticamente no más rápido que n 100
  2. T(n) crece asintóticamente no más rápido que n 3
  3. T(n) crece asintóticamente tan rápido como n 3 .

Entonces, aunque las tres afirmaciones son verdaderas, cada vez más información está contenida en cada una. En algunos campos, sin embargo, la notación Big O (viñetas número 2 en las listas anteriores) se usaría más comúnmente que la notación Big Theta (viñetas número 3 en las listas anteriores) porque las funciones que crecen más lentamente son más deseables.

He visto a Big Theta, y estoy bastante seguro de que me enseñaron la diferencia en la escuela. Aunque tuve que buscarlo. Esto es lo que dice Wikipedia:

Big O es la notación asintótica más comúnmente utilizada para comparar funciones, aunque en muchos casos Big O puede ser reemplazado por Big Theta Θ para límites más estrictos.

Fuente: Notación Big O # Notación asintótica relacionada

No sé por qué las personas usan Big-O cuando hablan formalmente. Tal vez es porque la mayoría de la gente está más familiarizada con Big-O que con Big-Theta. Había olvidado que Big-Theta incluso existía hasta que me lo recordaras. Aunque ahora que mi memoria se actualiza, puedo terminar utilizándola en una conversación. :)

Porque hay algoritmos cuyo mejor caso es rápido, y por lo tanto es técnicamente una gran O, no una gran Theta.

Big O es un límite superior , el gran Theta es una relación de equivalencia .

Porque mi teclado tiene una tecla O
No tiene una tecla Θ o Ω.

Sospecho que la mayoría de las personas son igualmente perezosas y usan O cuando significan Θ porque es más fácil escribir.

Soy matemático y he visto y necesitado una gran cantidad de O, gran Theta y Omega grande una y otra vez, y no solo por la complejidad de los algoritmos. Como decía la gente, Big-Theta tiene un límite de dos lados. Estrictamente hablando, debe usarlo cuando quiera explicar que eso es lo que puede hacer un algoritmo y que ese algoritmo no puede hacerlo mejor o que ningún algoritmo puede hacerlo mejor. Por ejemplo, si dices "La ordenación requiere comparaciones Θ (n (log n)) para la entrada al peor de los casos", entonces estás explicando que hay un algoritmo de clasificación que usa comparaciones O (n (log n)) para cualquier entrada ; y que para cada algoritmo de clasificación, hay una entrada que lo obliga a hacer comparaciones Ω (n (log n)).

Ahora bien, una pequeña razón por la que las personas usan O en lugar de Ω es para eliminar las renuncias sobre casos peores o promedio. Si dices "ordenar requiere comparaciones O (n (log n))", la afirmación sigue siendo cierta para una entrada favorable. Otra razón estrecha es que incluso si un algoritmo para hacer X toma tiempo Θ (f (n)), otro algoritmo podría funcionar mejor, por lo que solo puede decir que la complejidad de X es O (f (n)).

Sin embargo, hay una razón más amplia por la que las personas usan O de manera informal. A nivel humano, es un dolor hacer siempre declaraciones de dos caras cuando el lado inverso es "obvio" desde el contexto. Como soy matemático, lo ideal sería siempre tener cuidado de decir "tomaré un paraguas si y solo si llueve" o "puedo hacer malabares con 4 bolas pero no con 5", en lugar de "tomaré un paraguas si llueve "o" puedo hacer malabarismos con 4 bolas ". Pero las otras mitades de tales declaraciones a menudo son obviamente intencionales o obviamente no intencionales. La naturaleza humana es descuidada por lo obvio. Es confuso dividir los pelos.

Desafortunadamente, en un área rigurosa como las matemáticas o la teoría de algoritmos, también es confuso no dividir los pelos. La gente inevitablemente dirá O cuando deberían haber dicho Ω o Θ. Omitir detalles porque son "obvios" siempre conduce a malentendidos. No hay solución para eso.

Una de las razones por las que el gran O se usa tanto es porque se usa tanto. Muchas personas ven la notación y piensan que saben lo que significa, y luego la usan (erróneamente) ellos mismos. Esto sucede mucho con los programadores cuya educación formal solo llegó tan lejos: una vez fui culpable.

Otra es porque es más fácil escribir una O grande en la mayoría de los teclados no griegos que una gran theta.

Pero creo que mucho es debido a una especie de paranoia. Trabajé en programación relacionada con la defensa por un tiempo (y sabía muy poco sobre el análisis de algoritmos en ese momento). En ese escenario, el peor de los casos es siempre lo que le interesa a la gente, porque ese peor caso podría suceder en el momento equivocado. No importa si la probabilidad real de que eso ocurra es, por ejemplo, mucho menor que la probabilidad de que todos los miembros de la tripulación de un barco sufran un ataque repentino de corazón de platija en el mismo momento; aún podría suceder.

Aunque, por supuesto, muchos algoritmos tienen su peor caso en circunstancias muy comunes, el ejemplo clásico es insertar en orden en un árbol binario para obtener lo que efectivamente es una lista de enlace único. Una evaluación "real" del desempeño promedio necesita tener en cuenta la frecuencia relativa de los diferentes tipos de entrada.