Determinando se um Algoritmo é O (log n)

25

Estou atualizando minha teoria do CS e quero saber como identificar a complexidade de um algoritmo O (log n). Especificamente, existe uma maneira fácil de identificá-lo?

Eu sei que com O (n), você geralmente tem um único loop; O (n ^ 2) é um loop duplo; O (n ^ 3) é um loop triplo, etc. E quanto a O (log n)?

algorithms complexity big-o Atif
fonte
2
stackoverflow.com/questions/749819/... ou isso realmente longa leitura: stackoverflow.com/questions/487258/...
wkl
Ah, esse é o único lugar que eu não parecia :)
Atif

Respostas:

32

Eu sei que com O (n), você geralmente tem um único loop; O (n ^ 2) é um loop duplo; O (n ^ 3) é um loop triplo, etc. E quanto a O (log n)?

Você realmente está fazendo o caminho errado aqui. Você está tentando memorizar qual expressão big-O combina com uma determinada estrutura algorítmica, mas você deve apenas contar o número de operações que o algoritmo requer e compará-lo com o tamanho da entrada. Um algoritmo que faz um loop em toda a entrada tem desempenho O (n) porque executa o loop n vezes, não porque possui um único loop. Aqui está um loop único com desempenho O (log n):

for (i = 0; i < log2(input.count); i++) {
    doSomething(...);
}

Portanto, qualquer algoritmo em que o número de operações necessárias esteja na ordem do logaritmo do tamanho da entrada é O (log n). O importante que a análise big-O diz é como o tempo de execução de um algoritmo muda em relação ao tamanho da entrada: se você duplicar o tamanho da entrada, o algoritmo dará mais um passo (O (log n)) , duas vezes mais etapas (O (n)), quatro vezes mais etapas (O (n ^ 2)) etc.

Ajuda, por experiência própria, que algoritmos que particionam repetidamente sua entrada normalmente tenham 'log n' como um componente de seu desempenho? Certo. Mas não procure o particionamento e chegue à conclusão de que o desempenho do algoritmo é O (log n) - pode ser algo como O (n log n), que é bem diferente.

Caleb
fonte
3
Observe que uma maneira mais coloquial de dizer "na ordem do logaritmo do tamanho" é dizer "na ordem do número de dígitos no tamanho".
@Caleb, a base real do logaritmo não é importante quando se fala de dimensionamento.
@ Caleb falando absolutos não faz sentido com big-O. Uma frase que você pode gostar: quando o número de dígitos dobrar, o número de etapas dobrar.
@ Caleb falando absolutos não faz sentido com big-O. Uma frase que você pode gostar: quando o número de dígitos dobrar, o número de etapas dobrar.
@ ThorbjørnRavnAndersen Sim, é isso que significa "o logaritmo do tamanho". Não tenho certeza de qual é o seu problema com a frase, exceto que você escolheria dizê-la de maneira diferente. Fundamentalmente, acho que concordamos.
Caleb
25

A idéia é que um algoritmo seja: O(log n)se, em vez de percorrer uma estrutura 1 por 1, você divide a estrutura pela metade uma e outra vez e realiza um número constante de operações para cada divisão. Existem algoritmos de busca nos quais o espaço de resposta continua sendo dividido O(log n). Um exemplo disso é a pesquisa binária , em que você continua dividindo uma matriz ordenada ao meio repetidas vezes até encontrar o número.

Nota: Você não precisa necessariamente se dividir em partes iguais.

Casey Patton
fonte
1
E se eu dividir a entrada em duas e depois repetir 2 ^ (n / 2) vezes no restante antes de dividi-la novamente? (É claro que sei o que então, só queria mostrar um exemplo em que essa abordagem simplista falha).
Tamás Szelei
@afish Isso é meio raro. É espetacularmente raro ao pesquisar.
Donal Fellows
1
A teoria do algoritmo @DonalFellows não é uma ciência empírica. E a pergunta não era sobre busca, é apenas que a menção de log nreflexos de busca binária acionados nas pessoas.
Tamás Szelei
2
O particionamento não cria o algoritmo O (log n), mas (geralmente) adiciona um fator de log n ao limite do grande O. Classificações recursivas como heapsort e mergesort são exemplos perfeitos: elas particionam a entrada, mas depois particionam recursivamente ambas as partições resultantes. O resultado é desempenho O (n log n).
Caleb
@afish: Bom ponto. Meu objetivo com esta resposta é mantê-lo o mais simples possível, dada a natureza da pergunta. Mudei a linha "você divide a estrutura ao meio ..." para "você divide a estrutura ao meio ... e faz um número constante de operações para cada divisão" para tentar entender esse ponto simplesmente.
Casey Patton
2

Os exemplos típicos são aqueles que lidam com pesquisa binária. Por exemplo, um algoritmo de pesquisa binária é geralmente O(log n).

Se você possui uma árvore de pesquisa binária , pesquisa, inserção e exclusão são O(log n)complexas.

Qualquer situação em que você divida continuamente o espaço geralmente envolve um log ncomponente. É por isso que muitos algoritmos de classificação têm O(nlog n)complexidade, porque geralmente particionam um conjunto e classificam à medida que avançam.

Kris Harper
fonte
1

Se você deseja que seja tão simples quanto "loop único -> O (n), loop duplo -> O (n ^ 2)", a resposta provavelmente é "Árvore -> O (log n)". Atravessar com mais precisão uma árvore da raiz para uma (não todas!) Folha ou o contrário. No entanto, essas são todas simplificações excessivas.

scarfridge
fonte
Então, o que há de errado com a minha resposta? Estou aberto a críticas construtivas.
scarfridge
0

Você deseja saber se existe uma maneira fácil de identificar se um algoritmo é O (log N).

Bem: basta correr e cronometrar. Execute-o para entradas 1.000, 10.000, 100.000 e um milhão.

Se você observar um tempo de execução de 3,4,5,6 segundos (ou algum múltiplo), poderá dizer com segurança que é O (log N). Se é mais como: 1,10,100,1000 segundos, provavelmente é O (N). E se estiver em 3.40.500.6000 segundos, será O (N log N).

Pieter B
fonte
Todo mundo deveria dar a esta resposta um
voto positivo