¿Cómo se calculan O (logn) y O (nlogn)?

Answer 1

¡Bueno!

Así que comienza con algo muy básico.

Código:

número = 100

while (número! = 0) {

número = número / 2;

}

Explicación de funcionamiento en seco:

para la primera iteración, número = 100

para la segunda iteración, número = 50

para la tercera iteración, número = 25

para la cuarta iteración, número = 12

para la quinta iteración, número = 6 … y así.

Entonces podemos ver aquí, después de cada iteración, mi número se está convirtiendo en la mitad de su valor original. ¡Eso es! Esto implica que la complejidad temporal del código anterior es O (logn)

En palabras más simples, la forma en que n ^ 2 se duplica en cada iteración se registra de manera similar en cada iteración.

Algunos ejemplos conocidos de O (logn):

• Búsqueda binaria: en cada iteración, el grupo de búsqueda se convertirá en la mitad del valor original.
• Encontrar el número más grande / más pequeño en un árbol de búsqueda binario: en cada iteración, soltaremos cualquier medio árbol a la izquierda o a la derecha.

Ahora vamos a O (nlogn)

Código:

número = 100

para (int i = 0; i <100; i ++) {

while (número! = 0) {

número = número / 2;

}

}

Ahora el proceso de registro debe ejecutarse n veces.

Algunos ejemplos conocidos de O (nlogn):

• Ordenar por fusión: El Ordenar por fusión utiliza el enfoque de dividir y conquistar para resolver el problema de clasificación. Primero, divide la entrada a la mitad usando recursividad. Después de dividir, clasifica las mitades y las fusiona en una salida ordenada.
• Ordenación rápida

¡Gracias!

Answer 2

Lo que está preguntando se responde en una rama completa de las matemáticas que se ocupa del estudio, diseño y análisis de algoritmos y cómo se comportan a medida que aumenta el tamaño de entrada. Permítanme comenzar de una manera elegante:

T (n) = O (f (n), si y solo si existen constantes cyd

tal que

T (n) <= cf (n) para todos n> = d.

Suena confuso al principio, pero esto fue “Solo para dar un vistazo” de lo que hay debajo del capó y que hay mucho por explorar.

Para este problema particular, tome una instancia de Merge sort.

La idea de alto nivel es dividir el problema (en este caso, matriz) en dos mitades, resolver subproblemas y luego combinar los resultados

Ahora dividamos el problema en subniveles (j = 0,1,2,3….), Digamos inicialmente que está en el nivel 0 y que aún no se ha trabajado en la matriz,

En el siguiente subnivel, la matriz se divide en dos partes, cada una de longitud n / 2, y hay dos de ellas, en el siguiente paso se sigue el mismo procedimiento en el nivel dos, tiene 4 subproblemas de tamaño n / 4, y así sucesivamente.

En general, en cada nivel j, tiene 2 ^ j subproblemas cada uno de tamaño n / 2 ^ j.

También log (base2) de cualquier número es el número de veces que divide ese número entre 2 para obtener 1.

Este patrón se observa en el siguiente problema (¡piénselo!)

Entonces el último subnivel corresponderá a log (n) (con base 2). (Esto es como un árbol, rastrearlo).

Ahora el trabajo total realizado en cada nivel es:

cantidad de subproblemas * tamaño de cada subproblema

2 ^ j * n / 2 ^ j = n

y el trabajo total realizado es

trabajo realizado en cada nivel * número de niveles

n * (logn + 1) = nlog (n) (podemos ignorar la constante 1 para n grande).

Se puede realizar un tipo de análisis similar en muchos problemas, especialmente aquellos con enfoque de dividir y conquistar.

También hay algunos otros métodos para calcular los Big Ohs, incluso los más elegantes (llamados Método maestro), que resultan ser muy exitosos para ciertos conjuntos de problemas.

Si desea profundizar en cómo funciona la mecánica, probablemente debería tomar algún curso de algoritmo relevante.

Answer 3

Básicamente: un factor de N.

O (log n)
Una búsqueda binaria solo toca un pequeño número de elementos. Si hay mil millones de elementos, la búsqueda binaria solo toca ~ 30 de ellos.

O (n log n)
Una ordenación rápida toca cada elemento, un pequeño número de veces. Si hay mil millones de elementos, la clasificación rápida los toca a todos, unas 30 veces: unos 30 mil millones de toques en total.

Cuando un ciclo de entrada completo se ejecuta una vez, entonces la complejidad es O (1) si entra en el ciclo n veces, entonces es O (n).

La idea errónea con la que traté inicialmente es para cada bucle for, es como O (n) y 2 para los bucles O (n ^ 2), pero más tarde, conocí el caso donde incluso en el bucle for puede ser O (log n).

Ej: para (i = 0; i

ejecución de bucle ();

}

O (log n): divide la estructura por la mitad una y otra vez y realiza un número constante de operaciones para cada división. En la búsqueda binaria, se divide en la mitad o más en cada bucle. y no necesariamente se puede dividir en mitades.

O (n log n): recorre la estructura de ordenación rápida donde cada vez que dividimos la matriz en dos partes y cada vez que lleva O (n) tiempo para encontrar un elemento pivote. Por lo tanto, es O (log n)

En resumen, es O (n log n).

Consejo adicional :

Una manera fácil de identificar si un algoritmo es O (log n) u O (n log n) u O (n):

Bueno, solo corre y cronometra. Ejecútelo para las entradas 1000, 10000, 100000 y un millón.

Si ve un tiempo de ejecución de 3,4,5,6 segundos (o algunos múltiples), puede decir con seguridad que es O (log n) Si es más como: 1,10,100,1000 segundos, entonces probablemente sea O (n). Y si es como 3,40,500,6000 segundos, entonces es O (n log n).

Este es el gráfico que muestra la Complejidad.

Elementos vs No de operaciones requeridas.

Answer 4

[math] \ log (n) [/ math] suele ser el resultado de dicotomías: a partir del número [math] n [/ math], puede reducirlo a la mitad [math] \ log (n) [/ math] veces. (Por ejemplo, [matemática] 1024 [/ matemática] se puede dividir [matemática] 10 [/ matemática] veces).

Una búsqueda en una tabla ordenada usa dicotomías que se pueden realizar en una sola operación cada una, por lo que la complejidad es [matemática] O (\ log (n)) [/ matemática].

Ahora, un algoritmo de ordenación como MergeSort subdivide el número de entrada [math] n [/ math] en subconjuntos de la mitad del tamaño y procesa ambos, con un procesamiento que toma operaciones [math] n [/ math]. Como esto se realiza de forma recursiva, las subdivisiones se llevan a cabo en niveles [matemáticos] \ log (n) [/ matemáticos], hasta que los subconjuntos sean elementos individuales (que no necesitan ser ordenados). En total [math] O (n \ log n) [/ math] operaciones.

Answer 5

Si el tamaño del espacio muestral se reduce a la mitad en tiempo constante, entonces es O (log n) y si se reduce a la mitad en tiempo lineal, entonces es O (n log n). ¡Sencillo!