Meu conhecimento de big-O é limitado, e quando os termos de log aparecem na equação, fico ainda mais confuso.

Alguém pode me explicar em termos simples o que é um O(log n)algoritmo? De onde vem o logaritmo?

Isso surgiu especificamente quando eu estava tentando resolver esta questão prática intermediária:

Seja X (1..n) e Y (1..n) contendo duas listas de inteiros, cada uma classificada em ordem não decrescente. Forneça um algoritmo de tempo O (log n) para encontrar a mediana (ou o enésimo menor inteiro) de todos os 2n elementos combinados. Para ex, X = (4, 5, 7, 8, 9) e Y = (3, 5, 8, 9, 10), então 7 é a mediana da lista combinada (3, 4, 5, 5, 7 , 8, 8, 9, 9, 10). [Dica: use conceitos de pesquisa binária]

Eu tenho que concordar que é muito estranho a primeira vez que você vê um algoritmo O (log n) ... de onde diabos vem esse logaritmo? No entanto, descobriu-se que há várias maneiras diferentes de fazer com que um termo de log apareça em notação big-O. Aqui estão alguns:

Dividindo repetidamente por uma constante

Pegue qualquer número n; digamos, 16. Quantas vezes você pode dividir n por dois antes de obter um número menor ou igual a um? Para 16, temos que

16 / 2 = 8
 8 / 2 = 4
 4 / 2 = 2
 2 / 2 = 1

Observe que isso acaba levando quatro etapas para ser concluído. Curiosamente, também temos esse log ₂ 16 = 4. Hmmm ... e 128?

128 / 2 = 64
 64 / 2 = 32
 32 / 2 = 16
 16 / 2 = 8
  8 / 2 = 4
  4 / 2 = 2
  2 / 2 = 1

Isso levou sete etapas e log ₂ 128 = 7. Isso é uma coincidência? Não! Há um bom motivo para isso. Suponha que dividamos um número n por 2 i vezes. Então obtemos o número n / 2 ⁱ . Se quisermos resolver o valor de i onde esse valor é no máximo 1, obtemos

n / 2 ⁱ ≤ 1

n ≤ 2 ⁱ

log ₂ n ≤ i

Em outras palavras, se pegarmos um inteiro i tal que i ≥ log ₂ n, então, depois de dividir n pela metade i vezes, teremos um valor que é no máximo 1. O menor i para o qual isso é garantido é aproximadamente log ₂ n, então se tivermos um algoritmo que divide por 2 até que o número fique suficientemente pequeno, podemos dizer que ele termina em O (log n) etapas.

Um detalhe importante é que não importa por qual constante você está dividindo n (contanto que seja maior que um); se você dividir pela constante k, levará log _k n passos para chegar a 1. Portanto, qualquer algoritmo que divide repetidamente o tamanho da entrada por alguma fração precisará de O (log n) iterações para terminar. Essas iterações podem levar muito tempo e, portanto, o tempo de execução da rede não precisa ser O (log n), mas o número de etapas será logarítmico.

Então, de onde vem isso? Um exemplo clássico é a pesquisa binária , um algoritmo rápido para pesquisar um valor em uma matriz classificada. O algoritmo funciona assim:

• Se a matriz estiver vazia, retorne que o elemento não está presente na matriz.
• De outra forma:
  • Observe o elemento do meio da matriz.
  • Se for igual ao elemento que estamos procurando, retorna sucesso.
  • Se for maior do que o elemento que procuramos:
    • Jogue fora a segunda metade da matriz.
    • Repetir
  • Se for menor que o elemento que procuramos:
    • Jogue fora a primeira metade da matriz.
    • Repetir

Por exemplo, para pesquisar 5 na matriz

1   3   5   7   9   11   13

Primeiro, veríamos o elemento do meio:

1   3   5   7   9   11   13
            ^

Como 7> 5, e como o array está classificado, sabemos com certeza que o número 5 não pode estar na metade posterior do array, então podemos simplesmente descartá-lo. Isso deixa

1   3   5

Então, agora olhamos para o elemento do meio aqui:

