Mi conocimiento de big-O es limitado, y cuando aparecen términos logarítmicos en la ecuación, me desconcierta aún más.

¿Puede alguien explicarme en términos simples qué es un O(log n)algoritmo? ¿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) e Y (1..n) contengan dos listas de enteros, cada uno ordenado en orden no decreciente. Proporcione un algoritmo de tiempo O (log n) para encontrar la mediana (o el n-ésimo entero más pequeño) de los 2n elementos combinados. 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]

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 log ₂ 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 log ₂ 128 = 7. ¿Es una coincidencia? ¡No! Hay una buena razón para esto. Supongamos que dividimos un número n por 2 i veces. Luego obtenemos el número n / 2 ⁱ . Si queremos resolver el valor de i donde este valor es como máximo 1, obtenemos

n / 2 ^yo ≤ 1

n ≤ 2 ^yo

log ₂ n ≤ i

En otras palabras, si elegimos un entero i tal que i ≥ log ₂ n, luego de dividir n por la mitad i veces tendremos un valor que es como máximo 1. La i más pequeña para la que esto está garantizado es aproximadamente log ₂ 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á dividiendo n (siempre que sea mayor que uno); si divide por la constante k, se necesitarán log _k 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, 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, ¿de dónde viene esto? Un ejemplo clásico es la búsqueda binaria , un algoritmo rápido para buscar un valor en una matriz ordenada. El algoritmo funciona así:

• Si la matriz está vacía, devuelva que el elemento no está presente en la matriz.
• De otra manera:
  • Mira el elemento del medio de la matriz.
  • Si es igual al elemento que estamos buscando, devuelve éxito.
  • Si es mayor que el elemento que buscamos:
    • Deseche la segunda mitad de la matriz.
    • Repetir
  • Si es menor que el elemento que estamos buscando:
    • Deseche la primera mitad de la matriz.
    • Repetir

Por ejemplo, para buscar 5 en la matriz

1   3   5   7   9   11   13

Primero miraríamos el elemento del medio:

1   3   5   7   9   11   13
            ^

Dado que 7> 5, y dado que la matriz está ordenada, sabemos con certeza que el número 5 no puede estar en la mitad posterior de la matriz, 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 de la matriz, por lo que podemos lanzar la primera mitad de la matriz para dejar

        5

Nuevamente miramos el medio de esta matriz:

        5
        ^

Dado que este es exactamente el número que estamos buscando, podemos informar que 5 está en la matriz.

Entonces, ¿qué tan eficiente es esto? Bueno, en cada iteración desechamos al menos la mitad de los elementos restantes de la matriz. 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 por la mitad una y otra vez, terminaremos en la mayoría de O (log n) iteraciones, ya que no podemos cortar la matriz a la mitad más de O (log n) veces antes de ejecutar fuera de los elementos de la matriz.

Los algoritmos que siguen la técnica general de dividir y conquistar (cortar el problema en partes, resolver esas partes 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 en la mitad más que O (log n) veces. Es posible que desee ver la ordenación combinada 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 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 ₁₀ (n + 1) ≤ k + 1

(log ₁₀ (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
==============

Sumamos el último dígito y llevamos el 1:

          1
    1  3  3  7
+   2  0  6  5
==============
             2

Luego agregamos el penúltimo dígito ("penúltimo") 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 ("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 necesitan ser procesados. 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 el ordenamiento por radix , que ordena los números enteros un dígito a la vez. Hay muchos tipos de ordenación de base, 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 trabajan un dígito a la vez.

En cuanto a su segunda pregunta sobre cómo resolver 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 logarítmico 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 de grandes Oh, generalmente estamos hablando del tiempo que se necesita para 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 eso generalmente se llama n o N. (Obviamente, eso no siempre es cierto; los problemas con gráficas a menudo se caracterizan en números 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 todo N> algún N_0 arbitrario, 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 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 sigue siendo siempre menor que algunos tiempos constantes de esa función. 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 ordenados en orden creciente. Desea averiguar si existe un número determinado en esa lista. Una forma de hacer eso que no es una búsqueda binaria es simplemente 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, 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 bosquejamos arriba.

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 algunos N que violen 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 puede elegir 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 tienes alguna forma de hacer algo simple, lo que reduce el tamaño del 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 y otra vez. Pero, críticamente, lo que no puede hacer es algún paso de preprocesamiento que tomaría más tiempo que ese 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[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)

El término Log aparece muy a menudo en el análisis de complejidad de algoritmos. Aquí tienes algunas explicaciones:

1. ¿Cómo representas 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 que 10 ^ d puede representarse en d dígitos.

Entonces, ¿cuántos dígitos se requieren para representar 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 aparece log de nuevo ...
==> d = piso (log (x)) + 1

También tenga en cuenta que esta es la forma más concisa de denotar el número en este rango. Cualquier reducción conducirá 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 asignar 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 y N - 1 = log (N) dígitos.

Esto implica que, cuando se nos pide que busquemos un número en la línea entera, que va de 0 a N - 1, necesitamos al menos log (N) intenta encontrarlo. ¿Por qué? Cualquier algoritmo de búsqueda deberá elegir un dígito tras otro en su búsqueda del número.

El número mínimo de dígitos que debe elegir es log (N). Por tanto, el número mínimo de operaciones necesarias para buscar un número en un espacio de tamaño N es log (N).

¿Puedes adivinar las complejidades del orden de la búsqueda binaria, la búsqueda ternaria o la búsqueda deca?
¡Es O (log (N))!

3. ¿Cómo clasifica un conjunto de números?

Cuando se le pide que ordene un conjunto de números A en una matriz B, así es como se ve ->

Permutar elementos

Cada elemento de la matriz original debe asignarse a su índice correspondiente en la matriz ordenada. Entonces, para el primer elemento, tenemos n posiciones. Para encontrar correctamente el índice correspondiente en este rango de 0 a n - 1, necesitamos… operaciones log (n).

El siguiente elemento necesita operaciones log (n-1), el siguiente log (n-2) y así sucesivamente. El total llega a ser:

==> log (n) + log (n - 1) + log (n - 2) +… + log (1)

Usando log (a) + log (b) = log (a * b),

==> log (¡norte!)

Esto se puede aproximar a nlog (n) - n.
¿Cuál es O (n * log (n))!

Por lo tanto, llegamos a la conclusión de que no puede haber un algoritmo de clasificación que funcione 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 que vemos aparecer log (n) con tanta frecuencia en el análisis de complejidad de los algoritmos. Lo mismo se puede extender a los números binarios. Hice un video sobre eso aquí.
¿Por qué aparece log (n) con tanta frecuencia durante el análisis de complejidad del algoritmo?

¡Salud!

Llamamos a la complejidad de tiempo 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, ya que el algoritmo trabaja hacia la solución.

Aún no puedo comentar ... ¡es necro! 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 cinco. Estas son secuencias no decrecientes, no todos los valores son distintos.

Pruebe también este ejemplo de longitud 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 su lugar, ofrezco este algoritmo, llámelo 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)
}