O log Big O (logn) é base e?

96

Para o tipo de árvore de pesquisa binária de estruturas de dados, vejo que a notação Big O é normalmente indicada como O (logn). Com um 'l' minúsculo em log, isso implica log de base e (n) conforme descrito pelo logaritmo natural? Desculpe pela pergunta simples, mas sempre tive problemas para distinguir entre os diferentes logaritmos implícitos.

math binary-tree complexity-theory big-o BuckFilledPlatypus
fonte

58

Como outros apontaram convincentemente, não importa. Todos os logaritmos diferem uns dos outros por uma constante dependente apenas das bases envolvidas. Como esses fatores são constantes, eles são irrelevantes para os propósitos da análise assintótica. Em segundo lugar, no que diz respeito à determinação da base implícita, depende do contexto. Como regra geral, use o seguinte: 1. Quando um matemático escreve, log nele se refere ao logaritmo natural. 2. Quando um cientista da computação escreve, log nele se refere à base dois. 3. Quando um engenheiro escreve, log nele quer dizer base dez. Isso geralmente é verdade.

jason de

4

@Jason, outra convenção (dentro da matemática) é que ln n significa o logaritmo natural e log n é base dez. Think ln significa 'logaritmo naturelle' em francês.

Homem da Internet de

2

A base do logaritmo é o número de filhos que cada nó possui. Se for uma árvore binária, é um log de base 2.

Paul

3

Agradeço sua resposta, Jason, e aqui está algo em que pensar. Ao pesquisar em que base o log está (presumi 2), vi a mesma resposta: que não importa porque você pode eliminar a constante, log_10 (2). Meu problema com isso é que, por exemplo: 5 log_10 (5) <5, enquanto 5 log_2 (5)> 5. Eu inseri isso rapidamente no meu cálculo para ajudar a conceituar onde O (n logn) tem melhor ou pior tempo de execução do que O (n). Dependendo da base, IMPORTA. Portanto, eu realmente acho que a resposta CERTA para isso deveria ser que log contextualmente significa base 2 na maioria dos aplicativos de ciência da computação.

Doug Mead

@jason, diria que é mais fácil de usar ln (interpretação do matemático);). Os outros dois exemplos são razoáveis.

belford

77

Uma vez expresso na notação big-O (), ambos estão corretos. Porém, durante a derivação do polinômio O (), no caso da busca binária , apenas o log ₂ está correto. Presumo que essa distinção foi a inspiração intuitiva para sua pergunta para começar.

Além disso, na minha opinião, escrever O (log ₂ N) é melhor para o seu exemplo, porque comunica melhor a derivação do tempo de execução do algoritmo.

Na notação big-O (), os fatores constantes são removidos. A conversão de uma base de logaritmo para outra envolve a multiplicação por um fator constante.

Portanto, O (log N) é equivalente a O (log ₂ N) devido a um fator constante.

No entanto, se você pode digitar facilmente log ₂ N em sua resposta, isso é mais pedagógico. No caso de pesquisa em árvore binária, você está correto ao dizer que log ₂ N é introduzido durante a derivação do tempo de execução big-O ().

Antes de expressar o resultado como notação big-O (), a diferença é muito importante. Ao derivar o polinômio a ser comunicado por meio da notação big-O, seria incorreto para este exemplo usar um logaritmo diferente de log ₂ N, antes de aplicar a notação O () -. Assim que o polinômio é usado para comunicar um tempo de execução de pior caso por meio da notação big-O (), não importa qual logaritmo é usado.

Heath Hunnicutt
fonte

4

Mas é muito fácil mostrar que log_2 nvale Θ(log_a n)para qualquer base a, então não tenho certeza se vejo como usar a base 2 é "mais correto".

bcat

1

Kinopkio e bcat, obrigado por ajudá-lo a se tornar útil. Não foi muito bem escrito no início. :)

Heath Hunnicutt,

2

Bem, adicionei clareza, mas estou magoado que você pense que minha resposta pode confundir as pessoas. Na verdade, a maioria das respostas aqui não levou em consideração a intuição do OP e tentou ensiná-lo muito. Não estou muito impressionado com a competição, estou meio triste com o baixo nível da pedagogia.

Heath Hunnicutt,

11

"durante a derivação do polinômio O (), no caso de pesquisa binária, apenas log2 está correto." -1 para matemática pobre. A definição de x (n) ~ O (f (n)) diz que existe uma constante c tal que c * (f (n)) <x (n) para todo n> n_0. Assim, o coeficiente constante é completamente irrelevante durante a análise.

rlbond

3

Como log2 (x) é igual a log10 (x) / log10 (2), você pode derivá-lo de qualquer maneira. O log não é estritamente de base 2 em nenhum ponto.

rlbond de

80

A notação Big O não é afetada pela base logarítmica, porque todos os logaritmos em bases diferentes estão relacionados por um fator constante , O(ln n)é equivalente a O(log n).

Cade Roux
fonte

2

os gráficos são legais, mas pense sobre a derivação do O () - polinômio ... antes de O () ser aplicado, apenas log-base-2 é correto para pesquisa binária.

Heath Hunnicutt,

1

@Heath Hunnicutt: Não. log_2 xDifere de log_b xpor um fator constante c(b)para qualquer base bindependente de x.

Jason,

4

