If you're seeing this message, it means we're having trouble loading external resources on our website.

Se você está atrás de um filtro da Web, certifique-se que os domínios *.kastatic.org e *.kasandbox.org estão desbloqueados.

Conteúdo principal

Tempo de execução da busca binária

Sabemos que a busca linear em um array de n elementos pode precisar fazer até n suposições. Você provavelmente já tem uma ideia intuitiva de que a busca binária faz menos suposições do que a busca linear. Você pode até ter percebido que a diferença entre o pior número possível de suposições da busca linear e da busca binária se torna mais evidente conforme o tamanho do array aumenta. Vamos ver como analisar o número máximo de suposições que a busca binária faz.
A ideia principal é que quando a busca binária faz uma suposição incorreta, a porção do array que contém as suposições razoáveis se reduz pelo menos pela metade. Se a porção razoável tiver 32 elementos, então uma suposição incorreta a corta para ter no máximo 16. A busca binária divide o tamanho da porção razoável a cada suposição incorreta.
Se começarmos com um array de comprimento 8, então as suposições incorretas reduzem o tamanho da porção razoável para 4, para 2 e então para 1. Quando a porção razoável contém apenas um elemento, não ocorrem mais suposições. A suposição para a porção com 1 elemento está correta ou incorreta, e então terminamos. Então, com um array de comprimento 8, a busca binária precisa de no máximo quatro suposições.
O que você acha que aconteceria com um array de 16 elementos? Se você disse que a primeira suposição eliminaria pelo menos 8 elementos, de forma que restassem no máximo 8 elementos, você está começando a entender. Então, com 16 elementos, precisamos de no máximo cinco suposições.
Você já deve estar começando a ver o padrão. Sempre que dobramos o tamanho do array, precisamos de, no máximo, mais uma suposição. Suponha que precisamos de no máximo m suposições para um array de comprimento n. Então, para um array de comprimento 2, n, a primeira suposição reduz a porção razoável do array para o tamanho n, e no máximo m suposições terminam o processo, nos dando um total de no máximo m, plus, 1 suposições.
Vamos analisar o caso geral de um array de tamanho n. Podemos expressar o número de chutes, no pior cenário, como o "número de vezes que podemos reduzir pela metade de forma repetida, começando em n, até conseguir o valor 1, mais um." Mas essa é uma forma inconveniente de escrever.
Felizmente, há uma função matemática que significa a mesma coisa que o número de vezes que reduzimos pela metade de forma repetida, começando em n, até conseguirmos o valor de 1: o logarítmo de n na base 2, que normalmente é escrito como log, start base, 2, end base, n, mas você também pode encontrá-lo escrito como \lg, n em textos de ciência da computação. (Quer fazer uma revisão sobre logaritmos? Saiba mais aqui).
Aqui está uma tabela que mostra os logaritmos de base 2 de diversos valores de n:
nlog, start base, 2, end base, n
10
21
42
83
164
325
646
1287
2568
5129
102410
1.048.57620
2.097.15221
Podemos visualizar essa mesma tabela na forma de um gráfico:
Gráfico de log de n na base 2 para valores maiores
Dando zoom nos valores mais baixos de n:
Gráfico de log de n na base 2 para valores menores
A função logarítmica cresce muito lentamente. As funções logarítmicas são o inverso das exponenciais, que crescem muito rapidamente, portanto, se log, start base, 2, end base, n, equals, x, então n, equals, 2, start superscript, x, end superscript. Por exemplo, como log, start base, 2, end base, 128, equals, 7, sabemos que 2, start superscript, 7, end superscript, equals, 128.
Isso facilita o cálculo do tempo de execução de um algoritmo de busca binária em n que é exatamente uma potência de 2. Se n for 128, a busca binária vai precisar de, no máximo, 8 (log, start base, 2, end base, 128, plus, 1) tentativas.
E se n não for uma potência de 2? Nesse caso, podemos olhar a potência de 2 mais baixa. Para um array de tamanho 1.000, a potência de 2 mais próxima abaixo disso é 512, que é igual a 2, start superscript, 9, end superscript. Assim, podemos estimar que log, start base, 2, end base, 1, point, 000 é um número maior que 9 e menor que 10, ou usar uma calculadora para verificar que é aproximadamente 9,97. Somar um a esse valor resulta em 10,97. No caso de um número decimal, arredondamos para baixo para encontrar o número verdadeiro de tentativas. Portanto, para um array de 1.000 elementos, uma busca binária precisaria de, no máximo, 10 tentativas.
Para o catálogo estelar Tycho-2, que contém 2.539.913 estrelas, a potência mais próxima abaixo disso é de 2 é 2, start superscript, 21, end superscript (que é 2.097.152), então precisaríamos de, no máximo, 22 tentativas. Isso é muito melhor do que uma busca linear!
Compare n versus log, start base, 2, end base, n abaixo:
Gráfico que compara n e log de n na base 2
No próximo tutorial, vamos ver como os cientistas da computação caracterizam os tempos de execução das buscas linear e binária, usando uma notação que destila a parte mais importante do tempo de execução e descarta as partes menos importantes.

Este conteúdo é uma colaboração entre os professores de ciência da computação da Universidade de Dartmouth, Thomas Cormen e Devin Balkcom, juntamente com a equipe do currículo de computação da Khan Academy. O conteúdo é licenciado CC-BY-NC-SA.

Quer participar da conversa?

  • Avatar blobby green style do usuário Erica Almeida
    Não entendi muito bem o exercício anterior...tentei usar o método Math.trunc mas só funcionou com o Math.floor...
    (2 votos)
    Avatar Default Khan Academy avatar do usuário
  • Avatar blobby green style do usuário Cleitonjss
    o desafio anterior foi feito corretamente ! porem nao concretizou! porque
    (2 votos)
    Avatar Default Khan Academy avatar do usuário
  • Avatar mr pink green style do usuário produtor.marcelorocha
    No parágrafo acima: "Se começarmos com um array de comprimento 8, então as suposições incorretas reduzem o tamanho da porção razoável para 4, para 2 e então para 1. Quando a porção razoável contém apenas um elemento, não ocorrem mais suposições. A suposição para a porção com 1 elemento está correta ou incorreta, e então terminamos. Então, com um array de comprimento 8, a busca binária precisa de no máximo quatro suposições."

    Se a complexidade da busca binária é log n (na base 2), e o texto acima cita um array de 8 elementos, ou seja, n = 8. O número máximo de suposições não seria igual a log 8 (na base 2), que seria igual a 3? Se o meu raciocínio estiver correto, o mesmo erro ocorre no parágrafo seguinte, onde o texto fala que o máximo de suposições para um array de 16 elementos é 5. Esse seria o valor, no pior caso, de um array de 17 a 32 elementos, inclusive.
    (2 votos)
    Avatar Default Khan Academy avatar do usuário
  • Avatar blobby green style do usuário Marcus Becker
    Essa parte do texto não foi traduzida: "For example, because lg 128 = 7..."
    (2 votos)
    Avatar Default Khan Academy avatar do usuário
  • Avatar ohnoes default style do usuário debora dias
    não entendi o exercício anterior, alguma dica? onde fica o curso de JS?
    (1 voto)
    Avatar Default Khan Academy avatar do usuário
Você entende inglês? Clique aqui para ver mais debates na versão em inglês do site da Khan Academy.