O que significa O (log n) exatamente?

Estou aprendendo sobre os tempos de execução da Big O Notation e os tempos amortizados. Eu entendo a noção de tempo linear O (n) , o que significa que o tamanho da entrada afeta o crescimento do algoritmo proporcionalmente ... e o mesmo vale para, por exemplo, tempo quadrático O (n ² ) etc .. mesmo algoritmos , como geradores de permutação, com O (n!) vezes, que crescem por fatoriais.

Por exemplo, a seguinte função é O (n) porque o algoritmo cresce proporcionalmente à sua entrada n :

f(int n) {
  int i;
  for (i = 0; i < n; ++i)
    printf("%d", i);
}

Da mesma forma, se houvesse um loop aninhado, o tempo seria O (n ² ).

Mas o que exatamente é O (log n) ? Por exemplo, o que significa dizer que a altura de uma árvore binária completa é O (log n) ?

Eu sei (talvez não em detalhes) o que é Logaritmo, no sentido de que: log ₁₀ 100 = 2, mas não consigo entender como identificar uma função com um tempo logarítmico.

Não consigo entender como identificar uma função com um tempo de log.

Os atributos mais comuns da função logarítmica em tempo de execução são os seguintes:

• a escolha do próximo elemento no qual executar alguma ação é uma das várias possibilidades, e
• somente um precisará ser escolhido.

ou

• os elementos nos quais a ação é executada são dígitos de n

É por isso que, por exemplo, procurar pessoas em uma lista telefônica é O (log n). Você não precisa verificar todas as pessoas na lista telefônica para encontrar a certa; em vez disso, você pode simplesmente dividir e conquistar, baseando-se em onde o nome deles está em ordem alfabética, e em cada seção você só precisa explorar um subconjunto de cada seção antes de encontrar o número de telefone de alguém.

Obviamente, uma lista telefônica maior ainda levará mais tempo, mas não crescerá tão rapidamente quanto o aumento proporcional no tamanho adicional.

Podemos expandir o exemplo da lista telefônica para comparar outros tipos de operações e seu tempo de execução. Assumiremos que nossa agenda telefônica possui empresas (as "Páginas Amarelas") que têm nomes exclusivos e pessoas (as "Páginas Brancas") que podem não ter nomes exclusivos. Um número de telefone é atribuído a no máximo uma pessoa ou empresa. Também assumiremos que é necessário um tempo constante para acessar uma página específica.

Aqui estão os tempos de execução de algumas operações que podemos executar na lista telefônica, do mais rápido ao mais lento:

• O (1) (na pior das hipóteses): dada a página em que o nome de uma empresa está e o nome da empresa, encontre o número de telefone.

• O (1) (no caso médio): dada a página em que o nome de uma pessoa está e seu nome, encontre o número de telefone.

• O (log n): Dado o nome de uma pessoa, encontre o número de telefone escolhendo um ponto aleatório na metade da parte do livro que você ainda não pesquisou e depois verifique se o nome da pessoa está nesse ponto. Em seguida, repita o processo na metade da parte do livro onde está o nome da pessoa. (Esta é uma pesquisa binária pelo nome de uma pessoa.)

• O (n): encontre todas as pessoas cujos números de telefone contenham o dígito "5".

• O (n): dado um número de telefone, encontre a pessoa ou empresa com esse número.

• O (n log n): Houve uma confusão no escritório da impressora e nossa lista telefônica teve todas as suas páginas inseridas em uma ordem aleatória. Corrija a ordem para que esteja correta, observando o primeiro nome em cada página e colocando-a no local apropriado em uma lista telefônica nova e vazia.

Para os exemplos abaixo, agora estamos no escritório da impressora. As listas telefônicas estão aguardando para serem enviadas por correio para cada residente ou empresa, e há um adesivo em cada lista telefônica identificando para onde deve ser enviado. Cada pessoa ou empresa recebe uma lista telefônica.

• O (n log n): queremos personalizar a lista telefônica, para encontrar o nome de cada pessoa ou empresa em sua cópia designada, circular seu nome no livro e escrever uma breve nota de agradecimento por seu patrocínio. .

• O (n ² ): ocorreu um erro no escritório, e cada entrada em cada uma das listas telefônicas tem um "0" extra no final do número de telefone. Pegue um pouco de branco e remova cada zero.

