Big-O para Oito Anos de Idade?

Estou perguntando mais sobre o que isso significa para o meu código. Eu entendo os conceitos matematicamente, eu só tenho dificuldade em entender o que eles significam conceitualmente. Por exemplo, se fosse para executar uma operação O (1) em uma estrutura de dados, eu entendo que a quantidade de operações a serem executadas não crescerá porque há mais itens. E uma operação O (n) significaria que você executaria um conjunto de operações em cada elemento. Alguém poderia preencher os espaços em branco aqui?

  • Como exatamente o que uma operação O (n ^ 2) faria?
  • E o que diabos isso significa se uma operação é O (n log (n))?
  • E alguém tem que fumar crack para escrever um O (x!)?

Uma maneira de pensar sobre isso é esta:

O (N ^ 2) significa que para cada elemento, você está fazendo algo com todos os outros elementos, como compará-los. O tipo de bolha é um exemplo disso.

O (N log N) significa que para cada elemento, você está fazendo algo que precisa apenas olhar para o log N dos elementos. Isso geralmente acontece porque você sabe alguma coisa sobre os elementos que permitem fazer uma escolha eficiente. As classificações mais eficientes são um exemplo disso, como a sorting por mesclagem.

O (N!) Significa fazer algo para todas as permutações possíveis dos N elementos. O vendedor ambulante é um exemplo disso, onde existem N! maneiras de visitar os nós, e a solução de força bruta é olhar para o custo total de cada permutação possível para encontrar o melhor.

A grande coisa que a notação Big-O significa para o seu código é como ele será dimensionado quando você dobra a quantidade de “coisas” nas quais opera. Aqui está um exemplo concreto:

 Big-O |  cálculos para 10 coisas |  cálculos para 100 coisas
 -------------------------------------------------- --------------------
 O (1) |  1 |  1
 O (log (n)) |  3 |  7
 O (n) |  10 |  100
 O (n log (n)) |  30 |  700
 O (n ^ 2) |  100 |  10000

Então pegue quicksort que é O (n log (n)) vs bubble sort que é O (n ^ 2). Ao classificar 10 coisas, o quicksort é 3 vezes mais rápido que o bubble sort. Mas quando classificamos 100 coisas, é 14 vezes mais rápido! Escolher claramente o algoritmo mais rápido é importante. Quando você chega a bancos de dados com milhões de linhas, isso pode significar a diferença entre a execução da consulta em 0,2 segundos, em vez de levar horas.

Outra coisa a considerar é que um algoritmo ruim é uma coisa que a lei de Moore não pode ajudar. Por exemplo, se você tem algum cálculo científico que é O (n ^ 3) e pode computar 100 coisas por dia, dobrando a velocidade do processador, você recebe apenas 125 itens por dia. No entanto, derrube esse cálculo para O (n ^ 2) e você estará fazendo 1000 coisas por dia.

esclarecimento: Na verdade, Big-O não diz nada sobre o desempenho comparativo de diferentes algoritmos no mesmo ponto de tamanho específico, mas sim sobre o desempenho comparativo do mesmo algoritmo em diferentes pontos de tamanho:

  computações cálculos computações
 Big-O |  por 10 coisas |  por 100 coisas |  por 1000 coisas
 -------------------------------------------------- --------------------
 O (1) |  1 |  1 |  1
 O (log (n)) |  1 |  3 |  7
 O (n) |  1 |  10 |  100
 O (n log (n)) |  1 |  33 |  664
 O (n ^ 2) |  1 |  100 |  10000

Você pode achar útil visualizá-lo:

Big O Analysis

Além disso, na escala LogY / LogX , as funções n 1/2 , n, n 2 se parecem com linhas retas , enquanto que na escala LogY / X 2 n , e n , 10 n são linhas retas e n! é linearithmic (parece n log n ).

Isso pode ser muito matemático, mas aqui está minha tentativa. (Eu sou um matemático.)

Se algo é O ( f ( n )), então o tempo de execução em n elementos será igual a A f ( n ) + B (medido em, digamos, ciclos de clock ou operações de CPU). É importante entender que você também tem essas constantes A e B , que surgem da implementação específica. B representa essencialmente a “sobrecarga constante” de sua operação, por exemplo, um pré-processamento que você faz e que não depende do tamanho da coleção. A representa a velocidade do seu algoritmo de processamento de itens real.