1   3   5
    ^

Como 3 <5, sabemos que 5 não pode aparecer na primeira metade da matriz, então podemos lançar a primeira metade da matriz para sair

        5

Novamente, olhamos para o meio desta matriz:

        5
        ^

Como esse é exatamente o número que estamos procurando, podemos relatar que 5 está de fato na matriz.

Então, quão eficiente é isso? Bem, em cada iteração estamos jogando fora pelo menos metade dos elementos restantes do array. O algoritmo para assim que o array fica vazio ou encontramos o valor que desejamos. Na pior das hipóteses, o elemento não está lá, então continuamos reduzindo o tamanho da matriz pela metade até ficarmos sem elementos. Quanto tempo isso leva? Bem, uma vez que continuamos cortando o array pela metade repetidamente, terminaremos em no máximo O (log n) iterações, uma vez que não podemos cortar o array pela metade mais do que O (log n) vezes antes de executar fora dos elementos da matriz.

Algoritmos que seguem a técnica geral de dividir e conquistar (cortar o problema em partes, resolver essas partes e, em seguida, recompor o problema) tendem a ter termos logarítmicos por este mesmo motivo - você não pode continuar cortando algum objeto metade mais do que O (log n) vezes. Você pode querer ver a classificação por mesclagem como um ótimo exemplo disso.

Processando valores um dígito de cada vez

Quantos dígitos há no número de base 10 n? Bem, se houver k dígitos no número, então teríamos que o maior dígito é algum múltiplo de 10 ^k . O maior número de k dígitos é 999 ... 9, k vezes, e isso é igual a 10 ^{k + 1} - 1. Consequentemente, se sabemos que n contém k dígitos, então sabemos que o valor de n é no máximo 10 ^{k + 1} - 1. Se quisermos resolver para k em termos de n, obtemos

n ≤ 10 ^{k + 1} - 1

n + 1 ≤ 10 ^{k + 1}

log ₁₀ (n + 1) ≤ k + 1

(log ₁₀ (n + 1)) - 1 ≤ k

Do qual obtemos que k é aproximadamente o logaritmo de base 10 de n. Em outras palavras, o número de dígitos em n é O (log n).

Por exemplo, vamos pensar sobre a complexidade de adicionar dois números grandes que são muito grandes para caber em uma palavra de máquina. Suponha que tenhamos esses números representados na base 10, e chamaremos os números m e n. Uma maneira de adicioná-los é através do método da escola primária - escreva os números um dígito de cada vez e depois trabalhe da direita para a esquerda. Por exemplo, para adicionar 1337 e 2065, começaríamos escrevendo os números como

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

Adicionamos o último dígito e carregamos o 1:

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

Em seguida, adicionamos o penúltimo ("penúltimo") dígito e carregamos o 1:

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

Em seguida, adicionamos o terceiro ao último ("antepenúltimo") dígito:

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

Finalmente, adicionamos o quarto ao último ("preantepenúltimo" ... eu amo o inglês) dígito:

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

Agora, quanto trabalho fizemos? Fazemos um total de O (1) trabalho por dígito (ou seja, uma quantidade constante de trabalho), e há O (max {log n, log m}) dígitos totais que precisam ser processados. Isso dá um total de complexidade O (max {log n, log m}), porque precisamos visitar cada dígito nos dois números.

Muitos algoritmos obtêm um termo O (log n) por trabalharem um dígito por vez em alguma base. Um exemplo clássico é a classificação radix , que classifica inteiros um dígito por vez. Existem muitos tipos de classificação de raiz, mas eles geralmente são executados no tempo O (n log U), onde U é o maior número inteiro possível que está sendo classificado. A razão para isso é que cada passagem da classificação leva O (n) tempo, e há um total de O (log U) iterações necessárias para processar cada um dos O (log U) dígitos do maior número sendo classificado. Muitos algoritmos avançados, como o algoritmo de caminhos mais curtos de Gabow ou a versão de escala do algoritmo de fluxo máximo de Ford-Fulkerson , têm um termo de log em sua complexidade porque trabalham um dígito por vez.