• O (n · n!): Estamos prontos para carregar as agendas telefônicas na doca de remessa. Infelizmente, o robô que deveria carregar os livros deu errado: está colocando os livros no caminhão em uma ordem aleatória! Pior ainda, ele carrega todos os livros no caminhão, depois verifica se eles estão na ordem certa e, se não, os descarrega e começa de novo. (Essa é a temida classificação bogo .)

• O (n ⁿ ): Você conserta o robô para que ele carregue as coisas corretamente. No dia seguinte, um de seus colegas de trabalho faz uma brincadeira com você e liga o robô da estação de carregamento aos sistemas de impressão automatizados. Sempre que o robô carrega um livro original, a impressora de fábrica executa uma duplicação de todas as agendas telefônicas! Felizmente, os sistemas de detecção de erros do robô são sofisticados o suficiente para que o robô não tente imprimir ainda mais cópias ao encontrar um livro duplicado para carregamento, mas ainda precisa carregar todos os livros originais e duplicados que foram impressos.

O(log N)basicamente significa que o tempo aumenta linearmente enquanto naumenta exponencialmente. Portanto, se levar alguns 1segundos para calcular 10elementos, levará 2segundos para calcular 100elementos, 3segundos para calcular 1000elementos e assim por diante.

É O(log n)quando dividimos e conquistamos tipos de algoritmos, por exemplo, pesquisa binária. Outro exemplo é a classificação rápida, onde cada vez que dividimos a matriz em duas partes e cada vez que leva O(N)tempo para encontrar um elemento dinâmico. Por isso N O(log N)

Muitas boas respostas já foram postadas nesta pergunta, mas acredito que realmente estamos perdendo uma importante - a saber, a resposta ilustrada.

O que significa dizer que a altura de uma árvore binária completa é O (log n)?

O desenho a seguir mostra uma árvore binária. Observe como cada nível contém o dobro do número de nós em comparação com o nível acima (portanto, binário ):

A pesquisa binária é um exemplo com complexidade O(log n). Digamos que os nós no nível inferior da árvore na figura 1 representem itens em alguma coleção classificada. A pesquisa binária é um algoritmo de dividir e conquistar, e o desenho mostra como precisaremos (no máximo) de 4 comparações para encontrar o registro que estamos procurando neste conjunto de dados de 16 itens.

Suponhamos que tivéssemos um conjunto de dados com 32 elementos. Continue o desenho acima e descubra que agora precisaremos de 5 comparações para encontrar o que estamos procurando, pois a árvore só aumentou um nível ainda mais quando multiplicamos a quantidade de dados. Como resultado, a complexidade do algoritmo pode ser descrita como uma ordem logarítmica.

A plotagem log(n)em um pedaço de papel comum resultará em um gráfico em que a elevação da curva desacelera à medida que naumenta:

A explicação abaixo está usando o caso de uma árvore binária totalmente equilibrada para ajudá-lo a entender como obtemos a complexidade do tempo logarítmico.

Árvore binária é um caso em que um problema de tamanho n é dividido em subproblema de tamanho n / 2 até chegarmos a um problema de tamanho 1:

E é assim que você obtém O (log n), que é a quantidade de trabalho que precisa ser feito na árvore acima para chegar a uma solução.

Um algoritmo comum com complexidade de tempo O (log n) é a Pesquisa Binária, cuja relação recursiva é T (n / 2) + O (1), ou seja, em cada nível subseqüente da árvore, você divide o problema pela metade e realiza uma quantidade constante de trabalho adicional.

Visão geral

Outros deram bons exemplos de diagramas, como os diagramas de árvore. Não vi nenhum exemplo simples de código. Portanto, além da minha explicação, fornecerei alguns algoritmos com instruções de impressão simples para ilustrar a complexidade de diferentes categorias de algoritmos.

Primeiro, você deseja ter uma idéia geral do Logaritmo, que pode ser obtida em https://en.wikipedia.org/wiki/Logarithm . Uso das ciências naturais ee registro natural. Os discípulos da engenharia usarão o log_10 (base 10 do log) e os cientistas da computação usarão muito o log_2 (base 2 do log), uma vez que os computadores são binários. Às vezes, você verá as abreviações do log natural como ln(), os engenheiros normalmente deixam o _10 desativado e apenas usam log()e o log_2 é abreviado como lg(). Todos os tipos de logaritmos crescem de maneira semelhante, é por isso que compartilham a mesma categoria de log(n).

