Big O (log) é base de log e?

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

Uma vez expresso em notação big-O (), ambos estão corretos. No entanto, durante a derivação do polinômio O (), no caso da pesquisa binária , apenas o log 2 está correto. Presumo que essa distinção tenha sido a inspiração intuitiva para a sua pergunta.

Além disso, na minha opinião, escrever O (log 2 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.

Então O (log N) é equivalente a O (log 2 N) devido a um fator constante.

No entanto, se você puder compor facilmente o log 2 N em sua resposta, fazer isso é mais pedagógico. No caso da pesquisa de tree binária, você está correto que o log 2 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 via notação big-O, seria incorreto para este exemplo usar um logaritmo diferente de log 2 N, antes de aplicar a notação O (). Assim que o polinômio é usado para comunicar um tempo de execução do pior caso via notação big-O (), não importa qual logaritmo é usado.

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

insira a descrição da imagem aqui

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

Dito isto, provavelmente assumirei a base de log 2.

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

Sim, quando se fala de 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 tree, é útil entender que uma tree de pesquisa binária pode ser pesquisada em tempo O (n log n) porque essa é a altura da tree – ou seja, em uma tree binária com n nós, a tree profundidade é O (n log n) (base 2). Se cada nó tiver três filhos, a tree ainda poderá ser pesquisada no 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 (veja, por exemplo: link text )

Apreciar!

Paulo

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)) 

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

A definição formal é: * Uma function f (n) é dita como O (g (n)) iff | f (n) | <= C * | g (n) | sempre que n> k, onde C ek são constantes. *

então vamos 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 aeb podem ser qualquer valor maior que 1, por exemplo, a = 100 eb = 3

Agora nós temos o seguinte: log base a de n é dito ser O (log base b de n) iff | log base a de n | <= C * | log 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 of n | <= log base a de b * | log base b de n | sempre que n> 0

Observe o lado direito, podemos manipular a equação: = log base a b * | log base b de n | = log base b de n | * log base a de b = | log base a de b ^ (log base b de n) | = | log base a de n |

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

A equação é sempre verdadeira, não importa quais sejam os valores n, b ou a, além de 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 aqui: https://www.youtube.com/watch?v=MY-VCrQCaVw

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