Cómo saber si un algoritmo es [matemática] O (n) [/ matemática], [matemática] O (2n) [/ matemática] o [matemática] O (n ^ 2) [/ matemática]

1. O (n): algoritmo de tiempo lineal, toma n entradas y las ejecuta una por una. Generalmente los bucles toman O (n). Piense en encontrar un elemento en una lista de ordenamiento sin clasificar marcando cada elemento uno por uno hasta que encuentre el que está buscando. Puede que esté confundido acerca de por qué es O (n) cuando el algoritmo termina más rápido a veces, recuerde que el gran Oh siempre mira el peor de los casos, por lo que en el peor de los casos tendrá n elementos en su matriz y el que usted ‘ la búsqueda podría estar al final de la lista de la matriz, lo que significa que atravesó n entradas para encontrar el elemento que estaba buscando, lo que resultó en O (n). Ejemplos son búsquedas en colas, listas enlazadas individualmente, etc.
2. O (2n): imagine un algoritmo que toma n entradas y toma el doble de entradas como su peor caso. Es importante tener en cuenta aquí que O (2n) = O (n), sin entrar en demasiados detalles, comprende que el constante “2” tiene un impacto decreciente a medida que el algoritmo se escala y, por lo tanto, podemos ignorarlo y dar como resultado O (n).
3. O (n ^ 2): algoritmo de tiempo exponencial. Por cada n entradas, el algoritmo tarda O (n ^ 2) tiempo. Esto significa que el algoritmo puede comenzar de forma moderada pero puede aumentar los valores de n (a medida que aumenta el número de entradas, más pobre se vuelve nuestro algoritmo). En general, la mayoría de los algoritmos de ordenación de matrices como Bubble Sort, Selection Sort, Insertion Sort, etc. entran en esta categoría.

Voy a responder esta pregunta en 2 partes, suponiendo que comprenda la gran notación oh y solo quiera saber cómo encontrarla.

Suponga que hay un algoritmo que toma un conjunto de datos de tamaño n como entrada.

A. Parte 1 de la respuesta:

si un algoritmo se completa en

1. n o menos que igual a n pasos, tiene O (n).
   Ejemplo: algoritmo de búsqueda lineal, donde un elemento particular se debe buscar de forma secuencial de principio a fin en el conjunto de datos dado. Si se encuentra coincidencia, el algoritmo se termina. El número máximo de pasos antes de la finalización es n.
2. O (n) y O (2n) son iguales y puedes encontrarlo aquí:
   En las grandes anotaciones O, ¿por qué O (2n) es igual a O (n)?
3. menor o igual que n ^ 2 pasos, tiene O (n ^ 2)
   Ejemplo: algoritmo de ordenación por inserción, donde se debe ordenar el conjunto de datos de tamaño n (digamos enteros). El número máximo de pasos es n ^ 2, es decir, habrá como máximo n ^ n comparaciones para ordenar el conjunto de datos.

B: Parte 2 de la respuesta:

1. Su algoritmo tiene O (n) si solo tiene un bucle con límite superior n.
2. Su algoritmo tiene O (2n) si tiene dos bucles cada uno con límite superior n, y uno después del otro. Pero todavía se considera como O (n)
3. Su algoritmo tiene O (n ^ 2) si tiene dos bucles cada uno con un límite superior n, y uno dentro de otro.

Espero que esto te ayude.

PD: aprendí el concepto de gran oh por mi cuenta, así que estaré feliz si me corrigen cuando sea necesario. Gracias.

O (n) es un algoritmo lineal , lo que significa que si tuviéramos una lista l , y l tenía n artículos , y por ejemplo necesitábamos encontrar un artículo en l, tomaría n operaciones en el peor de los casos para encontrarlo. Escribiríamos un ciclo para iterar sobre l para encontrar el elemento .

