Te recomendamos que pruebes esta solución en un entorno controlado antes de pasarlo a producción, saludos.
Solución:
Tengo que estar de acuerdo en que es bastante extraño la primera vez que ves un algoritmo O (log n) … ¿de dónde diablos viene ese logaritmo? Sin embargo, resulta que hay varias formas diferentes de hacer que un término de registro se muestre en notación O grande. A continuación, presentamos algunos:
Dividiendo repetidamente 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 registro2 16 = 4. Hmmm … ¿qué pasa con 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 log2 128 = 7. ¿Es esto una coincidencia? ¡No! Hay una buena razón para esto. Suponga que dividimos un número n por 2 i veces. Entonces obtenemos el número n / 2I. Si queremos resolver el valor de i donde este valor es como máximo 1, obtenemos
n / 2I ≤ 1
n ≤ 2I
Iniciar sesión2 n ≤ yo
En otras palabras, si elegimos un entero i tal que i ≥ log2 n, luego de dividir n por la mitad i veces tendremos un valor que sea como máximo 1. La i más pequeña para la que esto está garantizado es aproximadamente log2 n, entonces si tenemos un algoritmo que divide por 2 hasta que el número se vuelve lo suficientemente pequeño, entonces podemos decir que termina en O (log n) pasos.
Un detalle importante es que no importa por qué constante estás dividiendo n (siempre que sea mayor que uno); si divide por la constante k, tomará logk n pasos para llegar a 1. Por lo tanto, cualquier algoritmo que divida repetidamente el tamaño de entrada por alguna fracción necesitará O (log n) iteraciones para terminar. Esas iteraciones pueden llevar mucho tiempo y, por lo tanto, el tiempo de ejecución neto no necesita ser O (log n), pero el número de pasos será logarítmico.
Entonces, ¿de dónde viene esto? Un ejemplo clásico es búsqueda binaria, un algoritmo rápido para buscar un ordenado array por un valor. El algoritmo funciona así:
- Si el array está vacío, devuelva que el elemento no está presente en el array.
- De lo contrario:
- Mira el elemento medio de la array.
- Si es igual al elemento que estamos buscando, devuelve éxito.
- Si es mayor que el elemento que buscamos:
- Deseche la segunda mitad del array.
- Repetir
- Si es menor que el elemento que estamos buscando:
- Deseche la primera mitad del array.
- Repetir
Por ejemplo, para buscar 5 en el array
1 3 5 7 9 11 13
Primero miraríamos el elemento del medio:
1 3 5 7 9 11 13
^
Desde 7> 5, y desde el array está ordenado, sabemos con certeza que el número 5 no puede estar en la mitad posterior de la array, por lo que podemos descartarlo. Esto deja
1 3 5
Así que ahora miramos el elemento del medio aquí:
1 3 5
^
Como 3 <5, sabemos que 5 no puede aparecer en la primera mitad del array, para que podamos lanzar la primera mitad array dejar
5
De nuevo miramos en medio de esto. array:
5
^
Dado que este es exactamente el número que estamos buscando, podemos informar que 5 está en el array.
Entonces, ¿qué tan eficiente es esto? Bueno, en cada iteración tiramos al menos la mitad del resto array elementos. El algoritmo se detiene tan pronto como array está vacío 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 del array hasta que nos quedemos sin elementos. ¿Cuánto tiempo lleva esto? Bueno, ya que seguimos cortando el array a la mitad una y otra vez, haremos como máximo O (log n) iteraciones, ya que no podemos cortar el array a la mitad más de O (log n) veces antes de que nos quedemos sin array elementos.
Algoritmos siguiendo la técnica general de divide y conquistaras (cortar el problema en pedazos, resolver esos pedazos y luego volver a armar el problema) tienden a tener términos logarítmicos por esta misma razón: no puede seguir cortando un objeto por la mitad más de O (log n) veces. Es posible que desee mirar fusionar ordenació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 n de base 10? 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 10k. El número más grande de k dígitos es 999 … 9, k veces, y esto es igual a 10k + 1 – 1. En consecuencia, si sabemos que n tiene k dígitos, entonces sabemos que el valor de n es como máximo 10k + 1 – 1. Si queremos resolver k en términos de n, obtenemos
n ≤ 10k + 1 – 1
n + 1 ≤ 10k + 1
Iniciar sesión10 (n + 1) ≤ k + 1
(Iniciar sesión10 (n + 1)) – 1 ≤ k
De donde obtenemos que k es aproximadamente el logaritmo en base 10 de n. En otras palabras, el número de dígitos de n es O (log n).
Por ejemplo, pensemos en la complejidad de sumar dos números grandes que son demasiado grandes para caber en una palabra de máquina. Supongamos que tenemos esos números representados en base 10, y llamaremos a los números my n. Una forma de sumarlos es a través del método de la escuela primaria: escriba los números un dígito a la vez, luego trabaje de derecha a izquierda. Por ejemplo, para sumar 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 sumamos el 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 penúltimo dígito (“antepenúltimo”):
1 1
1 3 3 7
+ 2 0 6 5
==============
4 0 2
Finalmente, agregamos el cuarto al último dígito (“pre-penúltimo” … Me encanta el inglés):
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 necesitamos visitar cada dígito en los dos números.
Muchos algoritmos obtienen un término O (log n) al trabajar un dígito a la vez en alguna base. Un ejemplo clásico es tipo de radix, que ordena los números enteros un dígito a la vez. Hay muchos tipos de ordenación 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 de esto es que cada pasada del tipo toma O (n) tiempo, y hay un total de O (log U) iteraciones 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 escala del algoritmo de flujo máximo de Ford-Fulkerson, tienen un término logarítmico en su complejidad porque funcionan un dígito a la vez.
En cuanto a su segunda pregunta sobre cómo resuelve ese problema, es posible que desee ver 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 le desaconsejaría mirar la respuesta hasta que la haya dado. Algún pensamiento.
¡Espero que esto ayude!
Cuando hablamos de descripciones del gran Oh, por lo general estamos hablando de tiempo se necesita para resolver problemas de un determinado Talla. Y generalmente, para problemas simples, ese tamaño solo se caracteriza por la cantidad de elementos de entrada, y eso generalmente se llama n o N. (Obviamente, eso no siempre es true- los problemas con gráficos a menudo se caracterizan por el número de vértices, V, y el 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 todo N> algún N_0 arbitrario, hay una constante c, de modo que el tiempo de ejecución del algoritmo es menos que esa constante c veces (alguna función de N.)
En otras palabras, no piense en problemas pequeños donde la “sobrecarga constante” de establecer el problema es importante, piense en problemas grandes. Y cuando se piensa en grandes problemas, big-Oh of (alguna función de N) significa que el tiempo de ejecución es todavía siempre menor que unos tiempos constantes que funcionan. Siempre.
En resumen, esa función es un límite superior, hasta un factor constante.
Entonces, “gran-Oh de log (n)” significa lo mismo que dije anteriormente, excepto que “alguna función de N” se reemplaza por “log (n)”.
Entonces, su problema le dice que piense en la búsqueda binaria, así que pensemos en eso. Supongamos que tiene, digamos, una lista de N elementos que están ordenados en orden creciente. Desea averiguar si existe un número determinado en esa lista. Una forma de hacer eso que es no una búsqueda binaria es simplemente escanear cada elemento de la lista y ver si es su número objetivo. Puede que tengas suerte y lo encuentres en el primer intento. Pero en el peor de los casos, comprobará N momentos diferentes. Esta no es una búsqueda binaria, y no es un gran Oh de log (N) porque no hay forma de forzarlo en los criterios que esbozamos anteriormente.
Puede elegir esa constante arbitraria para que sea c = 10, y si su lista tiene N = 32 elementos, está 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 aún podrá encontrar algo de N que infrinja ese requisito. En otras palabras, no hay N_0.
Sin embargo, si hacemos una búsqueda binaria, elegimos el elemento del medio y hacemos una comparación. Luego tiramos la mitad de los números y lo hacemos una y otra vez, 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 pueden Elija esa constante arbitraria c, de tal manera que siempre se cumpla el requisito para valores grandes de N.
Con todo ese trasfondo, lo que O (log (N)) generalmente significa es que tiene alguna forma de hacer algo simple, lo que reduce el tamaño de su problema a la mitad. Al igual que la búsqueda binaria anterior. Una vez que corte el problema a la mitad, puede cortarlo a la mitad una y otra vez. Pero, críticamente, lo que hipocresía hacer es algún paso de preprocesamiento que tomaría más tiempo que ese tiempo O (log (N)). Entonces, por ejemplo, no puede mezclar sus dos listas en una lista grande, a menos que también pueda 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 anteriormente).
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 submatrices de X e Y. Las demás 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).
Empiece con MEDIAN (X, 1, n, Y, 1, n).
MEDIAN(X, p, r, Y, i, k)
if X[r]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] 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]