Intuição algorítmica para complexidade logarítmica

60

Acredito que possuo uma compreensão razoável de complexidades como , e .Θ ( n ) Θ ( n 2 )O(1)Θ(n)Θ(n2)

Em termos de lista, é uma pesquisa constante, portanto, está apenas obtendo o cabeçalho da lista. é onde eu andaria na lista inteira, e caminha pela lista uma vez para cada elemento da lista.Θ ( n ) Θ ( n 2 )O(1)Θ(n)Θ(n2)

Existe uma maneira intuitiva semelhante de entender além de apenas saber que ela está em algum lugar entre e ?O ( 1 ) Θ ( n )Θ(logn)O(1)Θ(n)

Khanzor
fonte
8
log n é para "procurar": pense busca binária
Suresh
2
Usar para fazer esta pergunta está incorreto, pois apenas indica um limite superior. Por exemplo, o tempo constante é . seria mais apropriado. Veja a meta questão: meta.cs.stackexchange.com/questions/182/…O ( log n ) θOO(logn)θ
Aryabhata
11
Mais informações sobre SO: o que significa exatamente? O(logn).
Ran G.
Uma pequena observação: nas configurações clássicas da Máquina de Turing, todos os algoritmos são , pois precisam ler cada símbolo da entrada pelo menos uma vez. A pesquisa binária pode ser feita em porque temos a promessa de que a lista está classificada, por exemplo. O ( log n )Ω(n)O(logn)
chazisop
11
Uma contribuição tardia: por definição, o logaritmo base de um número é apenas o número de vezes que você multiplica por si só para obter . . Por exemplo, . Então, se você tem um número e deseja descobrir o quecontinue dividindo por até chegar a (assumindo que é uma potência de por simplicidade). O número de divisões é igual a . Os algoritmos que exibem esse comportamento de divisão têm tempos de execução emn b n b l = nbnbnbl=nl=logb(n)n l o g b ( n ) = ? b 1 n b l o g b ( n ) O ( l o g ( n ) )23=8log2(8)=3nlogb(n)=?b1nblogb(n)O(log(n)).
Saadtaame

Respostas:

54

A complexidade geralmente é conectada à subdivisão. Ao usar listas como exemplo, imagine uma lista cujos elementos sejam classificados. Você pode pesquisar nessa lista em - na verdade, você não precisa examinar cada elemento devido à natureza classificada da lista.O ( log n )Θ(logn)O(logn)

Se você olhar para o elemento no meio da lista e compará-lo com o elemento que procura, poderá dizer imediatamente se ele fica na metade esquerda ou direita da matriz. Em seguida, você pode pegar esta metade e repetir o procedimento até encontrá-la ou chegar a uma lista com 1 item que você compara trivialmente.

Você pode ver que a lista efetivamente divide pela metade cada etapa. Isso significa que, se você obtiver uma lista de tamanho , as etapas máximas necessárias para alcançar a lista de um item serão . Se você tiver uma lista de itens, precisará de apenas etapas; para uma lista de precisará de apenas etapas, etc.5 128 = 2 7 7 1024 = 2 10 10325128=2771024=21010

Como você pode ver, o expoente em sempre mostra o número de etapas necessárias. O logaritmo é usado para "extrair" exatamente esse número do expoente, por exemplo . Também generaliza para listar comprimentos que não são potências de dois comprimentos.2 n log 2 2 10 = 10n2nlog2210=10

Karel Petranek
fonte
4
Note-se que isso ocorre apenas O(log n)se a lista tiver acesso aleatório em tempo constante. Em implementações de lista mais típicas (listas vinculadas), isto éO(n log n)
asm
11
A pesquisa binária não funciona em listas por falta de ponteiros; geralmente é feito em matrizes.
Raphael
A pesquisa binária funciona bem em listas. É apenas inútil por ser muito mais complicado do que o necessário / útil / prático.
Anton
@AndrewMyers A pesquisa de uma lista vinculada é mais precisaO(n)
phant0m
11
@ phant0m Sim, demorei um pouco para descobrir que ele está assumindo que você está saindo da posição atual em vez de atravessar desde o início todas as vezes.
asm
38