O (n2) es un algoritmo cuadrático , lo que significa que si tuviéramos una lista l , y yo tuviera n ítems, y por ejemplo necesitábamos encontrar el ítem más grande en l , compararíamos cada ítem con todos los otros ítems en el peor de los casos en l Para encontrar el elemento más grande, piense en un bucle anidado en un bucle.

O (2n) es un algoritmo exponencial , piense en Fibonacci recursiva , este crecimiento se duplica con cada entrada .

Esta es una respuesta muy básica, también tengo una comprensión básica de la notación asintótica , pensé que contribuiría.

A continuación se muestra una representación gráfica del crecimiento de las tasas de diferentes tiempos de ejecución.

Espero que esto ayude.

Estudiar y practicar:

https://ocw.mit.edu/courses/elec …

¡Conoce tus complejidades!

Conferencias de video | Matemáticas para la informática | Ingeniería Eléctrica e Informática | MIT OpenCourseWare

Videos de la conferencia | Introducción a los algoritmos | Ingeniería Eléctrica e Informática | MIT OpenCourseWare

Lo sabes analizando la complejidad de tu algoritmo. Además, verifique la entrada de notación Big O en Wikipedia. Verá que, de hecho, [matemática] O (2n) [/ matemática] no tiene mucho sentido decir, ya que la notación generalmente solo se refiere a tiempos de ejecución hasta un factor constante.

Ejemplo simple: calculemos el valor máximo de alguna lista que contiene elementos [math] n [/ math]. Puede hacerlo definiendo el valor del máximo encontrado hasta ahora, recorriendo cada uno de los elementos [math] n [/ math] y sobrescribiendo el máximo actual cada vez que se encuentra un valor mayor. Cada comparación lleva una cantidad constante de tiempo, y usted está haciendo comparaciones [matemáticas] n [/ matemáticas]. Primero pasa un tiempo definiendo el valor máximo actual y así sucesivamente, por lo que el tiempo de ejecución real en función de [math] n [/ math] es [math] f (n) = a + b \ times n [/ math ] Sin embargo, esta función es [matemática] O (n) [/ matemática] porque existe una constante [matemática] M [/ matemática] tal que [matemática] | f (n) | \ leq M \ cdot n [/ math] como [math] n [/ math] tiende al infinito. Entonces puede ver cómo [math] O (2n) [/ math] se vuelve discutible, aunque técnicamente no es incorrecto, porque cualquier función que sea [math] O (n) [/ math] también es [math] O (2n) [ / matemáticas] y viceversa.

Si su iteración de bucle necesita evaluar las declaraciones dentro del bucle desde el primer índice hasta el último índice para obtener su valor de optimización, significa

En)

por ejemplo:

// se ejecuta n veces

para (int i = 1; i <= n; ++ i)

{

m + = 2; // tiempo constante, c

}

por ejemplo, busque un elemento en una matriz de tamaño n, donde n = 1,2,3, … ..cualquier número.

O (2n) casi igual a O (n)

O (n ^ 2)

Analizar de adentro hacia afuera. El tiempo total de ejecución es producto del tamaño de todos los bucles.

ex.

// bucle externo ejecutado n veces

para (int i = 1; i <= n; ++ i)

{

// bucle interno ejecutado n veces

para (int j = 1; j <= n; ++ j)

{

k = k + 1 // tiempos constantes

}

}

por ejemplo, selección de clasificación, clasificación de burbujas, clasificación de inserción. etc.

Sugeriría pasar por los videos en el sitio web http://www.inerviewbit.com . En un par de horas, este misterio se resolverá por ti, con suerte una vez y para siempre.

La forma en que los profesores lo enseñan en institutos educativos formales, realmente no ayuda, solo te confunde de por vida.

Hay 2 clases abiertas en Coursera a partir de hoy. Algoritmo I y Pensamiento Algorítmico. Ambos tienen 2 partes. Tomarlos podría ayudar. Ambos son un nivel intermedio. Uno usa python y el otro usa java