A chave, no entanto, é que você use uma grande notação O para descobrir como algo será dimensionado . Então, essas constantes não serão realmente importantes: se você está tentando descobrir como escalar de 10 a 10.000 itens, quem se importa com a constante sobrecarga B ? Da mesma forma, outras preocupações (veja abaixo) certamente compensarão o peso da constante multiplicativa A.

Então o negócio real é f ( n ). Se f não cresce com n , por exemplo, f ( n ) = 1, então você vai escalar fantasticamente — seu tempo de corrida será sempre A + B. Se f cresce linearmente com n , ex: f ( n ) = n , seu tempo de execução aumentará praticamente da melhor maneira possível – se seus usuários estiverem esperando 10 ns por 10 elementos, eles aguardarão 10000 ns por 10000 elementos (ignorando a constante aditiva). Mas se crescer mais rápido, como n 2 , então você está com problemas; as coisas começarão a desacelerar muito quando você tiver collections maiores. f ( n ) = n log ( n ) é um bom compromisso, geralmente: sua operação não pode ser tão simples a ponto de dar escalonamento linear, mas você conseguiu reduzir as coisas de tal forma que ele vai escalar muito melhor que f ( n ) = n 2 .

Praticamente, aqui estão alguns bons exemplos:

  • O (1): recuperando um elemento de uma matriz. Nós sabemos exatamente onde está na memory, então nós apenas a pegamos. Não importa se a coleção tem 10 itens ou 10000; ainda está no índice (digamos) 3, então nós simplesmente pulamos para o local 3 na memory.
  • O ( n ): recuperando um elemento de uma linked list. Aqui, A = 0,5, porque em média você terá que passar por metade da linked list antes de encontrar o elemento que está procurando.
  • O ( n 2 ): vários algoritmos de ordenação “burros”. Porque geralmente a estratégia deles envolve, para cada elemento ( n ), você olha para todos os outros elementos (então vezes outro n , dando n 2 ), então se posicione no lugar certo.
  • O ( n log ( n )): vários algoritmos de ordenação “inteligentes”. Acontece que você só precisa olhar, digamos, 10 elementos em uma coleção de 10 10 elementos para classificar-se de forma inteligente em relação a todos os outros membros da coleção. Porque todo mundo também vai olhar para 10 elementos, e o comportamento emergente é orquestrado da maneira correta, de modo que isso seja suficiente para produzir uma lista ordenada.
  • O ( n !): Um algoritmo que “tenta tudo”, já que existem (proporcionalmente) n ! combinações possíveis de n elementos que podem resolver um determinado problema. Então, apenas faz um loop em todas essas combinações, tenta-as e depois pára sempre que consegue.

A resposta de don.neufeld é muito boa, mas eu provavelmente explicaria isso em duas partes: primeiro, há uma hierarquia aproximada de O () na qual a maioria dos algoritmos se enquadra. Então, você pode ver cada uma delas para esboçar os algoritmos típicos dessa complexidade de tempo.