Quando você olha os exemplos de código abaixo, recomendo olhar O (1), O (n) e O (n ^ 2). Depois de ser bom com eles, olhe para os outros. Incluí exemplos limpos e variações para demonstrar como as mudanças sutis ainda podem resultar na mesma categorização.

Você pode pensar em O (1), O (n), O (logn) etc. como classes ou categorias de crescimento. Algumas categorias levarão mais tempo do que outras. Essas categorias nos ajudam a ordenar o desempenho do algoritmo. Alguns cresceram mais rápido à medida que a entrada n cresce. A tabela a seguir demonstra o referido crescimento numericamente. Na tabela abaixo, considere log (n) como o limite máximo de log_2.

Exemplos de código simples de várias grandes categorias O:

O (1) - Exemplos de tempo constante:

• Algoritmo 1:

O algoritmo 1 imprime olá uma vez e não depende de n, portanto sempre será executado em tempo constante, como é O(1).

print "hello";

• Algoritmo 2:

O algoritmo 2 imprime olá 3 vezes, no entanto, não depende do tamanho da entrada. Mesmo quando n cresce, esse algoritmo sempre imprime olá apenas 3 vezes. Dito isto 3, é uma constante, então esse algoritmo também é O(1).

print "hello";
print "hello";
print "hello";

O (log (n)) - Exemplos logarítmicos:

• Algoritmo 3 - Funciona como "log_2"

O algoritmo 3 demonstra um algoritmo que é executado em log_2 (n). Observe que a pós-operação do loop for multiplica o valor atual de i por 2, ivaria de 1 a 2 a 4 a 8 a 16 a 32 ...

for(int i = 1; i <= n; i = i * 2)
  print "hello";

• Algoritmo 4 - Funciona como "log_3"

O algoritmo 4 demonstra log_3. O aviso ivaria de 1 a 3 a 9 a 27 ...

for(int i = 1; i <= n; i = i * 3)
  print "hello";

• Algoritmo 5 - Funciona como "log_1.02"

O algoritmo 5 é importante, pois ajuda a mostrar que, desde que o número seja maior que 1 e o resultado seja multiplicado repetidamente contra si mesmo, você está procurando um algoritmo logarítmico.

for(double i = 1; i < n; i = i * 1.02)
  print "hello";

O (n) - Exemplos de tempo linear:

• Algoritmo 6

Esse algoritmo é simples, que imprime olá n vezes.

for(int i = 0; i < n; i++)
  print "hello";

• Algoritmo 7

Este algoritmo mostra uma variação, na qual imprimirá olá n / 2 vezes. n / 2 = 1/2 * n. Ignoramos a constante 1/2 e vemos que esse algoritmo é O (n).

for(int i = 0; i < n; i = i + 2)
  print "hello";

O (n * log (n)) - nlog (n) Exemplos:

• Algoritmo 8

Pense nisso como uma combinação de O(log(n))e O(n). O aninhamento dos loops for nos ajuda a obter oO(n*log(n))

for(int i = 0; i < n; i++)
  for(int j = 1; j < n; j = j * 2)
    print "hello";

• Algoritmo 9

O algoritmo 9 é como o algoritmo 8, mas cada um dos loops permitiu variações, o que ainda resulta no resultado final sendo O(n*log(n))

for(int i = 0; i < n; i = i + 2)
  for(int j = 1; j < n; j = j * 3)
    print "hello";

O (n ^ 2) - n ao quadrado Exemplos:

• Algoritmo 10

O(n^2) é obtido facilmente aninhando o padrão para loops.

for(int i = 0; i < n; i++)
  for(int j = 0; j < n; j++)
    print "hello";

• Algoritmo 11

Como o algoritmo 10, mas com algumas variações.

for(int i = 0; i < n; i++)
  for(int j = 0; j < n; j = j + 2)
    print "hello";

O (n ^ 3) - n em cubo Exemplos:

• Algoritmo 12

É como o algoritmo 10, mas com 3 loops em vez de 2.

for(int i = 0; i < n; i++)
  for(int j = 0; j < n; j++)
    for(int k = 0; k < n; k++)
      print "hello";

• Algoritmo 13

Como o algoritmo 12, mas com algumas variações que ainda produzem O(n^3).

for(int i = 0; i < n; i++)
  for(int j = 0; j < n + 5; j = j + 2)
    for(int k = 0; k < n; k = k + 3)
      print "hello";

Sumário

