O que a complexidade de tempo O (log n) realmente significa?

Maaz 28 de maio de 2017

Conhecer a complexidade dos algoritmos de antemão é uma coisa, e outra coisa é saber a razão por trás disso ser assim.

Se você é um graduado de CS ou alguém que quer lidar com problemas de otimização de forma eficaz, isso é algo que você deve entender se você quiser usar seu conhecimento para resolver problemas reais.

Complexidades como O (1) e O (n) são simples e diretas. O (1) significa uma operação que é feita para alcançar um elemento diretamente (como um dicionário ou uma tabela de hash), O (n) significa que primeiro teríamos que procurá-lo verificando n elementos, mas o que poderia O (log n) possivelmente significar?

Um local onde você pode ter ouvido falar sobre complexidade de tempo O (log n) na primeira vez é o algoritmo de busca binária. Portanto, deve haver algum tipo de comportamento que o algoritmo esteja mostrando para receber uma complexidade de log n. Vamos ver como isso funciona.

Como a pesquisa binária tem uma eficiência de melhor caso de O (1) e a pior das hipóteses (caso médio) de eficiência de O (log n), veremos um exemplo do pior caso. Considere uma matriz ordenada de 16 elementos.

Para o pior caso, digamos que queremos procurar o número 13.

Uma matriz classificada de 16 elementosSelecionando o elemento do meio como pivô (comprimento / 2) Como 13 é menor que pivô, removemos a outra metade da matrizRependendo o processo para localizar o elemento do meio para cada subarray

Você pode ver que, após cada comparação com o termo do meio, nosso intervalo de pesquisa é dividido em metade do intervalo atual.

Então, para alcançar um elemento de um conjunto de 16 elementos, tivemos que dividir o array 4 vezes,

Nós podemos dizer que,

Fórmula Simplificada

Da mesma forma, para n elementos,

GeneralizationSeparating o poder para o numerador e denominadorMultiplicação de ambos os lados por 2 ^ kFinal result

Agora, vamos olhar para a definição de logaritmo, ele diz que

Uma quantidade representando a potência para a qual um número fixo (a base) deve ser elevado para produzir um determinado número.

O que torna nossa equação em

Forma logarítmica

Então, o log n realmente significa alguma coisa, não é? Um tipo de comportamento que mais nada pode representar.

Bem, espero que a ideia esteja clara em sua mente. Ao trabalhar no campo da ciência da computação, é sempre útil conhecer essas coisas (e é bastante interessante também). Quem sabe, talvez você seja o único em sua equipe que é capaz de encontrar uma solução otimizada para um problema, só porque você sabe com o que está lidando. Boa sorte!

Hacker Noon é como os hackers começam suas tardes. Nós somos uma parte da família @AMI . Estamos agora aceitando inscrições e felizes em discutir oportunidades de publicidade e patrocínio .

Se você gostou dessa história, recomendamos que leia as últimas notícias sobre tecnologia e as tendências das histórias sobre tecnologia . Até a próxima vez, não tome as realidades do mundo como garantidas!

Texto original en inglés.