Para fins práticos, os únicos O () que parecem importar são:

  • O (1) “tempo constante” – o tempo necessário é independente do tamanho da input. Como uma categoria aproximada, eu includeia algoritmos como pesquisas de hash e Union-Find aqui, mesmo que nenhum deles seja realmente O (1).
  • O (log (n)) “logarítmico” – fica mais lento à medida que você obtém insumos maiores, mas, uma vez que sua input fique razoavelmente grande, ela não mudará o suficiente para se preocupar. Se o seu tempo de execução estiver ok com dados de tamanho razoável, você poderá inundá-lo com o máximo de dados adicionais que desejar e ainda assim ficará bem.
  • O (n) “linear” – quanto mais input, mais tempo demora, em uma troca de palavras. Três vezes o tamanho da input levará cerca de três vezes mais tempo.
  • O (n log (n)) “melhor que quadrático” – aumentar o tamanho da input dói, mas ainda é gerenciável. O algoritmo é provavelmente decente, é apenas que o problema subjacente é mais difícil (as decisões são menos localizadas em relação aos dados de input) do que os problemas que podem ser resolvidos em tempo linear. Se seus tamanhos de input estiverem chegando lá, não presuma que você poderia lidar com o dobro do tamanho sem alterar sua arquitetura (por exemplo, movendo as coisas para cálculos de lote noturno ou não fazendo coisas por quadro). Tudo bem se o tamanho da input aumentar um pouco; apenas atente para múltiplos.
  • O (n ^ 2) “quadrático” – é realmente só vai funcionar até um certo tamanho de sua input, então preste atenção em quão grande ele poderia ficar. Além disso, o seu algoritmo pode chupar – pense muito para ver se existe um algoritmo O (n log (n)) que lhe daria o que você precisa. Quando estiver aqui, fique muito agradecido pelo incrível hardware que nos foi presenteado. Não faz muito tempo, o que você está tentando fazer seria impossível para todos os propósitos práticos.
  • O (n ^ 3) “cúbico” – não qualitativamente tão diferente de O (n ^ 2). Os mesmos comentários se aplicam, só que mais. Há uma chance decente de que um algoritmo mais inteligente possa reduzir esse tempo para algo menor, por exemplo, O (n ^ 2 log (n)) ou O (n ^ 2.8 …), mas, novamente, há uma boa chance de que não valerá a pena. (Você já está limitado em seu tamanho prático de input, portanto, os fatores constantes que podem ser necessários para os algoritmos mais espertos provavelmente aumentarão suas vantagens em casos práticos. Além disso, o raciocínio é lento; deixar o computador mastigá-lo pode economizar tempo No geral.)
  • O (2 ^ n) “exponencial” – o problema é fundamentalmente computacionalmente difícil ou você está sendo um idiota. Esses problemas têm um sabor reconhecível para eles. Seus tamanhos de input são limitados a um limite rígido bastante específico. Você saberá rapidamente se você se encheckbox nesse limite.

E é isso. Existem muitas outras possibilidades que se encheckboxm entre elas (ou são maiores que O (2 ^ n)), mas elas geralmente não acontecem na prática e não são qualitativamente muito diferentes de uma delas. Os algoritmos cúbicos já são um pouco exagerados; Eu só os incluí porque eu os encontrei com freqüência suficiente para valer a pena mencionar (por exemplo, multiplicação de matrizes).

O que está realmente acontecendo para essas classs de algoritmos? Bem, acho que você teve um bom começo, embora haja muitos exemplos que não se encheckboxm nessas caracterizações. Mas para o acima, eu diria que geralmente é algo como:

  • O (1) – você só está olhando mais em um pedaço de tamanho fixo de seus dados de input e, possivelmente, nada disso. Exemplo: o máximo de uma lista classificada.
    • Ou o seu tamanho de input é limitado. Exemplo: adição de dois números. (Observe que a adição de N números é tempo linear.)
  • O (log n) – cada elemento da sua input lhe diz o suficiente para ignorar uma grande fração do resto da input. Exemplo: quando você olha para um elemento de matriz na pesquisa binária, seu valor informa que você pode ignorar “metade” de sua matriz sem olhar para nada dela. Ou da mesma forma, o elemento que você olha dá-lhe um resumo de uma fração da input restante que você não precisa olhar para ele.
    • Não há nada de especial sobre as metades – se você só pode ignorar 10% da sua input em cada etapa, ela ainda é logarítmica.
  • O (n) – você faz uma quantidade fixa de trabalho por elemento de input. (Mas veja abaixo)
  • O (n log (n)) – existem algumas variantes.
    • Você pode dividir a input em duas pilhas (em tempo não mais que linear), resolver o problema de forma independente em cada pilha e, em seguida, combinar as duas pilhas para formar a solução final. A independência das duas pilhas é fundamental. Exemplo: mergesort recursivo clássico.
    • Cada passagem de tempo linear nos dados leva você à metade da sua solução. Exemplo: quicksort se você pensar em termos da distância máxima de cada elemento para sua posição ordenada final em cada passo de particionamento (e sim, eu sei que é de fato O (n ^ 2) por causa das escolhas de pivô degeneradas. cai na minha categoria O (n log (n)).)
  • O (n ^ 2) – você tem que olhar para cada par de elementos de input.
    • Ou você não, mas pensa que sim, e está usando o algoritmo errado.
  • O (n ^ 3) – hum … Eu não tenho uma caracterização rápida destes. É provavelmente um dos:
    • Você está multiplicando matrizes
    • Você está olhando para cada par de inputs, mas a operação que você faz requer olhar para todas as inputs novamente
    • toda a estrutura gráfica de sua input é relevante
  • O (2 ^ n) – você precisa considerar todos os subconjuntos possíveis de suas inputs.