O exemplo acima fornece vários exemplos diretos e variações para ajudar a demonstrar que mudanças sutis podem ser introduzidas que realmente não alteram a análise. Espero que isso lhe dê informações suficientes.

Se você tivesse uma função que aceita:

1 millisecond to complete if you have 2 elements.
2 milliseconds to complete if you have 4 elements.
3 milliseconds to complete if you have 8 elements.
4 milliseconds to complete if you have 16 elements.
...
n milliseconds to complete if you have 2^n elements.

Depois, leva ₂ (n) tempo para o log . A notação Big O , em termos gerais, significa que o relacionamento só precisa ser verdadeiro para n grande e que fatores constantes e termos menores podem ser ignorados.

O tempo de execução logarítmico ( O(log n)) significa essencialmente que o tempo de execução aumenta proporcionalmente ao logaritmo do tamanho da entrada - por exemplo, se 10 itens levam no máximo algum tempo xe 100 itens levam no máximo, digamos 2x, e 10.000 itens leva no máximo 4x, então parece uma O(log n)complexidade de tempo.

O logaritmo

Ok, vamos tentar entender completamente o que é realmente um logaritmo.

Imagine que temos uma corda e a amarramos a um cavalo. Se a corda estiver diretamente amarrada ao cavalo, a força que o cavalo precisaria puxar (digamos, de um homem) é diretamente 1.

Agora imagine que a corda está presa em volta de um poste. O cavalo para fugir agora terá que se esforçar muitas vezes. A quantidade de vezes dependerá da aspereza da corda e do tamanho do poste, mas vamos supor que ela multiplique a força de alguém por 10 (quando a corda fizer uma curva completa).

Agora, se a corda for presa uma vez, o cavalo precisará puxar 10 vezes mais. Se o humano decidir tornar isso realmente difícil para o cavalo, ele poderá prender a corda novamente em volta de um poste, aumentando sua força em mais 10 vezes. Um terceiro loop aumentará novamente a força em mais 10 vezes.

Podemos ver que, para cada loop, o valor aumenta em 10. O número de voltas necessárias para obter qualquer número é chamado logaritmo do número, ou seja, precisamos de 3 postagens para multiplicar sua força por 1000 vezes, 6 postagens para multiplicar sua força por 1.000.000.

3 é o logaritmo de 1.000 e 6 é o logaritmo de 1.000.000 (base 10).

Então, o que O (log n) realmente significa?

No exemplo acima, nossa 'taxa de crescimento' é O (log n) . Para cada loop adicional, a força que nossa corda pode suportar é 10 vezes mais:

Turns | Max Force
  0   |   1
  1   |   10
  2   |   100
  3   |   1000
  4   |   10000
  n   |   10^n

Agora, o exemplo acima usou a base 10, mas, felizmente, a base do log é insignificante quando falamos de grande notação.

Agora vamos imaginar que você está tentando adivinhar um número entre 1 e 100.

Your Friend: Guess my number between 1-100! 
Your Guess: 50
Your Friend: Lower!
Your Guess: 25
Your Friend: Lower!
Your Guess: 13
Your Friend: Higher!
Your Guess: 19
Your Friend: Higher!
Your Friend: 22
Your Guess: Lower!
Your Guess: 20
Your Friend: Higher!
Your Guess: 21
Your Friend: YOU GOT IT!  

Agora você precisou de 7 palpites para acertar. Mas qual é o relacionamento aqui? Qual é a maior quantidade de itens que você pode adivinhar em cada palpite adicional?

Guesses | Items
  1     |   2
  2     |   4
  3     |   8
  4     |   16
  5     |   32
  6     |   64
  7     |   128
  10    |   1024

Usando o gráfico, podemos ver que, se usarmos uma pesquisa binária para adivinhar um número entre 1 e 100, levaremos no máximo 7 tentativas. Se tivéssemos 128 números, também poderíamos adivinhar o número em 7 tentativas, mas 129 números nos levarão no máximo 8 tentativas (em relação aos logaritmos, aqui precisaríamos de 7 suposições para um intervalo de 128 valores, 10 suposições para um intervalo de valores de 1024 7 é o logaritmo de 128, 10 é o logaritmo de 1024 (base 2)).

Observe que eu tenho negrito 'no máximo'. A notação Big-O sempre se refere ao pior caso. Se você tiver sorte, poderá adivinhar o número em uma tentativa e, portanto, o melhor caso é O (1), mas isso é outra história.

