Como saber quando Big O é logarítmica?

Question

A minha pergunta surge da pós "Plain Inglês Explicação do Big O" . Eu não sei o significado exato de complexidade logarítmica. Eu sei que eu posso fazer uma regressão entre o tempo eo número de operações e calcular o valor X-quadrado, e determinar assim a complexidade. No entanto, eu quero saber um método para determinar rapidamente no papel.

Como você determina a complexidade logarítmica? Existem algumas boas referências?

Answer 1

Não tenho certeza se é isso que você quer dizer, mas ... complexidade logarítmica geralmente surge quando você está trabalhando com uma estrutura de dados espalhado como uma árvore binária balanceada, que contém 1 nó na raiz, 2 crianças, 4 netos, 8 bisnetos, etc. Basicamente, em cada nível o número de nós será multiplicada por algum factor (2), mas ainda só um desses está envolvido na iteração. Ou, como outro exemplo, um circuito em que as duplas de índice em cada passo:

for (int i = 1; i < N; i *= 2) { ... }

Coisas como essa são as assinaturas de complexidade logarítmica.

Answer 2

Não rigorosa, mas você tem um algoritmo que é, essencialmente, dividindo o trabalho precisava ser feito pela metade em cada iteração, então você tem complexidade logarítmica. O exemplo clássico é a busca binária.

Answer 3

Mestre teorema geralmente funciona.

Answer 4

Se você só quer saber sobre logarítmica Big Oh, estar atento para quando seus dados é cortado ao meio cada etapa da recorrência.

Isso porque, se você está processando dados que é 1/2 tão grande como a etapa anterior, é uma série infinita.

Answer 5

Aqui é uma outra maneira de dizê-lo.

Suponha que seu algoritmo é linear no número de dígitos no tamanho do problema. Então, talvez você tem um novo algoritmo para fator de um grande número, que você pode mostrar para ser linear no número de dígitos. Um número de 20 dígitos, assim, leva o dobro do tempo para fator como um número de 10 dígitos usando seu algoritmo. Isso teria complexidade log. (E seria algo que vale para o inventor.)

Bissecção tem o mesmo comportamento. Demora cerca de 10 bisection passos para cortar o comprimento do intervalo por um fator de 1024 = 2 ^ 10, mas apenas 20 passos vai cortar o intervalo por um fator de 2 ^ 20.

complexidade

Log nem sempre significa um algoritmo é rápido em todos os problemas. O factor linear em frente do O (log (n)) pode ser grande. Portanto, o seu algoritmo pode ser terrível em pequenos problemas, não se tornando útil até que o tamanho do problema é significativamente grande que outros algoritmos de uma morte exponencial (ou polinomial).