Em termos de árvores (balanceadas) (por exemplo, árvore binária, então todos os 's são a base 2):log

  • Θ(1) está obtendo a raiz da árvore
  • Θ(logn) é um passeio da raiz às folhas
  • Θ(n) está atravessando todos os nós da árvore
  • Θ(n2) são ações em todos os subconjuntos dois nós na árvore, por exemplo, o número de caminhos diferentes entre dois nós.
  • k kΘ(nk) - generalização do anterior para qualquer subconjunto de nós (para uma constante )kk
  • k = 1 , 2 , , nΘ(2n) são ações em todos os subconjuntos possíveis de nós (subconjuntos de todos os tamanhos possíveis, ou seja, .). Por exemplo, o número de diferentes subárvores da árvore.k=1,2,,n
Tocou.
fonte
5
Para adicionar a isso, a intuição para vem de duas coisas: 1.) A recorrência e 2.) Pesquisa binária em algo do tamanho ou seja, uma pesquisa binária na altura da árvore. T ( n ) = T ( Θ(loglogn)log(n)T(n)=T((n))+1log(n)
Mcorley
17

Para que seja possível, é necessário reduzir o tamanho do problema proporcionalmente em uma quantia arbitrária em relação a com uma operação de tempo constante.nO(logn)n

Por exemplo, no caso de pesquisa binária, você pode reduzir o tamanho do problema pela metade a cada operação de comparação.

Agora, você precisa reduzir o tamanho do problema pela metade, na verdade não. Um algoritmo é mesmo que possa reduzir o espaço de pesquisa do problema em 0,0001%, desde que a porcentagem e a operação que ele usa para reduzir o tamanho do problema permaneçam constantes, é um algoritmo, não será um algoritmo rápido, mas ainda é com uma constante muito grande. (Supondo que estamos falando de com um log de base 2)O ( log n ) O ( log n ) log nO(logn)O(logn)O(logn)logn

Ken Li
fonte
11
O que seria se a 'quantidade reduzida' não fosse constante?
Svish
@Svish Se você puder reduzir o problema a uma taxa positiva, ainda será um algoritmo , embora provavelmente não seja mais um limite restrito. Taxa negativa é difícil de dizer. A suposição foi feita para tornar a resposta bastante simples neste caso, uma vez que esta pergunta tem seu próprio mérito, você é convidado a fazer isso como uma pergunta por si só. O(logn)
Ken Li
Sim, eu queria dizer que o espaço de pesquisa do problema sempre diminuía, mas não necessariamente a uma taxa constante. Estava pensando no seu "contanto que a porcentagem e a operação que ele usa para reduzir o tamanho do problema permaneçam constantes, é um algoritmo O (log n)"; se tivesse um nome diferente se a porcentagem não fosse constante.
#
8

Pense no algoritmo para converter o número decimal em binárion

while n != 0:
   print n%2, 
   n = n/2

Esse whileloop é executado vezes.log(n)

Pratik Deoghare
fonte
11
Certamente este programa faz loops vezes, mas geralmente quando falamos em complexidade, é o tamanho da sua entrada. Aqui o tamanho da sua entrada já está , então eu diria que este programa só é linear (em )O ( f ( s ) ) s s = log n O ( s )lognO(f(s))ss=lognO(s)
Jmad
@jmad Certo. Mas este exemplo fornece intuição no log (n).
Pratik Deoghare 21/03
@ jmad Eu poderia ter usado o algoritmo para gerar números aleatórios também, mas queria o mais simples possível.
Pratik Deoghare 21/03
8

Sim, está entre e , mas é mais próximo de que . O que é ? A função log é a função inversa da exponenciação. Deixe-me começar com a exponenciação e você deve ter uma idéia melhor do que é o logaritmo.1 n 1 n log ( n )log(n)1n1nlog(n)

Considere dois números, e . é multiplicado por si mesmo vezes. Você pode, com algum esforço, contar números, mas pode contar ? Aposto que você não pode. Por quê? é um número tão grande que é maior que o número de todos os átomos no universo. Reflita sobre isso por um momento. É um número tão grande que permite que você dê um nome (número) a cada átomo. E o número de átomos em sua unha é provavelmente da ordem de bilhões. deve ser suficiente para qualquer pessoa (trocadilho intencional :)).2 100 2 100 2 100 100 2 100 2 100 2 100100210021002100100210021002100