Mas por que você está falando sobre isso, se não tem relação com a pergunta e só serve para confundir?

hobbs,

4

hobbs: Porque esse é o motivo pelo qual o OP foi inspirado a perguntar. Estou tentando conectar suas idéias com a resposta, para que ele entenda por que teve sua intuição, por que ela não se aplica a O (), mas não aplique demais o que ele aprendeu aqui à parte de derivação da análise. As respostas concisas que não abordam a causa raiz do mal-entendido podem levar a mais mal-entendidos. É uma pedagogia ruim.

Heath Hunnicutt,

4

@Heath Hunnicutt: Se você está fazendo uma análise assintótica, não importa. O fato de você esperar até o último minuto para lançar alguns grandes O's não muda o fato de que posso multiplicar e dividir todos os meus logaritmos por alguma constante boba e mudar a base em todas as etapas. Ou seja, se eu tiver alguma análise que envolva log_2 n, posso simplesmente entrar e substituir tudo log_2 npor log_pi 2 * log_2 n / log_pi 2e, então, terminar com uma análise que envolve tudo log_pi 2 * log_pi n. Agora minha análise é em termos de log_pi n.

jason de

9

Na verdade, não importa que base seja, uma vez que a notação big-O geralmente é escrita mostrando apenas a ordem assintoticamente mais alta de n, então os coeficientes constantes diminuirão. Como uma base de logaritmo diferente é equivalente a um coeficiente constante, ela é supérflua.

Dito isso, provavelmente assumirei a base de log 2.

Daniel Pryden
fonte

@Kinopiko: O que exatamente há de errado nisso? Mais precisamente, em que minha resposta é factualmente diferente da sua e de outras aqui?

Daniel Pryden,

Ah, talvez o meu erro no uso de "coeficiente". Vou editar para esclarecer.

Daniel Pryden,

Esse foi o meu principal problema com sua resposta. Além disso, não está claro o que você quer dizer com "eles ainda terão algum efeito". Algum efeito em quê?

bcat

1

Sua resposta discute os coeficientes de ordem mais altos. O que você disse está correto até o fim, mas não é por isso que a base do logaritmo é irrelevante. A razão é que a diferença entre os diferentes logaritmos de base é uma constante que é absorvida pelo O ().

1

@Kinopiko: OK. Acho que estamos dizendo a mesma coisa. Eu diria O (100) = O (1) porque O (100) = O (100 * 1) = O (C * 1) = O (1). Que é o que eu quis dizer com expressões constantes sendo supérfluas. Ou seja, a ordem de qualquer constante é 1.

Daniel Pryden,

7

Ambos estão corretos. Pense sobre isso

log2(n)=log(n)/log(2)=O(log(n))
log10(n)=log(n)/log(10)=O(log(n))
logE(n)=log(n)/log(E)=O(log(n))

cartonn
fonte

2

Sim, ao falar sobre a notação big-O, a base não importa. No entanto, computacionalmente, quando confrontado com um problema de pesquisa real, isso importa.

Ao desenvolver uma intuição sobre estruturas de árvore, é útil entender que uma árvore de pesquisa binária pode ser pesquisada em tempo O (n log n) porque essa é a altura da árvore - ou seja, em uma árvore binária com n nós, a árvore a profundidade é O (n log n) (base 2). Se cada nó tiver três filhos, a árvore ainda pode ser pesquisada em tempo O (n log n), mas com um logaritmo de base 3. Computacionalmente, o número de filhos que cada nó possui pode ter um grande impacto no desempenho (ver por exemplo: texto do link )

Aproveitar!

Paulo

Paulo
fonte

você quis dizer que a altura de uma árvore binária é log n, não n log n, certo?

celular

1

Tecnicamente, a base não importa, mas geralmente você pode pensar nela como base-2.

Tim Sylvester
fonte

1

Primeiro você deve entender o que significa para uma função f (n) ser O (g (n)).

A definição formal é: * Diz-se que uma função f (n) é O (g (n)) iff | f (n) | <= C * | g (n) | sempre que n> k, onde C e k são constantes. *

então seja f (n) = log base a de n, onde a> 1 e g (n) = log base b de n, onde b> 1

NOTA: Isso significa que os valores a e b podem ser qualquer valor maior que 1, por exemplo a = 100 e b = 3

Agora temos o seguinte: log base a de n é dito ser O (log base b de n) iff | log base a de n | <= C * | log de base b de n | sempre que n> k

Escolha k = 0 e C = log base a de b.

Agora nossa equação se parece com o seguinte: | log base a de n | <= log da base a de b * | log da base b de n | sempre que n> 0

Agora nossa equação se parece com o seguinte: | log base a de n | <= | log de base a de n | sempre que n> 0

A equação é sempre verdadeira, não importa quais são os valores n, b ou a, exceto suas restrições a, b> 1 e n> 0. Portanto, log base a de n é O (log base b de n) e como a, b não importa, podemos simplesmente omiti-los.

Você pode ver um vídeo do YouTube sobre ele aqui: https://www.youtube.com/watch?v=MY-VCrQCaVw

Você pode ler um artigo sobre ele aqui: https://medium.com/@randerson112358/omitting-bases-in-logs-in-big-o-a619a46740ca

tempmail
fonte

O log Big O (logn) é base e?

Respostas: