Cuando hablamos de descripciones big-Oh, generalmente estamos hablando del tiempo que se necesita para resolver problemas de un tamaño dado. Y por lo general, para problemas simples, ese tamaño se caracteriza sólo por el número de elementos de entrada, y que por lo general se llama n, o N. (Obviamente eso no siempre es cierto problems problemas con gráficos se caracterizan a menudo en números de vértices, V, y el número de aristas, E; pero por ahora, vamos a hablar de listas de objetos, con N objetos en el lista.)

Decimos que un problema "es grande-Oh de (alguna función de N)" si y solo si :

Para todos N > algunos N_0 arbitrarios, 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 configurar el problema importa, piense en problemas grandes. Y cuando se piensa en grandes problemas, grande-Oh de (alguna función de N) significa que el tiempo de ejecución es todavía siempre menor que algunas constantes multiplicadas por esa función. Siempre.

En resumen, esa función es un límite superior, hasta un factor constante.

Entonces, "big-Oh de log(n)" significa lo mismo que dije anteriormente, excepto que "alguna función de N" es reemplazada por "log(n)."

Entonces, tu problema te dice que pienses en la búsqueda binaria, así que pensemos en eso. Supongamos que tiene, digamos, una lista de N elementos que se ordenan en aumento orden. Desea averiguar si existe algún número dado en esa lista. Una forma de hacer lo que es no una búsqueda binaria es simplemente escanear cada elemento de la lista y ver si es su número de destino. Es posible que tenga suerte y lo encuentre en el primer intento. Pero en el peor de los casos, comprobarás N veces diferentes. Esto no es búsqueda binaria, y no es big-Oh de log(N) porque no hay manera de forzarlo en los criterios que esbozamos arriba.

Puede elegir esa constante arbitraria para ser 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. Usted puede elegir c=100, o 1000, o un gazillion, y usted todavía será capaz de encontrar algunos N que viola ese requisito. En otras palabras, no hay N_0.

Si hacemos una búsqueda binaria, sin embargo, elegimos el elemento central y hacemos una comparación. Luego tiramos la mitad de los números, y lo hacemos de nuevo, y otra vez, y así sucesivamente. Si su N = 32, solo puede hacerlo alrededor de 5 veces, que es log (32). Si su N = 64, solo puede hacer esto alrededor de 6 veces, etc. Ahora puede elegir esa constante arbitraria c, de tal manera que el requisito siempre se cumple para valores grandes de N.

Con todo ese fondo, lo que O(log(N)) generalmente significa es que tienes alguna manera de hacer algo simple, lo que reduce el tamaño del problema a la mitad. Al igual que la búsqueda binaria está haciendo arriba. Una vez que se corta el problema en la mitad, puedes cortarla por la mitad otra vez, y otra vez, 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 tiempo O(log(N)). Así que, por ejemplo, no puedes mezclar tus dos listas en una lista grande, a menos que también puedas encontrar una manera de hacerlo en tiempo O(log(N)).

(NOTA: Casi siempre, Log(N) significa log-base-dos, que es lo que asumo arriba.)

En la siguiente solución, todas las líneas con una llamada recursiva se realizan en la mitad de los tamaños dados de los sub-arrays de X e Y. Otras líneas se hacen en un tiempo constante. La función recursiva es T(2n)=T(2n/2)+c=T(n)+c=O(lg(2n))=O(lgn).

Se comienza con la MEDIANA(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 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.

Todavía no puedo comentar... 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 son verdaderas, por lo que la MEDIANA(X, p, q, Y, j, k) cortará ambos cincos. Estas son secuencias no decrecientes, no todos los valores son distintos.

También pruebe este ejemplo de longitud par con valores distintos:

X = 1 3 4 7
Y = 2 5 6 8

Ahora la MEDIANA(X, p, q, Y, j+1, k) cortará los cuatro.

En su lugar ofrezco este algoritmo, lo llamo con MEDIANA (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)
}

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

1. ¿Cómo representas un número?

Tomemos el número X = 245436. Esta notación de "245436" contiene información implícita. Making that information explicit:

X = 2 * 10 ^ 5 + 4 * 10 ^ 4 + 5 * 10 ^ 3 + 4 * 10 ^ 2 + 3 * 10 ^ 1 + 6 * 10 ^ 0

Que es la expansión decimal del número. Por lo tanto, la cantidad mínima de información necesitamos representar este número es 6 dígitos. Esto no es coincidencia, ya que cualquier número menor que 10^d puede ser representado en d dígitos.

Entonces, ¿cuántos dígitos se requieren para representar X? Eso es igual al exponente más grande 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 = suelo (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 buscar 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 de forma única un valor en un rango entre 0 y N-1 = log(N) dígitos.

Esto implica que, cuando se le pide que busque un número en la línea entera, que va desde 0 a N - 1, necesitamos al menos log (N) intenta encontrarlo. ¿Por qué? Cualquier algoritmo de búsqueda tendrá que elegir un dígito tras 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 tomadas para buscar un número en un espacio de tamaño N es log (N).

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

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

Cuando se le pide ordenar un conjunto de números A en una matriz B, esto es lo que parece- >

Elementos permutados

Cada elemento en el array original tiene que ser asignado a su índice correspondiente en el array ordenado. Por lo tanto, para el primer elemento, tenemos n puestos. Para encontrar correctamente el índice correspondiente en este rango de 0 a n-1, necesitamos operaciones log 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) + ... + registro(1)

el Uso de log(a) + log(b) = log(a * b),

==> log(n!)

Esto puede ser aproximada a nlog(n) - n.
Que es O(n*log(n))!

De ahí que concluyamos que no puede haber ningún algoritmo de ordenación que pueda hacer 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 log(n) aparecer tan a menudo 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é el log (n) aparece tan a menudo durante el análisis de complejidad del algoritmo?