Cómo entender las anotaciones asintóticas

Answer 1

La mejor manera de aprender las anotaciones asintóticas es seguir esta serie, solo te llevará 15 minutos y serás un experto en algoritmos y complejidad de tiempo:

1. ¿Qué es un algoritmo?

1. ¿Qué es la complejidad del tiempo?

1. Finalmente, ¿qué es la notación asintótica?

En los videos se sigue la enseñanza de la narración de historias para hacernos entender cada concepto de una manera única, y ten en cuenta que nunca olvidarás los conceptos una vez que veas estos videos.

Estoy describiendo aquí una historia del video, que nuevamente nos ayudaría a obtener más claridad.

Supongamos que es un día festivo y estás acostado en la habitación de tu hostal y viendo una película en tu computadora portátil. Ahora uno de tus amigos te llama cuando estás a punto de llegar al clímax y te pregunta si puede venir, ya que se está aburriendo en casa.
Aunque estás demasiado involucrado en la película, pero un amigo necesitado es un amigo, así que llamas a tu amigo a casa.
Él viene, tienen una buena sesión de chat y de repente tienen ganas de beber.

Este es el telón de fondo de la historia, ahora expongamos la historia en términos de estas constantes complicadas:

Hay una función f (n) para la cual: –
Su objetivo : tomar licor y emborracharse
c : Día seco (esto significa que todas las licorerías están cerradas hoy)
n : Número de personas (tú y tu amigo = 2)

Puede haber 3 posibilidades:

1. Tu amigo no llegó (tipo inútil), por lo tanto, n = 1,
   y como estás solo y espero que no bebas solo, es un día seco o no, no importa, ya que simplemente no quieres beber,
   lo que implica c = irrelevante
2. Llega tu amigo, pero hoy no es un día seco, por lo tanto, n = 2 pero c = falso.
   Entonces, en este caso, puede llegar fácilmente a un lugar de licores y disfrutar de su velada juntos
3. Llega tu amigo, y hoy es un día seco, por lo tanto, n = 2 yc = verdadero
   Lo siento mucho, pero no obtendrás tu licor esta vez, jaja. ¡Es una broma! aún trata de organizar uno, llamando a sus amigos y preguntándoles si lo tienen en existencia.

Ahora puedes ver aquí, el Caso 1 tomará el menor tiempo, ya que no amigo = no beber
El caso 3 tomará el tiempo máximo, ya que consumirá mucho tiempo para organizar el licor.

Por lo tanto, podemos decir, cuando n> = n0 (n0 = 2 aquí) yc = Día seco, el caso 3 lleva más tiempo que el caso 2 o 1,
así (caso 3) cg (n) es O grande para (caso 1 o 2) f (n)

Básicamente, cualquier desafío que pueda surgir, creo en ti, puedes organizar el licor y emborracharte: p

¡Espero que esto ayude!

Answer 2

El análisis asintótico se usa para estudiar cómo crece el tiempo de ejecución a medida que aumenta el tamaño de entrada. Este crecimiento se estudia en términos del tamaño de entrada. El tamaño de entrada, que generalmente se denota como N o M , podría significar cualquier cosa desde el número de números (como en la ordenación), número de nodos (como en gráficos) o incluso número de bits (como en la multiplicación de dos números).
Al tratar con el análisis asintótico, nuestro objetivo es descubrir qué algoritmo funciona mejor en casos específicos. Tenga en cuenta que un algoritmo se ejecuta en tiempos bastante variables incluso para entradas del mismo tamaño. Para apreciar esto, considere que es una máquina de clasificación. Se le dará un conjunto de números y necesita ordenarlos. Si le doy una lista ordenada de números, no tendría trabajo, y ya está hecho. Si le doy una lista ordenada inversa de números, imagine la cantidad de operaciones que necesita hacer para ordenar la lista. Ahora que ves esto, date cuenta de que necesitamos una forma de saber en qué caso sería la entrada? ¿Sería el mejor caso? ¿Recibiría una entrada en el peor de los casos? Para responder a esto, necesitamos algunos conocimiento de la distribución de la entrada. ¿Serán los peores casos? ¿O serán los casos promedio? ¿O serán los mejores casos?
El conocimiento de la distribución de entrada es bastante difícil de determinar en la mayoría de los casos. Entonces nos quedan dos opciones. Podemos suponer un caso promedio todo el tiempo y analizar nuestro algoritmo, o podríamos obtener una garantía sobre el caso en ejecución independientemente del distribución de entrada. El primero se conoce como análisis de caso promedio, y para hacer dicho análisis se requeriría una definición formal de lo que hace un caso promedio. A veces esto es difícil de definir y requiere mucha comprensión matemática. Todo el problema vale la pena, cuando sabes que algún algoritmo se ejecuta mucho más rápido en el caso promedio, en comparación con su peor tiempo de ejecución. Hay varios algoritmos aleatorios que dan testimonio de esto. En tales casos, hacer un análisis de caso promedio revela su aplicabilidad práctica. En este último caso, el análisis del peor de los casos se usa con mayor frecuencia, ya que proporciona una buena garantía del tiempo de ejecución. En la práctica, encontrar el peor de los casos suele ser bastante intuitivo. Digamos que usted es la máquina de clasificación, el peor de los casos es como una matriz de clasificación inversa ¿Cuál es el caso promedio?
Sí, estás pensando, ¿verdad? No es tan intuitivo.
El mejor análisis de casos rara vez se usa, ya que no siempre se obtienen los mejores casos. Aún así se puede hacer un análisis de este tipo y encontrar comportamientos interesantes.
En conclusión, cuando tenemos un problema que queremos resolver, se nos ocurren algoritmos. Una vez que tenemos un algoritmo, debemos decidir si es de utilidad práctica para nuestra situación. Si es así, seguimos adelante y seleccionamos los algoritmos que pueden aplicarlos y compararlos en función de su complejidad de tiempo y espacio. Podría haber más métricas para comparar, pero estas dos son fundamentales. Una de esas métricas podría ser la facilidad de implementación. Y dependiendo de la situación en cuestión, emplearía el peor de los casos análisis o análisis de casos promedio es el mejor análisis de casos. Por ejemplo, si rara vez tiene los peores escenarios, entonces tiene mucho más sentido llevar a cabo un análisis de casos promedio. Sin embargo, si el rendimiento de nuestro código es de naturaleza crítica y necesitamos proporcionar el salida en un límite de tiempo estricto, entonces es mucho más prudente mirar el análisis del peor de los casos. Por lo tanto, el análisis que realice depende de la situación en cuestión, y con el tiempo, la intuición de qué análisis aplicar se convierte en una segunda naturaleza.