Nenhum destes é rigoroso. Especialmente algoritmos de tempo não linear (O (n)): Eu poderia apresentar um número de exemplos onde você tem que olhar para todas as inputs, depois para metade, depois para metade, etc. Ou vice-versa – – você dobra juntos pares de inputs, depois recorre à saída. Estes não se encheckboxm na descrição acima, já que você não está olhando para cada input uma vez, mas ainda aparece em tempo linear. Ainda assim, 99,2% do tempo, o tempo linear significa olhar para cada input uma vez.

Muitos deles são fáceis de demonstrar com algo que não é programação, como embaralhar cartas.

Classificando um baralho de cartas indo pelo baralho inteiro para encontrar o ás de espadas, passando pelo baralho inteiro até encontrar o 2 de espadas, e assim por diante, seria o pior caso n ^ 2, se o baralho já estivesse classificado para trás. Você olhou para todas as 52 cartas 52 vezes.

Em geral, os algoritmos realmente ruins não são necessariamente intencionais, eles geralmente são um mau uso de outra coisa, como chamar um método que é linear dentro de algum outro método que se repete linearmente no mesmo conjunto.

Ok – há algumas respostas muito boas aqui, mas quase todas parecem cometer o mesmo erro e é uma que está impregnando o uso comum.

Informalmente, escrevemos que f (n) = O (g (n)) se, até um fator de escala e para todo n maior que algum n0, g (n) é maior que f (n). Ou seja, f (n) não cresce mais rápido do que, ou é limitado de cima por, g (n). Isso não nos diz nada sobre o quão rápido f (n) cresce, exceto pelo fato de que é garantido que não é pior que g (n).

Um exemplo concreto: n = O (2 ^ n). Todos nós sabemos que n cresce muito menos rapidamente do que 2 ^ n, de modo que nos permite dizer que é limitado por cima pela function exponencial. Há muito espaço entre n e 2 ^ n, então não é um limite muito apertado , mas ainda é um limite legítimo.

Por que nós (cientistas da computação) usamos limites em vez de sermos exatos? Porque a) os limites são geralmente mais fáceis de serem testados e b) nos dá uma mão curta para expressar as propriedades dos algoritmos. Se eu disser que meu novo algoritmo é O (n.log n) isso significa que no pior caso seu tempo de execução será limitado de cima por n.log n em n inputs, por grande o suficiente n (embora veja meus comentários abaixo quando eu não quis dizer pior caso).

Se em vez disso, queremos dizer que uma function cresce exatamente tão rapidamente quanto alguma outra function, usamos theta para fazer esse ponto (eu escreverei T (f (n)) para significar \ Theta de f (n) no markdown) . T (g (n)) é uma mão curta para ser limitada de cima para baixo por g (n), novamente, até um fator de escala e assimptoticamente.

Isso é f (n) = T (g (n)) <=> f (n) = O (g (n)) e g (n) = O (f (n)). Em nosso exemplo, podemos ver que n! = T (2 ^ n) porque 2 ^ n! = O (n).

Por que se preocupar com isso? Porque na sua pergunta você escreve ‘alguém teria que fumar crack para escrever um O (x!)?’ A resposta é não – porque basicamente tudo que você escreve será delimitado de cima pela function fatorial. O tempo de execução do quicksort é O (n!) – não é apenas um limite apertado.

Há também uma outra dimensão de sutileza aqui. Normalmente, estamos falando sobre a pior input quando usamos a notação O (g (n)), de modo que estamos fazendo uma instrução composta: no pior dos casos, o tempo não será pior do que um algoritmo que g (n ) passos, novamente escala de módulo e para n grande o suficiente. Mas às vezes queremos falar sobre o tempo de execução da média e até mesmo os melhores casos.

O quicksort de baunilha é, como sempre, um bom exemplo. É T (n ^ 2) no pior dos casos (na verdade, leva pelo menos n ^ 2 passos, mas não significativamente mais), mas T (n.log n) no caso médio, que é o número esperado de etapas é proporcional ao n.log n. No melhor dos casos, também é T (n.log n) – mas você poderia melhorar isso, por exemplo, verificando se a matriz já estava classificada, nesse caso o melhor tempo de execução seria T (n).

