algorithm - ordenamiento - notacion o programacion
¿Qué causaría que un algoritmo tenga complejidad O(log n)? (6)
Cuando hablamos de grandes descripciones de Oh, generalmente estamos hablando del tiempo que lleva resolver problemas de un tamaño determinado. Y, por lo general, para problemas simples, ese tamaño solo se caracteriza por la cantidad de elementos de entrada, y normalmente se llama n, o N. (Obviamente, eso no siempre es cierto-- los problemas con los gráficos a menudo se caracterizan por el número de vértices, V y número de aristas, E; pero por ahora, hablaremos de listas de objetos, con N objetos en las listas).
Decimos que un problema "es grande -Oh (de alguna función de N)" si y solo si :
Para todos N> algunos arbitrarios N_0, hay alguna constante c, tal que el tiempo de ejecución del algoritmo es menor que esa constante c veces (alguna función de N.)
En otras palabras, no piense en pequeños problemas donde importa la "carga constante" de establecer el problema, piense en grandes problemas. Y al pensar en grandes problemas, Big-Oh of (alguna función de N) significa que el tiempo de ejecución es siempre menor que algunas veces esta función. Siempre.
En resumen, esa función es un límite superior, hasta un factor constante.
Entonces, "grande-Oh de log (n)" significa lo mismo que dije antes, excepto que "alguna función de N" se reemplaza por "log (n)".
Entonces, tu problema te dice que pienses en la búsqueda binaria, así que pensemos en eso. Supongamos que tiene, por ejemplo, una lista de N elementos ordenados en orden creciente. Desea averiguar si existe un número dado en esa lista. Una forma de hacer eso que no es una búsqueda binaria es escanear cada elemento de la lista y ver si es su número objetivo. Puede tener suerte y encontrarlo en el primer intento. Pero en el peor de los casos, verificará N diferentes veces. Esta no es una búsqueda binaria, y no es grande -Oh del registro (N) porque no hay forma de forzarlo dentro del criterio que esbozamos arriba.
Puedes elegir esa constante arbitraria para que sea c = 10, y si tu lista tiene N = 32 elementos, estás bien: 10 * log (32) = 50, que es mayor que el tiempo de ejecución de 32. Pero si N = 64 , 10 * log (64) = 60, que es menor que el tiempo de ejecución de 64. Puede elegir c = 100, o 1000, o un trillón, y todavía podrá encontrar algunos N que violen ese requisito. En otras palabras, no hay N_0.
Sin embargo, si hacemos una búsqueda binaria, seleccionamos el elemento medio y hacemos una comparación. Luego tiramos la mitad de los números, y lo hacemos nuevamente, y nuevamente, y así sucesivamente. Si su N = 32, solo puede hacer eso unas 5 veces, que es log (32). Si su N = 64, solo puede hacer esto unas 6 veces, etc. Ahora puede seleccionar esa constante arbitraria c, de tal manera que el requisito siempre se cumple para valores grandes de N.
Con todo ese trasfondo, lo que normalmente O (log (N)) significa es que tiene alguna manera de hacer algo simple, lo que reduce el tamaño de su problema a la mitad. Al igual que la búsqueda binaria está haciendo arriba. Una vez que corte el problema a la mitad, puede cortarlo a la mitad otra vez, y otra vez, y nuevamente. Pero, críticamente, lo que no puede hacer es un paso de preprocesamiento que llevaría más tiempo que ese O (log (N)) tiempo. Entonces, por ejemplo, no puedes mezclar tus dos listas en una sola lista grande, a menos que también puedas encontrar una manera de hacerlo en el tiempo O (log (N)).
(NOTA: Casi siempre, Log (N) significa log-base-two, que es lo que supongo arriba).
Mi conocimiento de big-O es limitado, y cuando los términos de registro aparecen en la ecuación me da más.
¿Puede alguien explicarme en términos simples qué es un algoritmo O(log n) ? ¿De dónde viene el logaritmo?
Esto surgió específicamente cuando estaba tratando de resolver esta pregunta de práctica de mitad de período:
Deje que X (1..n) y Y (1..n) contengan dos listas de enteros, cada uno ordenado en orden no decreciente. Proporcione un algoritmo O (log n) -time para encontrar la mediana (o el enésimo entero más pequeño) de todos los elementos combinados 2n. Por ejemplo, X = (4, 5, 7, 8, 9) e Y = (3, 5, 8, 9, 10), entonces 7 es la mediana de la lista combinada (3, 4, 5, 5, 7 , 8, 8, 9, 9, 10). [Sugerencia: use conceptos de búsqueda binaria]
El término de registro aparece muy a menudo en el análisis de complejidad del algoritmo. Aquí hay algunas explicaciones:
1. ¿Cómo se representa un número?
Tomemos el número X = 245436. Esta notación de "245436" tiene información implícita. Haciendo esa información explícita:
X = 2 * 10 ^ 5 + 4 * 10 ^ 4 + 5 * 10 ^ 3 + 4 * 10 ^ 2 + 3 * 10 ^ 1 + 6 * 10 ^ 0
Cuál es la expansión decimal del número. Entonces, la cantidad mínima de información que necesitamos para representar este número es de 6 dígitos. Esto no es una coincidencia, ya que cualquier número menor a 10 ^ d puede representarse en d dígitos.
Entonces, ¿cuántos dígitos se requieren para representar a X? Eso es igual al mayor exponente de 10 en X más 1.
==> 10 ^ d> X
==> log (10 ^ d)> log (X)
==> d * log (10)> log (X)
==> d> log (X) // Y el registro aparece de nuevo ...
==> d = piso (log (x)) + 1
También tenga en cuenta que esta es la forma más concisa para denotar el número en este rango. Cualquier reducción dará lugar a la pérdida de información, ya que un dígito faltante se puede asignar a otros 10 números. Por ejemplo: 12 * se puede mapear a 120, 121, 122, ..., 129.
2. ¿Cómo se busca un número en (0, N - 1)?
Tomando N = 10 ^ d, usamos nuestra observación más importante:
La cantidad mínima de información para identificar unívocamente un valor en un rango entre 0 a N - 1 = dígitos de registro (N).
Esto implica que, cuando se le pida que busque un número en la línea entera, que va de 0 a N - 1, necesitamos al menos log (N) para encontrarlo. ¿Por qué? Cualquier algoritmo de búsqueda tendrá que elegir un dígito después de otro en su búsqueda del número.
El número mínimo de dígitos que necesita elegir es log (N). Por lo tanto, el número mínimo de operaciones para buscar un número en un espacio de tamaño N es log (N).
¿Puedes adivinar las complejidades de orden de la búsqueda binaria, la búsqueda ternaria o la búsqueda deca?
¡Es O (log (N))!
3. ¿Cómo se ordena un conjunto de números?
Cuando se le pide que clasifique un conjunto de números A en una matriz B, esto es lo que parece ->
Todos los elementos del conjunto original deben asignarse a su índice correspondiente en el conjunto ordenado. Entonces, para el primer elemento, tenemos n posiciones. Para encontrar correctamente el índice correspondiente en este rango de 0 a n - 1, necesitamos ... operaciones de registro (n).
El siguiente elemento necesita operaciones de registro (n-1), el siguiente registro (n-2), etc. El total viene a ser:
==> log (n) + log (n - 1) + log (n - 2) + ... + log (1)
Usando log (a) + log (b) = log (a * b),
==> log (n!)
Esto se puede approximated a nlog (n) - n.
¡Cuál es O (n * log (n))!
Por lo tanto, concluimos que no puede haber ningún algoritmo de clasificación que pueda funcionar mejor que O (n * log (n)). Y algunos algoritmos que tienen esta complejidad son los populares Merge Sort y Heap Sort.
Estas son algunas de las razones por las cuales vemos log (n) pop-up tan a menudo en el análisis de complejidad de los algoritmos. Lo mismo se puede extender a números binarios. Hice un video sobre eso aquí.
¿Por qué el registro (n) aparece tan a menudo durante el análisis de complejidad del algoritmo?
¡Aclamaciones!
En la siguiente solución, todas las líneas con una llamada recursiva se realizan en la mitad de los tamaños dados de las sub-matrices de X e Y. Otras líneas se realizan en un tiempo constante. La función recursiva es T (2n) = T (2n / 2) + c = T (n) + c = O (lg (2n)) = O (lgn).
Empiezas con MEDIAN (X, 1, n, Y, 1, n).
MEDIAN(X, p, r, Y, i, k)
if X[r]<Y[i]
return X[r]
if Y[k]<X[p]
return Y[k]
q=floor((p+r)/2)
j=floor((i+k)/2)
if r-p+1 is even
if X[q+1]>Y[j] and Y[j+1]>X[q]
if X[q]>Y[j]
return X[q]
else
return Y[j]
if X[q+1]<Y[j-1]
return MEDIAN(X, q+1, r, Y, i, j)
else
return MEDIAN(X, p, q, Y, j+1, k)
else
if X[q]>Y[j] and Y[j+1]>X[q-1]
return Y[j]
if Y[j]>X[q] and X[q+1]>Y[j-1]
return X[q]
if X[q+1]<Y[j-1]
return MEDIAN(X, q, r, Y, i, j)
else
return MEDIAN(X, p, q, Y, j, k)
Llamamos complejidad temporal O (log n), cuando la solución se basa en iteraciones sobre n, donde el trabajo realizado en cada iteración es una fracción de la iteración anterior, a medida que el algoritmo trabaja para la solución.
No puedo comentar todavía ... necro es! La respuesta de Avi Cohen es incorrecta, intente:
X = 1 3 4 5 8
Y = 2 5 6 7 9
Ninguna de las condiciones es verdadera, por lo que MEDIAN (X, p, q, Y, j, k) cortará los cincos. Estas son secuencias no decrecientes, no todos los valores son distintos.
Pruebe también este ejemplo uniforme con valores distintos:
X = 1 3 4 7
Y = 2 5 6 8
Ahora MEDIAN (X, p, q, Y, j + 1, k) cortará los cuatro.
En cambio, ofrezco este algoritmo, llámalo con MEDIAN (1, n, 1, n):
MEDIAN(startx, endx, starty, endy){
if (startx == endx)
return min(X[startx], y[starty])
odd = (startx + endx) % 2 //0 if even, 1 if odd
m = (startx+endx - odd)/2
n = (starty+endy - odd)/2
x = X[m]
y = Y[n]
if x == y
//then there are n-2{+1} total elements smaller than or equal to both x and y
//so this value is the nth smallest
//we have found the median.
return x
if (x < y)
//if we remove some numbers smaller then the median,
//and remove the same amount of numbers bigger than the median,
//the median will not change
//we know the elements before x are smaller than the median,
//and the elements after y are bigger than the median,
//so we discard these and continue the search:
return MEDIAN(m, endx, starty, n + 1 - odd)
else (x > y)
return MEDIAN(startx, m + 1 - odd, n, endy)
}
Tengo que aceptar que es bastante extraño la primera vez que ves un algoritmo O (log n) ... ¿De dónde viene ese logaritmo? Sin embargo, resulta que hay varias maneras diferentes en que puede obtener un término de registro para mostrarse en notación de gran O. Aquí hay algunos:
Repetidamente dividiendo por una constante
Tome cualquier número n; digamos, 16. ¿Cuántas veces puedes dividir n por dos antes de obtener un número menor o igual a uno? Para 16, tenemos eso
16 / 2 = 8
8 / 2 = 4
4 / 2 = 2
2 / 2 = 1
Tenga en cuenta que esto termina tomando cuatro pasos para completar. Curiosamente, también tenemos ese registro 2 16 = 4. Hmmm ... ¿qué hay de 128?
128 / 2 = 64
64 / 2 = 32
32 / 2 = 16
16 / 2 = 8
8 / 2 = 4
4 / 2 = 2
2 / 2 = 1
Esto tomó siete pasos, y log 2 128 = 7. ¿Es esto una coincidencia? ¡No! Hay una buena razón para esto. Supongamos que dividimos un número n por 2 veces. Entonces obtenemos el número n / 2 i . Si queremos resolver el valor de i donde este valor es como máximo 1, obtenemos
n / 2 i ≤ 1
n ≤ 2 i
log 2 n ≤ i
En otras palabras, si seleccionamos un número entero tal que i> log 2 n, luego de dividir n por la mitad i veces tendremos un valor que es como máximo 1. El más pequeño i para el que esto está garantizado es aproximadamente log 2 n, entonces si tenemos un algoritmo que se divide por 2 hasta que el número sea lo suficientemente pequeño, entonces podemos decir que termina en O (log n) pasos.
Un detalle importante es que no importa con qué constante se divida n (siempre que sea mayor que uno); si divide por la constante k, tomará log k n pasos para llegar a 1. Por lo tanto, cualquier algoritmo que divide repetidamente el tamaño de entrada por una fracción necesitará iteraciones O (log n) para terminar. Esas iteraciones pueden llevar mucho tiempo, por lo que el tiempo de ejecución neto no necesita ser O (log n), pero el número de pasos será logarítmico.
Entonces, ¿dónde surge esto? Un ejemplo clásico es la búsqueda binaria , un algoritmo rápido para buscar una matriz ordenada para un valor. El algoritmo funciona así:
- Si la matriz está vacía, devuelve que el elemento no está presente en la matriz.
- De otra manera:
- Mira el elemento medio de la matriz.
- Si es igual al elemento que estamos buscando, devuelve el éxito.
- Si es mayor que el elemento que estamos buscando:
- Bote la segunda mitad de la matriz.
- Repetir
- Si es menor que el elemento que estamos buscando:
- Bote la primera mitad del conjunto.
- Repetir
Por ejemplo, para buscar 5 en la matriz
1 3 5 7 9 11 13
Primero veríamos el elemento medio:
1 3 5 7 9 11 13
^
Desde 7> 5, y dado que el conjunto está ordenado, sabemos con certeza que el número 5 no puede estar en la mitad posterior del conjunto, por lo que podemos descartarlo. Esto deja
1 3 5
Entonces ahora miramos el elemento medio aquí:
1 3 5
^
Dado que 3 <5, sabemos que 5 no pueden aparecer en la primera mitad de la matriz, por lo que podemos tirar la primera mitad de la matriz para salir
5
Nuevamente vemos en el medio de esta matriz:
5
^
Dado que este es exactamente el número que estamos buscando, podemos informar que 5 está efectivamente en la matriz.
Entonces, ¿qué tan eficiente es esto? Bueno, en cada iteración estamos tirando al menos la mitad de los elementos de la matriz restantes. El algoritmo se detiene tan pronto como la matriz está vacía o encontramos el valor que queremos. En el peor de los casos, el elemento no está allí, por lo que seguimos reduciendo a la mitad el tamaño de la matriz hasta que nos quedemos sin elementos. ¿Cuánto tiempo lleva esto? Bueno, dado que seguimos cortando la matriz a la mitad una y otra vez, terminaremos en la mayoría de las iteraciones O (log n), ya que no podemos cortar la matriz en la mitad más que O (log n) veces antes de ejecutar fuera de los elementos de la matriz.
Los algoritmos que siguen la técnica general de divide-and-conquer ( divide-and-conquer el problema en partes, resolver esas piezas y luego volver a unir el problema) tienden a tener términos logarítmicos en ellas por esta misma razón: no puedes seguir cortando un objeto en la mitad más que O (log n) veces. Es posible que desee ver el tipo de fusión como un gran ejemplo de esto.
Procesando valores de un dígito a la vez
¿Cuántos dígitos hay en el número de base 10 n? Bueno, si hay k dígitos en el número, entonces tendríamos que el dígito más grande es un múltiplo de 10 k . El número más grande de k dígitos es 999 ... 9, k veces, y esto es igual a 10 k + 1 - 1. En consecuencia, si sabemos que n tiene k dígitos, entonces sabemos que el valor de n es como máximo 10 k + 1 - 1. Si queremos resolver k en términos de n, obtenemos
n ≤ 10 k + 1 - 1
n + 1 ≤ 10 k + 1
log 10 (n + 1) ≤ k + 1
(log 10 (n + 1)) - 1 ≤ k
De lo que obtenemos que k es aproximadamente el logaritmo de base 10 de n. En otras palabras, la cantidad de dígitos en n es O (log n).
Por ejemplo, pensemos en la complejidad de agregar dos números grandes que son demasiado grandes para caber en una palabra de máquina. Supongamos que tenemos esos números representados en la base 10, y llamaremos a los números myn. Una forma de agregarlos es a través del método de la escuela primaria: escriba los números de un dígito a la vez, luego trabaje de derecha a izquierda. Por ejemplo, para agregar 1337 y 2065, comenzaríamos escribiendo los números como
1 3 3 7
+ 2 0 6 5
==============
Agregamos el último dígito y llevamos el 1:
1
1 3 3 7
+ 2 0 6 5
==============
2
Luego agregamos el segundo al último ("penúltimo") dígito y llevamos el 1:
1 1
1 3 3 7
+ 2 0 6 5
==============
0 2
A continuación, agregamos el tercer al último ("antepenúltimo") dígito:
1 1
1 3 3 7
+ 2 0 6 5
==============
4 0 2
Finalmente, agregamos el cuarto al último ("preantepenultimate" ... I love English) dígito:
1 1
1 3 3 7
+ 2 0 6 5
==============
3 4 0 2
Ahora, ¿cuánto trabajo hicimos? Hacemos un total de O (1) trabajo por dígito (es decir, una cantidad constante de trabajo), y hay O (max {log n, log m}) dígitos totales que deben procesarse. Esto da un total de O (max {log n, log m}) complejidad, porque tenemos que visitar cada dígito en los dos números.
Muchos algoritmos obtienen un término O (log n) en ellos al trabajar un dígito a la vez en alguna base. Un ejemplo clásico es radix sort , que ordena enteros de un dígito a la vez. Hay muchos sabores de ordenamiento de radix, pero generalmente se ejecutan en el tiempo O (n log U), donde U es el entero más grande posible que se está ordenando. La razón para esto es que cada pasada del tipo toma O (n) tiempo, y hay un total de iteraciones O (log U) requeridas para procesar cada uno de los dígitos O (log U) del número más grande que se está ordenando. Muchos algoritmos avanzados, como el algoritmo de rutas más cortas de Gabow o la versión de escalado del algoritmo de flujo máximo de Ford-Fulkerson , tienen un término de registro en su complejidad porque funcionan un dígito a la vez.
En cuanto a su segunda pregunta sobre cómo resolver ese problema, es posible que desee consultar esta pregunta relacionada que explora una aplicación más avanzada. Dada la estructura general de los problemas que se describen aquí, ahora puede tener una mejor idea de cómo pensar en los problemas cuando sabe que hay un término de registro en el resultado, por lo que aconsejaría no mirar la respuesta hasta que la haya dado. Algún pensamiento.
¡Espero que esto ayude!