Agora, entre os dois números, e , é o logaritmo de (na base ). é comparativamente um número tão pequeno que . Alguém deveria ter itens diferentes em sua casa. Mas, é bom o suficiente para o universo. Pense em casa versus universo ao pensar em e .2 100 100 2 100 2 100 2 100 100 2 100 log ( n ) n10021001002100210021001002100log(n)n

De onde vêm a exponenciação e os logaritmos? Por que eles têm tanto interesse em ciência da computação? Você pode não perceber, mas a exponentação está em toda parte. Você pagou juros no cartão de crédito? Você acabou de pagar um universo por sua casa (não é tão ruim, mas a curva se encaixa). Eu gosto de pensar que a exponenciação vem da regra do produto, mas outros são bem-vindos para dar mais exemplos. Qual é a regra do produto, você pode perguntar; E eu responderei.

Digamos que você tenha duas cidades e , e há duas maneiras de ir entre elas. Qual é o número de caminhos entre eles? Dois. Isso é trivial. Agora diga, existe outra cidade , e você pode ir de para de três maneiras. Quantos caminhos existem entre e agora? Seis, certo? Como você conseguiu isso? Você os contou? Ou você os multiplicou? De qualquer maneira, é fácil ver que ambas as formas dão um resultado semelhante. Agora, se você adicionar uma cidade que pode ser acessada a partir de de quatro maneiras, quantas maneiras existem entre eB C B C A C D C A D 2 3 4 24 2 10 1024 2 10 10 10 2 10 10 1024ABCBCACDCAD? Conte se você não confia em mim, mas é igual a que é . Agora, se houver dez cidades e houver dois caminhos de uma cidade para a próxima, eles serão organizados como se fossem uma linha reta. Quantos caminhos existem do começo ao fim? Multiplique-os se não confiar em mim, mas vou lhe dizer que existem , que é . Veja que é resultado exponencial de e é o logaritmo de . é um número pequeno em comparação com .2342421010242101010210101024

A função do logaritmo é que é (observe que é a base do logaritmo). Se você multipy consigo mesmo vezes (observe que é a base do logaritmo), obtém . é tão pequeno, tão pequeno em comparação com , que é o tamanho da sua casa onde é o tamanho do universo.n n 2 n 2 log b ( n ) b b n log ( n ) n nlog2(n)nn2n2logb(n)bbnlog(n)nn

Em uma nota prática, as funções executam muito semelhante às funções constantes. Eles crescem com , mas crescem muito lentamente. Se você otimizou um programa para ser executado no tempo logarítmico que estava demorando um dia antes, provavelmente o executará na ordem de minutos. Verifique você mesmo com problemas no Project Euler.nlog(n)n

Ravi
fonte
3
Embora bem escrita, esta resposta contém quase nenhuma informação além de " é realmente pequeno". log(n)
Raphael
3
Eu estava tentando dar uma intuição de quão pequeno é.
Ravi
5

Para continuar seu tema, é como adivinhar repetidamente onde x está na lista e receber "alto" ou "baixo" (em termos de índice).O(logn)x

Ainda é baseado no tamanho da lista, mas você só precisa visitar uma fração dos elementos.

dpatchery
fonte
4

Se temos um algoritmo de divisão e conquista , e fazemos apenas uma chamada recursiva para um subproblema, e é o segundo caso no teorema mestre , ou seja, a complexidade do tempo da parte não recursiva é , então o a complexidade do algoritmo será Θ ( lg k + 1 n ) .Θ(lgkn)Θ(lgk+1n)

Θ(1)lgn

O algoritmo de busca binária é o exemplo clássico.

Kaveh
fonte
1

A intuição é quantas vezes você pode reduzir pela metade um número, digamos n, antes que ele seja reduzido a 1 seja O (lg n).

Para visualizar, tente desenhá-lo como uma árvore binária e conte o número de níveis, resolvendo essa progressão geométrica.

2^0+2^1+...+2^h = n
user1234
fonte
lognn