Como isso se relaciona com sua pergunta sobre as realizações práticas desses limites? Bem, infelizmente, a notação O () esconde constantes com as quais as implementações do mundo real têm que lidar. Então, embora possamos dizer que, por exemplo, para uma operação T (n ^ 2), temos que visitar todos os pares de elementos possíveis, não sabemos quantas vezes temos que visitá-los (exceto que não é uma function de n). Assim, poderíamos ter que visitar cada par 10 vezes, ou 10 ^ 10 vezes, e a declaração T (n ^ 2) não faz distinção. As funções de ordem inferior também estão ocultas – poderíamos ter de visitar cada par de elementos uma vez e cada elemento individual 100 vezes, porque n ^ 2 + 100n = T (n ^ 2). A idéia por trás da notação O () é que, para n grande o suficiente, isso não importa, pois n ^ 2 é muito maior do que 100n, e nem percebemos o impacto de 100n no tempo de execução. No entanto, muitas vezes lidamos com “suficientemente pequenos”, de modo que fatores constantes e assim por diante façam uma diferença real e significativa.

Por exemplo, quicksort (custo médio T (n.log n)) e heapsort (custo médio T (n.log n)) são ambos algoritmos de ordenação com o mesmo custo médio – ainda que o quicksort seja tipicamente muito mais rápido que o heapsort. Isso ocorre porque o heapsort faz mais algumas comparações por elemento do que o quicksort.

Isso não quer dizer que a notação de O () é inútil, apenas imprecisa. É uma ferramenta bastante contundente para usar em pequenos n.

(Como nota final deste tratado, lembre-se que a notação O () apenas descreve o crescimento de qualquer function – não necessariamente tem que ser hora, pode ser memory, mensagens trocadas em um sistema distribuído ou número de CPUs necessárias para um algoritmo paralelo.)

Eu tento explicar, dando exemplos de código simples em c #.

Para List numbers = new List {1,2,3,4,5,6,7,12,543,7};

O (1) parece

 return numbers.First(); 

O (n) parece

 int result = 0; foreach (int num in numbers) { result += num; } return result; 