Quanto à sua segunda pergunta sobre como resolver esse problema, você pode querer olhar para esta questão relacionada, que explora um aplicativo mais avançado. Dada a estrutura geral dos problemas que são descritos aqui, agora você pode ter uma noção melhor de como pensar sobre os problemas quando sabe que há um termo de registro no resultado, portanto, não aconselho olhar para a resposta até que você a dê algum pensamento.

Espero que isto ajude!

Quando falamos sobre descrições big-Oh, geralmente estamos falando sobre o tempo que leva para resolver problemas de um determinado tamanho . E geralmente, para problemas simples, esse tamanho é apenas caracterizado pelo número de elementos de entrada, e isso geralmente é chamado de n ou N. (Obviamente, isso nem sempre é verdade - problemas com gráficos são frequentemente caracterizados em números de vértices, V e número de arestas, E; mas, por enquanto, falaremos sobre listas de objetos, com N objetos nas listas.)

Dizemos que um problema "é grande (alguma função de N)" se e somente se :

Para todo N> algum N_0 arbitrário, existe alguma constante c, de modo que o tempo de execução do algoritmo é menor do que a constante c vezes (alguma função de N.)

Em outras palavras, não pense em pequenos problemas onde a "sobrecarga constante" de configurar o problema é importante, pense em grandes problemas. E quando se pensa em grandes problemas, big-Oh of (alguma função de N) significa que o tempo de execução ainda é sempre menor do que algumas constantes vezes essa função. Sempre.

Em suma, essa função é um limite superior, até um fator constante.

Então, "big-Oh of log (n)" significa a mesma coisa que eu disse acima, exceto "alguma função de N" é substituída por "log (n)."

Então, seu problema diz para você pensar sobre a pesquisa binária, então vamos pensar sobre isso. Vamos supor que você tenha, digamos, uma lista de N elementos classificados em ordem crescente. Você deseja descobrir se algum determinado número existe nessa lista. Uma maneira de fazer o que não é uma pesquisa binária é apenas examinar cada elemento da lista e ver se é o seu número de destino. Você pode ter sorte e encontrá-lo na primeira tentativa. Mas, no pior caso, você verificará N vezes diferentes. Esta não é uma pesquisa binária e não é grande (N) porque não há como forçá-la aos critérios que esboçamos acima.

Você pode escolher essa constante arbitrária como c = 10 e, se sua lista tiver N = 32 elementos, tudo bem: 10 * log (32) = 50, que é maior do que o tempo de execução de 32. Mas se N = 64 , 10 * log (64) = 60, que é menor que o tempo de execução de 64. Você pode escolher c = 100, ou 1000, ou um zilhão, e ainda será capaz de encontrar algum N que viola esse requisito. Em outras palavras, não há N_0.

Se fizermos uma pesquisa binária, no entanto, escolhemos o elemento do meio e fazemos uma comparação. Então jogamos fora metade dos números e fazemos isso de novo, e de novo, e assim por diante. Se seu N = 32, você só pode fazer isso cerca de 5 vezes, que é log (32). Se seu N = 64, você só pode fazer isso cerca de 6 vezes, etc. Agora você pode escolher essa constante arbitrária c, de modo que o requisito seja sempre atendido para valores grandes de N.

Com todo esse histórico, o que O (log (N)) geralmente significa é que você tem alguma maneira de fazer uma coisa simples, que reduz o tamanho do seu problema pela metade. Assim como a pesquisa binária está fazendo acima. Depois de cortar o problema pela metade, você pode cortá-lo pela metade novamente, e novamente, e novamente. Mas, criticamente, o que você não pode fazer é alguma etapa de pré-processamento que levaria mais tempo do que o tempo O (log (N)). Então, por exemplo, você não pode embaralhar suas duas listas em uma lista grande, a menos que encontre uma maneira de fazer isso no tempo O (log (N)) também.

(NOTA: Quase sempre, Log (N) significa log-base-dois, que é o que presumo acima.)