Podemos ver que, para todos os palpites, nosso conjunto de dados está diminuindo. Uma boa regra para identificar se um algoritmo tem um tempo logaritmático é verificar se o conjunto de dados diminui em uma determinada ordem após cada iteração

E quanto a O (n log n)?

Você encontrará um algoritmo de tempo linearitômico O (n log (n)) . A regra geral acima se aplica novamente, mas desta vez a função logarítmica deve executar n vezes, por exemplo, reduzindo o tamanho de uma lista n vezes , o que ocorre em algoritmos como um mergesort.

Você pode identificar facilmente se o tempo algorítmico é n log n. Procure um loop externo que itere através de uma lista (O (n)). Então veja se há um loop interno. Se o loop interno estiver cortando / reduzindo o conjunto de dados em cada iteração, esse loop será (O (log n)) e, portanto, o algoritmo geral será = O (n log n) .

Isenção de responsabilidade: O exemplo do logaritmo de corda foi retirado do excelente livro Mathematician's Delight, de W.Sawyer .

Você pode pensar em O (log N) intuitivamente dizendo que o tempo é proporcional ao número de dígitos em N.

Se uma operação executar um trabalho de tempo constante em cada dígito ou bit de uma entrada, toda a operação levará um tempo proporcional ao número de dígitos ou bits na entrada, não à magnitude da entrada; assim, O (log N) em vez de O (N).

Se uma operação toma uma série de decisões de tempo constante, cada uma das quais reduz pela metade (reduz em um fator de 3, 4, 5 ..) o tamanho da entrada a ser considerada, o conjunto levará um tempo proporcional à base 2 do log (base 3 , base 4, base 5 ...) do tamanho N da entrada, em vez de ser O (N).

E assim por diante.

A melhor maneira que eu sempre tive para visualizar mentalmente um algoritmo executado em O (log n) é a seguinte:

Se você aumentar o tamanho do problema em uma quantidade multiplicativa (ou seja, multiplicar seu tamanho por 10), o trabalho será aumentado apenas em uma quantidade aditiva.

Aplicando isso à sua pergunta sobre árvore binária, para que você tenha uma boa aplicação: se você dobrar o número de nós em uma árvore binária, a altura aumentará apenas 1 (uma quantidade aditiva). Se você dobrar novamente, ele ainda aumentará apenas 1. (Obviamente, estou assumindo que ele permanece equilibrado e tal). Dessa forma, em vez de dobrar o seu trabalho quando o tamanho do problema é multiplicado, você está fazendo um pouco mais de trabalho. É por isso que os algoritmos O (log n) são impressionantes.

Primeiro eu recomendo que você leia o livro a seguir;

Algoritmos (4ª Edição)

Aqui estão algumas funções e suas complexidades esperadas. Os números estão indicando frequências de execução de instruções .

Seguinte Big-O Complexity Chart também retirado de bigocheatsheet

Por fim, uma mostra muito simples mostra como é calculada;

Anatomia das frequências de execução de instruções de um programa.

Analisando o tempo de execução de um programa (exemplo).

O que é log _b (n)?

É o número de vezes que você pode cortar um log de comprimento n repetidamente em b partes iguais antes de atingir uma seção de tamanho 1.

Os algoritmos de divisão e conquista geralmente têm um logncomponente para o tempo de execução. Isso ocorre pela metade repetida da entrada.

No caso de pesquisa binária, toda iteração que você joga fora da metade da entrada. Note-se que na notação Big-O, o log é a base 2 do log.

Edit: Como observado, a base de log não importa, mas ao derivar o desempenho Big-O de um algoritmo, o fator de log virá da metade, portanto, por que eu penso nisso como base 2.

Mas o que exatamente é O (log n)? Por exemplo, o que significa dizer que a altura de uma árvore binária completa é O (log n)?

Eu reformularia isso como 'a altura de uma árvore binária completa é log n'. Descobrir a altura de uma árvore binária completa seria O (log n), se você estivesse descendo passo a passo.

Não consigo entender como identificar uma função com um tempo logarítmico.

O logaritmo é essencialmente o inverso da exponenciação. Portanto, se cada 'etapa' da sua função estiver eliminando um fator de elementos do conjunto de itens original, esse é um algoritmo de tempo logarítmico.