Breve descripción de Big-Oh:
Cuando decimos f (x) = O (g (x)), queremos decir que para alguna constante c independiente del tamaño de entrada, f (x) <= cg (x) para todo x> = k
en otras palabras, más allá de cierto punto k, la curva f (n) siempre está limitada por encima de la curva g (n) como se muestra en la figura.
Ahora, en el caso que haya considerado, las operaciones de suma y resta, la multiplicación son todas operaciones primitivas que requieren tiempo constante (O (1)). Digamos que la suma de dos números lleva tiempo ‘a’ y la asignación del resultado lleva tiempo ‘b’.
Entonces para este código:
para (i = 0; i Seamos descuidados e ignoremos las operaciones de bucle for de asignación y actualización. El tiempo de ejecución T (n) = (a + b) n2.
Tenga en cuenta que esto es solo O (n2) , ¿por qué?
Según la definición, esto significa que podemos identificar algún punto k más allá del cual, para alguna constante c, la curva T (n) siempre está limitada por n2.
Tenga en cuenta que esto es cierto. Siempre podemos elegir constantes suficientemente grandes para que la curva cn ^ 2 siempre se limite por encima de la curva dada.
Por eso la gente dice: ¡ Suelta las constantes!
En pocas palabras: Big O de f (n) es g (n) significa que, a la derecha de alguna línea vertical, la curva f (n) siempre está limitada por g (n).

Answer 3

Ir a través de los 2 enlaces a continuación. primero el video y la página web. pasar por varias veces, obtendrá los conceptos básicos para comenzar ..
Puede verificar el video MIT en asintótico, pero creo que este es fácil de comenzar.
Capítulo 3 – Anotaciones asintóticas

Y luego vea los enlaces a continuación solo para analizar sus programas normales.
Complejidad y notación Big-O
Complejidad y análisis de algoritmos

Answer 4

Antes de comenzar con las anotaciones asintóticas, es mejor revisar los conceptos matemáticos de las funciones y la teoría de conjuntos. Puede consultar los Tutoriales de Ingeniería Matemática – GeeksforGeeks.

Ahora, para comenzar con el Análisis Asintótico, puede ver este conjunto de 4 videos: Análisis de Complejidad de Tiempo – YouTube. Esto le dará una visión general del tema. Luego puede consultar la sección Análisis de algoritmos en Algoritmos – GeeksforGeeks.

Para una comprensión profunda de las anotaciones asintóticas, puede leer Introducción a los algoritmos de Thomas H. Cormen y Charles E. Leiserson.

¡Para más práctica, resuelve Matemáticas discretas de Kenneth Rosen!

¡Espero que esto te ayude!

Answer 5

Puedes ver este breve video y seguir libros para aprenderlo en profundidad. Ahora, dado que tiene amplias aplicaciones, necesitará el concepto durante toda su carrera de programación.

Answer 6

El análisis asintótico está vinculado a la entrada, es decir, si no hay entrada al algoritmo, se concluye que funciona en un tiempo constante. Aparte de la “entrada”, todos los demás factores se consideran constantes. El análisis asintótico se refiere a calcular el tiempo de ejecución de cualquier operación en unidades matemáticas de cálculo.

Utiliza estos enlaces:

academia Khan

Anotaciones asintóticas y análisis a priori

Answer 7

Hay muchas fuentes en línea como las conferencias en video de NPTEL sobre Diseño y Análisis de Algoritmos, conferencias en video en Coursera y software de campo abierto MIT. Puedes ver estas video conferencias y aprender.

Answer 8

Siempre puede referirse a “El gran libro blanco (de algoritmos)”, es decir

Introducción a los algoritmos por CLRS