O (n log (n)) parece

 int result = 0; foreach (int num in numbers) { int index = numbers.length - 1; while (index > 1) { // yeah, stupid, but couldn't come up with something more useful :-( result += numbers[index]; index /= 2; } } return result; 

O (n ^ 2) parece

 int result = 0; foreach (int outerNum in numbers) { foreach (int innerNum in numbers) { result += outerNum * innerNum; } } return result; 

O (n!) Parece cansar de pensar em algo simples.
Mas eu espero que você consiga o ponto geral?

A maneira como eu descrevo isso para meus amigos não técnicos é assim:

Considere a adição de vários dígitos. Boa e antiga adição de lápis e papel. O tipo que você aprendeu quando tinha 7-8 anos de idade. Dados dois números de três ou quatro dígitos, você pode descobrir o que eles adicionam com bastante facilidade.

Se eu te desse dois números de 100 dígitos, e te perguntasse o que eles acrescentam, descobrir seria bem direto, mesmo se você tivesse que usar lápis e papel. Um garoto shiny poderia fazer tal adição em apenas alguns minutos. Isso exigiria apenas cerca de 100 operações.

Agora, considere a multiplicação de vários dígitos. Você provavelmente aprendeu isso por volta dos 8 ou 9 anos de idade. Você (espero) fez muitos exercícios repetitivos para aprender a mecânica por trás disso.

Agora, imagine que eu te dei os mesmos dois números de 100 dígitos e lhe disse para multiplicá-los juntos. Esta seria uma tarefa muito, muito mais difícil, algo que levaria horas para você fazer – e que seria improvável que você fizesse sem erros. A razão para isto é que (esta versão de) multiplicação é O (n ^ 2); cada dígito no número inferior tem que ser multiplicado por cada dígito no número superior, deixando um total de cerca de n ^ 2 operações. No caso dos números de 100 dígitos, são 10.000 multiplicações.

Não, um algoritmo O (n) não significa que irá executar uma operação em cada elemento. A notação Big-O oferece uma maneira de falar sobre a “velocidade” do seu algoritmo independente da sua máquina real.

O (n) significa que o tempo que seu algoritmo levará cresce linearmente conforme sua input aumenta. O (n ^ 2) significa que o tempo que o seu algoritmo leva cresce como o quadrado da sua input. E assim por diante.

A maneira que eu penso sobre isso, é que você tem a tarefa de limpar um problema causado por algum vilão maligno V que escolhe N, e você tem que estimar quanto tempo levará para terminar seu problema quando ele aumentar N.

O (1) -> aumentar N realmente não faz diferença alguma

O (log (N)) -> sempre que V duplica N, você tem que gastar uma quantia extra de tempo T para completar a tarefa. V duplica N novamente e você gasta a mesma quantia.

O (N) -> sempre que V duplica N, você gasta o dobro do tempo.

O (N ^ 2) -> toda vez que V dobra N, você gasta 4x tanto tempo. (não é justo!!!)

O (N log (N)) -> sempre que V duplica N, você gasta o dobro do tempo e um pouco mais.

Estes são limites de um algoritmo; cientistas de computação querem descrever quanto tempo levará para grandes valores de N. (o que é importante quando você está fatorando números usados ​​em criptografia – se os computadores aceleram em um fator de 10, quantos mais bits você tem que usar para garantir que ainda levará 100 anos para quebrar sua criptografia e não apenas 1 ano?)

Alguns dos limites podem ter expressões estranhas, se isso fizer diferença para as pessoas envolvidas. Eu vi coisas como O (N log (N) log (log (N))) em algum lugar na Arte de Programação de Computador de Knuth para alguns algoritmos. (não me lembro qual deles está no topo da minha cabeça)

Uma coisa que ainda não foi tocada por algum motivo:

Quando você vê algoritmos com coisas como O (2 ^ n) ou O (n ^ 3) ou outros valores desagradáveis, isso geralmente significa que você terá que aceitar uma resposta imperfeita ao seu problema para obter um desempenho aceitável.

Soluções corretas que explodem assim são comuns quando se lida com problemas de otimização. Uma resposta quase correta entregue em um prazo razoável é melhor do que uma resposta correta entregue muito depois que a máquina se deteriorou.

Considere o xadrez: não sei exatamente qual é a solução correta, mas provavelmente é algo como O (n ^ 50) ou pior. É teoricamente impossível para qualquer computador calcular a resposta correta – mesmo se você usar todas as partículas no universo como um elemento de computação que executa uma operação no mínimo tempo possível para a vida do universo, você ainda tem muitos zeros . (Se um computador quântico pode resolvê-lo é outra questão.)

A “intuição” por trás de Big-O

Imagine uma “competição” entre duas funções sobre x, já que x se aproxima do infinito: f (x) eg (x).

Agora, se de algum ponto em (algum x) uma function sempre tiver um valor maior que o outro, então vamos chamar essa function de “mais rápida” que a outra.

Então, por exemplo, se para cada x> 100 você ver que f (x)> g (x), então f (x) é “mais rápido” que g (x).

Neste caso, diríamos g (x) = O (f (x)). f (x) representa uma espécie de “limite de velocidade” para g (x), uma vez que, por fim, passa e deixa para trás para sempre.

Esta não é exatamente a definição de notação big-O , que também afirma que f (x) só precisa ser maior que C * g (x) para alguma constante C (que é apenas outra maneira de dizer que você não pode ajude g (x) a ganhar a competição multiplicando-a por um fator constante – f (x) sempre vencerá no final. A definição formal também usa valores absolutos. Mas espero ter conseguido torná-lo intuitivo.

  • E alguém tem que fumar crack para escrever um O (x!)?

Não, apenas use o Prolog. Se você escrever um algoritmo de sorting no Prolog apenas descrevendo que cada elemento deve ser maior que o anterior, e deixar o backtracking fazer a sorting para você, isso será O (x!). Também conhecido como “permutation sort”.

Eu gosto da resposta de don neufeld, mas acho que posso acrescentar algo sobre O (n log n).

Um algoritmo que usa uma estratégia simples de dividir e conquistar provavelmente será O (log n). O exemplo mais simples disso é encontrar algo em uma lista classificada. Você não começa no início e procura por ele. Você vai para o meio, você decide se você deve ir para trás ou para frente, pular até a metade do último lugar que você olhou e repetir isso até encontrar o item que está procurando.

Se você observar os algoritmos quicksort ou mergesort, verá que ambos usam a abordagem de dividir a lista a ser classificada ao meio, classificando cada metade (usando o mesmo algoritmo, recursivamente) e, em seguida, recombinando as duas metades. Esse tipo de estratégia de divisão e conquista recursiva será O (n log n).

Se você pensar sobre isso com cuidado, você verá que o quicksort faz um algoritmo de particionamento O (n) em todos os n itens, então um O (n) particionando duas vezes em n / 2 itens e 4 vezes em n / 4 itens etc … até chegar em n partições em 1 item (que é degenerado). O número de vezes que você divide n na metade para chegar a 1 é aproximadamente log n, e cada etapa é O (n), então a divisão e conquista recursiva é O (n log n). O mergesort é construído de outra maneira, começando com n recombinações de 1 item e terminando com 1 recombinação de n itens, onde a recombinação de duas listas ordenadas é O (n).

Quanto a fumar crack para escrever um algoritmo O (n!), Você está a menos que você não tenha escolha. Acredita-se que o problema do vendedor ambulante dado acima seja um desses problemas.

A maioria dos livros de Jon Bentley (por exemplo, Programming Pearls ) cobre essas coisas de uma maneira realmente pragmática. Esta palestra dada por ele inclui uma dessas análises de um quicksort.

Embora não seja totalmente relevante para a questão, Knuth teve uma idéia interessante : ensinar a notação Big-O em aulas de cálculo do ensino médio, embora eu ache essa idéia bastante excêntrica.

Pense nisso como empilhar blocos de lego (n) verticalmente e saltar sobre eles.

O (1) significa que a cada passo você não faz nada. A altura permanece a mesma.

O (n) significa que a cada passo você empilha blocos c, onde c1 é uma constante.

O (n ^ 2) significa que a cada passo, você empilha blocos c2xn, onde c2 é uma constante, e n é o número de blocos empilhados.

O (nlogn) significa que a cada passo, você empilha blocos c3 xnx log n, onde c3 é uma constante, e n é o número de blocos empilhados.

Para entender O (n log n), lembre-se de que log n significa log-base-2 de n. Então olhe para cada parte:

O (n) é, mais ou menos, quando você opera em cada item do conjunto.

O (log n) é quando o número de operações é o mesmo que o expoente para o qual você aumenta 2, para obter o número de itens. Uma busca binária, por exemplo, tem que cortar o conjunto no meio log n vezes.

O (n log n) é uma combinação – você está fazendo algo ao longo das linhas de uma pesquisa binária para cada item no conjunto. Classes eficientes geralmente operam fazendo um loop por item, e em cada loop fazendo uma boa pesquisa para encontrar o lugar certo para colocar o item ou grupo em questão. Daí n * log n.

Apenas para responder aos comentários no meu post acima:

Domenic – Estou neste site e me importo. Não por causa do pedantismo, mas porque nós – como programadores – normalmente nos preocupamos com a precisão. Usar a notação O () incorretamente no estilo que alguns fizeram aqui torna isso meio sem sentido; podemos dizer que algo toma n ^ 2 unidades de tempo como O (n ^ 2) sob as convenções usadas aqui. Usando o O () não adiciona nada. Não é apenas uma pequena discrepância entre o uso comum e a precisão matemática de que estou falando, é a diferença entre ser significativo e não.

Conheço muitos e muitos excelentes programadores que usam esses termos com precisão. Dizer ‘oh, nós somos programadores, portanto, não nos importamos’ economiza toda a empresa.

onebyone – Bem, não realmente embora eu tome o seu ponto. Não é O (1) para n arbitrariamente grande, que é uma espécie de definição de O (). Isso apenas mostra que O () tem aplicabilidade limitada para n limitado, onde preferiríamos realmente falar sobre o número de passos dados ao invés de um limite naquele número.

Diga ao seu log de oito anos (n) significa o número de vezes que você tem que cortar um comprimento n log em dois para que ele caia para o tamanho n = 1: p

O (n log n) é geralmente classificar O (n ^ 2) é geralmente comparar todos os pares de elementos

Suponha que você tenha um computador que possa resolver um problema de um determinado tamanho. Agora imagine que podemos dobrar o desempenho algumas vezes. Quanto maior um problema podemos resolver com cada duplicação?

Se pudermos resolver um problema do dobro do tamanho, é O (n).

Se tivermos algum multiplicador que não seja um, isso é algum tipo de complexidade polinomial. Por exemplo, se cada duplicação nos permitir aumentar o tamanho do problema em cerca de 40%, será O (n ^ 2) e cerca de 30% será O (n ^ 3).

Se adicionarmos apenas ao tamanho do problema, é exponencial ou pior. Por exemplo, se cada duplicação significa que podemos resolver um problema 1 maior, é O (2 ^ n). (É por isso que a força bruta de uma chave de criptografia torna-se efetivamente impossível com chaves de tamanho razoável: uma chave de 128 bits requer cerca de 16 quintilhões de vezes mais processamento do que uma de 64 bits.)

Lembre-se da fábula da tartaruga e da lebre (tartaruga e coelho)?

A longo prazo, a tartaruga vence, mas no curto prazo a lebre vence.

Isso é como O (logN) (tartaruga) vs. O (N) (lebre).

Se dois methods diferem em seu grande O, então há um nível de N no qual um deles vencerá, mas big-O não diz nada sobre quão grande esse N é.

Para permanecer sincero à pergunta feita eu responderia a pergunta da maneira que eu responderia a uma criança de 8 anos

Suponha que um vendedor de sorvetes prepare vários sorvetes (digamos, N) de formas diferentes organizadas de maneira ordenada. Você quer comer o sorvete deitado no meio

Caso 1: – Você pode comer um sorvete apenas se tiver comido todos os sorvetes menores do que você Você terá que comer metade de todos os sorvetes preparados (input). A resposta depende diretamente do tamanho da input. da ordem o (N)

Caso 2: – Você pode comer diretamente o sorvete no meio

A solução será O (1)

Caso 3: Você só pode comer um sorvete se você tiver comido todos os sorvetes menores do que ele e cada vez que você comer um sorvete você permitir que outro garoto (criança nova) coma todos os sorvetes dele. + N + N ……. (N / 2) vezes A solução será O (N2)

log (n) significa crescimento logarítmico. Um exemplo seria dividir e conquistar algoritmos. Se você tem 1000 números ordenados em uma matriz (ex. 3, 10, 34, 244, 1203 …) e deseja procurar um número na lista (encontre sua posição), você pode começar verificando o valor da número no índice 500. Se for inferior ao que você procura, pule para 750. Se for maior do que o que você procura, pule para 250. Em seguida, repita o processo até encontrar seu valor (e chave). Toda vez que pulamos metade do espaço de busca, podemos testar vários outros valores, já que sabemos que o número 3004 não pode estar acima do número 5000 (lembre-se, é uma lista ordenada).

n log (n) significa n * log (n).

Vou tentar realmente escrever uma explicação para um menino de oito anos de idade, além de termos técnicos e noções matemáticas.

Como exatamente o que uma operação O(n^2) faria?

Se você está em uma festa, e não há pessoas na festa, incluindo você. Quantos apertos de mão são necessários para que todos tenham apertado as mãos de todos, uma vez que as pessoas provavelmente esquecerão de quem foram manipulados em algum momento.

Nota: isto se aproxima de um simplex rendendo n(n-1) que é próximo o suficiente para n^2 .

E o que diabos isso significa se uma operação é O(n log(n)) ?

Seu time favorito venceu, eles estão na fila, e há n jogadores na equipe. Quantos hanshakes você levaria para o aperto de mão de cada jogador, dado que você irá acenar cada um várias vezes, quantas vezes, quantos dígitos estão no número de jogadores n .

Note: this will yield n * log n to the base 10 .

And does somebody have to smoke crack to write an O(x!) ?

You are a rich kid and in your wardrobe there are alot of cloths, there are x drawers for each type of clothing, the drawers are next to each others, the first drawer has 1 item, each drawer has as many cloths as in the drawer to its left and one more, so you have something like 1 hat, 2 wigs, .. (x-1) pants, then x shirts. Now in how many ways can you dress up using a single item from each drawer.

Note: this example represent how many leaves in a decision-tree where number of children = depth , which is done through 1 * 2 * 3 * .. * x