Para o exemplo da árvore, você pode ver facilmente que descer um nível de nós reduz um número exponencial de elementos à medida que você continua percorrendo. O exemplo popular de procurar em uma lista telefônica classificada por nome é essencialmente equivalente a percorrer uma árvore de pesquisa binária (a página do meio é o elemento raiz e você pode deduzir a cada passo se vai para a esquerda ou para a direita).

Esses 2 casos levarão tempo O (log n)

case 1: f(int n) {
      int i;
      for (i = 1; i < n; i=i*2)
        printf("%d", i);
    }


 case 2  : f(int n) {
      int i;
      for (i = n; i>=1 ; i=i/2)
        printf("%d", i);
    }

O (log n) é um pouco enganador, mais precisamente é O (log ₂ n), ou seja (logaritmo com base 2).

A altura de uma árvore binária balanceada é O (log ₂ n), pois cada nó possui dois (observe os "dois", como no log ₂ n) nós filhos. Portanto, uma árvore com n nós tem uma altura de log ₂ n.

Outro exemplo é a pesquisa binária, que possui um tempo de execução de O (log ₂ n), pois a cada passo você divide o espaço de pesquisa por 2.

O(log n) refere-se a uma função (ou algoritmo, ou etapa de um algoritmo) trabalhando em uma quantidade de tempo proporcional ao logaritmo (geralmente base 2 na maioria dos casos, mas nem sempre, e, de qualquer forma, isso é insignificante pela notação big-O *) do tamanho da entrada.

A função logarítmica é o inverso da função exponencial. Em outras palavras, se sua entrada cresce exponencialmente (em vez de linearmente, como você normalmente consideraria), sua função cresce linearmente.

O(log n)os tempos de execução são muito comuns em qualquer tipo de aplicação de dividir e conquistar, porque você (idealmente) está cortando o trabalho pela metade toda vez. Se em cada uma das etapas de divisão ou conquista, você estiver trabalhando constantemente (ou um trabalho que não seja constante, mas com o tempo crescendo mais lentamente do que O(log n)), toda a sua função será O(log n). É bastante comum que cada etapa exija um tempo linear na entrada; isso equivalerá a uma complexidade total de tempo de O(n log n).

A complexidade do tempo de execução da pesquisa binária é um exemplo de O(log n) . Isso ocorre porque, na pesquisa binária, você sempre ignora metade de sua entrada em cada etapa posterior, dividindo a matriz pela metade e concentrando-se apenas na metade de cada etapa. Cada etapa é de tempo constante, porque na pesquisa binária você só precisa comparar um elemento com sua chave para descobrir o que fazer a seguir, independentemente do tamanho da matriz que você está considerando em qualquer momento. Então você executa aproximadamente as etapas log (n) / log (2).

A complexidade do tempo de execução da classificação por mesclagem é um exemplo de O(n log n). Isso ocorre porque você está dividindo a matriz ao meio com cada etapa, resultando em um total de aproximadamente etapas de log (n) / log (2). No entanto, em cada etapa, é necessário executar operações de mesclagem em todos os elementos (seja uma operação de mesclagem em duas sublistas de n / 2 elementos ou duas operações de mesclagem em quatro sublistas de n / 4 elementos, é irrelevante, pois aumenta a necessidade de faça isso para n elementos em cada etapa). Assim, a complexidade total é O(n log n).

* Lembre-se de que a notação big-O, por definição , constantes não importa. Também pela mudança da regra de base para logaritmos, a única diferença entre logaritmos de bases diferentes é um fator constante.

Simplesmente significa que o tempo necessário para esta tarefa aumenta com o log (n) (exemplo: 2s para n = 10, 4s para n = 100, ...). Leia os artigos da Wikipedia sobre Algoritmo de pesquisa binária e Big O Notation para obter mais precisões.

Simplificando: em cada etapa do seu algoritmo, você pode cortar o trabalho pela metade. (Assintoticamente equivalente a terceiro, quarto, ...)

Se você plotar uma função logarítmica em uma calculadora gráfica ou algo semelhante, verá que ela aumenta muito lentamente - ainda mais lentamente que uma função linear.

É por isso que algoritmos com uma complexidade de tempo logarítmica são muito procurados: mesmo para n realmente grande (digamos n = 10 ^ 8, por exemplo), eles executam mais do que aceitável.

Mas o que exatamente é O (log n)

O que isso significa precisamente é "como ntende para infinity, a timetendência para a*log(n)onde aé um fator de escala constante".