Na solução a seguir, todas as linhas com uma chamada recursiva são feitas na metade dos tamanhos fornecidos das submatrizes de X e Y. As outras linhas são feitas em um tempo constante. A função recursiva é T (2n) = T (2n / 2) + c = T (n) + c = O (lg (2n)) = O (lgn).

Você começa com 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)

O termo Log aparece com muita frequência na análise da complexidade do algoritmo. Aqui estão algumas explicações:

1. Como você representa um número?

Vamos pegar o número X = 245436. Esta notação de “245436” contém informações implícitas. Tornando essa informação explícita:

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

Qual é a expansão decimal do número. Portanto, a quantidade mínima de informações de que precisamos para representar esse número é de 6 dígitos. Isso não é coincidência, pois qualquer número menor que 10 ^ d pode ser representado em d dígitos.

Então, quantos dígitos são necessários para representar X? Isso é igual ao maior expoente de 10 em X mais 1.

==> 10 ^ d> X
==> log (10 ^ d)> log (X)
==> d * log (10)> log (X)
==> d> log (X) // E o log aparece novamente ...
==> d = floor (log (x)) + 1

Observe também que esta é a maneira mais concisa de denotar o número neste intervalo. Qualquer redução levará à perda de informações, pois um dígito ausente pode ser mapeado para 10 outros números. Por exemplo: 12 * pode ser mapeado para 120, 121, 122,…, 129.

2. Como você procura um número em (0, N - 1)?

Tomando N = 10 ^ d, usamos nossa observação mais importante:

A quantidade mínima de informações para identificar exclusivamente um valor em um intervalo entre 0 a N - 1 = log (N) dígitos.

Isso implica que, quando solicitados a pesquisar um número na linha inteira, variando de 0 a N - 1, precisamos de pelo menos log (N) tentativas para encontrá-lo. Por quê? Qualquer algoritmo de busca precisará escolher um dígito após o outro em sua busca pelo número.

O número mínimo de dígitos que ele precisa escolher é log (N). Portanto, o número mínimo de operações realizadas para pesquisar um número em um espaço de tamanho N é log (N).

Você consegue adivinhar as complexidades de ordem da pesquisa binária, pesquisa ternária ou pesquisa deca?
É O (log (N))!

3. Como você classifica um conjunto de números?

Quando solicitado a classificar um conjunto de números A em uma matriz B, é assim que se parece ->

Elementos Permutados

Cada elemento na matriz original deve ser mapeado para seu índice correspondente na matriz classificada. Portanto, para o primeiro elemento, temos n posições. Para encontrar corretamente o índice correspondente neste intervalo de 0 a n - 1, precisamos ... operações log (n).

O próximo elemento precisa de operações de log (n-1), o próximo log (n-2) e assim por diante. O total chega a ser:

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

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

==> log (n!)

Isso pode ser aproximado de nlog (n) - n.
Que é O (n * log (n))!

Conseqüentemente, concluímos que não pode haver algoritmo de ordenação melhor do que O (n * log (n)). E alguns algoritmos com essa complexidade são os populares Merge Sort e Heap Sort!

Essas são algumas das razões pelas quais vemos log (n) aparecer com tanta frequência na análise de complexidade de algoritmos. O mesmo pode ser estendido para números binários. Fiz um vídeo sobre isso aqui.
Por que log (n) aparece com tanta frequência durante a análise de complexidade do algoritmo?

Felicidades!

Chamamos a complexidade de tempo de O (log n), quando a solução é baseada em iterações sobre n, onde o trabalho realizado em cada iteração é uma fração da iteração anterior, pois o algoritmo trabalha em direção à solução.

Ainda não posso comentar ... necro é! A resposta de Avi Cohen está incorreta, tente:

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

Nenhuma das condições é verdadeira, então MEDIAN (X, p, q, Y, j, k) cortará os cincos. Essas são sequências não decrescentes, nem todos os valores são distintos.

Experimente também este exemplo de comprimento par com valores distintos:

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

Agora MEDIAN (X, p, q, Y, j + 1, k) cortará os quatro.

Em vez disso, ofereço este algoritmo, chame-o de 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)
}