Ou, na verdade, não significa exatamente isso; mais provavelmente significa algo como " timedividido por a*log(n)tendências em direção a 1".

"Tende para" tem o significado matemático usual de 'análise': por exemplo, que "se você escolher qualquer constante diferente de zero arbitrariamente pequena k, posso encontrar um valor correspondente Xtal que ((time/(a*log(n))) - 1)seja menor do que kpara todos os valores nmaiores que X".

Em termos leigos, significa que a equação para o tempo pode ter outros componentes: por exemplo, pode ter um tempo de inicialização constante; mas esses outros componentes empalidecem na insignificância para grandes valores de n, e a * log (n) é o termo dominante para n grande.

Observe que se a equação fosse, por exemplo ...

tempo (n) = a + b log (n) + c n + d n n

... então seria O (n ao quadrado) porque, independentemente dos valores das constantes a, b, c e diferente de zero d, o d*n*ntermo sempre dominaria sobre as outras por qualquer valor suficientemente grande de n.

É isso que a notação O de bit significa: significa "qual é a ordem do termo dominante para qualquer n suficientemente grande".

Posso acrescentar algo interessante, que li no livro de Kormen e etc., há muito tempo. Agora, imagine um problema, onde temos que encontrar uma solução em um espaço problemático. Esse espaço problemático deve ser finito.

Agora, se você puder provar, a cada iteração do seu algoritmo você corta uma fração desse espaço, que não é menor que algum limite, isso significa que seu algoritmo está sendo executado no tempo O (logN).

Devo salientar que estamos falando aqui de um limite relativo de fração, não do absoluto. A pesquisa binária é um exemplo clássico. A cada passo, jogamos fora 1/2 do espaço do problema. Mas a pesquisa binária não é o único exemplo. Suponha, você provou de alguma forma, que a cada passo você joga fora pelo menos 1/128 do espaço do problema. Isso significa que seu programa ainda está sendo executado no horário O (logN), embora significativamente mais lento que a pesquisa binária. Essa é uma dica muito boa na análise de algoritmos recursivos. Frequentemente, pode-se provar que em cada etapa a recursão não utilizará várias variantes, e isso leva ao corte de alguma fração no espaço do problema.

Posso dar um exemplo para um loop for e, uma vez que compreendi o conceito, talvez seja mais simples de entender em diferentes contextos.

Isso significa que, no loop, o passo cresce exponencialmente. Por exemplo

for (i=1; i<=n; i=i*2) {;}

A complexidade na notação O deste programa é O (log (n)). Vamos tentar percorrê-lo manualmente (n estando em algum lugar entre 512 e 1023 (excluindo 1024):

step: 1   2   3   4   5    6    7    8     9     10
   i: 1   2   4   8   16   32   64   128   256   512

Embora n esteja entre 512 e 1023, apenas 10 iterações ocorrem. Isso ocorre porque a etapa no loop cresce exponencialmente e, portanto, leva apenas 10 iterações para atingir a terminação.

O logaritmo de x (na base de a) é a função inversa de a ^ x.

É como dizer que o logaritmo é o inverso do exponencial.

Agora tente ver dessa maneira, se o exponencial cresce muito rápido, o logaritmo cresce (inversamente) muito lentamente.

A diferença entre O (n) e O (log (n)) é enorme, semelhante à diferença entre O (n) e O (a ^ n) (sendo uma constante).

Na verdade, se você tiver uma lista de n elementos e criar uma árvore binária a partir dessa lista (como no algoritmo de dividir e conquistar), você continuará dividindo por 2 até chegar a listas de tamanho 1 (as folhas).

Na primeira etapa, você divide por 2. Você tem 2 listas (2 ^ 1), divide cada por 2, então você tem 4 listas (2 ^ 2), você divide novamente, você tem 8 listas (2 ^ 3 ) e assim sucessivamente até o tamanho da sua lista ser 1

Isso fornece a equação:

n/(2^steps)=1 <=> n=2^steps <=> lg(n)=steps

(você pega o lg de cada lado, sendo lg a base de log 2)

Toda vez que escrevemos um algoritmo ou código, tentamos analisar sua complexidade assintótica. É diferente da complexidade do tempo .

Complexidade assintótica é o comportamento do tempo de execução de um algoritmo enquanto a complexidade do tempo é o tempo de execução real. Mas algumas pessoas usam esses termos de forma intercambiável.

Porque a complexidade do tempo depende de vários parâmetros viz.
1. Sistema físico
2. Linguagem de programação
3. Estilo de codificação
4. E muito mais ......

O tempo real de execução não é uma boa medida para análise.

Em vez disso, consideramos o tamanho da entrada como parâmetro, pois, independentemente do código, a entrada é a mesma. Portanto, o tempo de execução é uma função do tamanho da entrada.

A seguir, é apresentado um exemplo de algoritmo de tempo linear

Pesquisa linear
Dados os n elementos de entrada, para pesquisar um elemento na matriz, você precisa no máximo de comparações 'n' . Em outras palavras, não importa qual linguagem de programação você usa, que estilo de codificação você prefere, em que sistema você a executa. No pior cenário, requer apenas n comparações. O tempo de execução é linearmente proporcional ao tamanho da entrada.

E não é apenas a pesquisa, qualquer que seja o trabalho (incremento, comparação ou qualquer operação), é uma função do tamanho da entrada.

Portanto, quando você diz que qualquer algoritmo é O (log n), significa que o tempo de execução é o log vezes o tamanho de entrada n.

À medida que o tamanho da entrada aumenta, o trabalho realizado (aqui o tempo de execução) aumenta (daí a proporcionalidade)

      n      Work
      2     1 units of work
      4     2 units of work
      8     3 units of work

Veja como o tamanho da entrada aumentou, o trabalho realizado aumentou e é independente de qualquer máquina. E se você tentar descobrir o valor das unidades de trabalho, na verdade, depende dos parâmetros acima especificados. Isso mudará de acordo com os sistemas e tudo.

log x to base b = y é o inverso de b^y = x

Se você tem uma árvore M-ária de profundidade d e tamanho n, então:

• atravessando a árvore inteira ~ O (M ^ d) = O (n)

• Percorrendo um único caminho na árvore ~ ​​O (d) = O (log na base M)

Em tecnologia da informação, isso significa que:

  f(n)=O(g(n)) If there is suitable constant C and N0 independent on N, 
  such that
  for all N>N0  "C*g(n) > f(n) > 0" is true.

Parece que essa notação foi tirada principalmente da matemática.

Neste artigo, há uma citação: DE Knuth, "BIG OMICRON E BIG OMEGA E BIG THETA", 1976 :

Com base nas questões discutidas aqui, proponho que os membros do SIGACT e os editores de periódicos de ciência da computação e matemática adotem notações conforme definido acima, a menos que uma alternativa melhor possa ser encontrada razoavelmente em breve .

Hoje é 2016, mas ainda o usamos hoje.

Na análise matemática, isso significa que:

  lim (f(n)/g(n))=Constant; where n goes to +infinity

Mas, mesmo na análise matemática, algumas vezes esse símbolo era usado para significar "C * g (n)> f (n)> 0".

Como eu sei da universidade, o símbolo foi introduzido pelo matemático alemão Landau (1877-1938)

O exemplo binário completo é O (ln n) porque a pesquisa se parece com isso:

1 2 3 4 5 6 7 8 9 10 11 12

A pesquisa de 4 gera 3 ocorrências: 6, 3 e 4. E log2 12 = 3, que é uma boa proporção de quantas ocorrências necessárias.

Se você procura uma resposta baseada na intuição, gostaria de apresentar duas interpretações para você.

1. Imagine uma colina muito alta com uma base muito ampla também. Para chegar ao topo da colina, existem duas maneiras: uma é um caminho dedicado que gira em espiral ao redor da colina, chegando ao topo; a outra: pequeno terraço como esculturas cortadas para fornecer uma escada. Agora, se a primeira maneira está atingindo no tempo linear O (n), a segunda é O (log n).

2. Imagine um algoritmo que aceita um número inteiro ncomo entrada e é concluído no tempo proporcional a nO (n) ou teta (n), mas se for executado na proporção de tempo ao number of digits or the number of bits in the binary representation on numberentão o algoritmo será executado em O (log n) ou teta (log n) hora.

Os algoritmos no paradigma Divide e Conquer são de complexidade O (logn). Um exemplo aqui, calcule sua própria função de potência,

int power(int x, unsigned int y)
{
    int temp;
    if( y == 0)
        return 1;
    temp = power(x, y/2);
    if (y%2 == 0)
        return temp*temp;
    else
        return x*temp*temp;
}

de http://www.geeksforgeeks.org/write-ac-program-to-calculate-powxn/