Big-O para Eight Year Olds? [duplicado]
https://stackoverflow.com/questions/107165
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Esta questão já tem uma resposta aqui:
Eu estou perguntando mais sobre o que isso significa para o meu código. Eu entendo os conceitos matematicamente, eu só tenho um tempo difícil envolver minha cabeça em torno do que eles significam conceitualmente. Por exemplo, se fosse para realizar um O (1) operação em uma estrutura de dados, eu entendo que o número de operações que tem de realizar não vai crescer porque há mais itens. E um (n) operação O que significaria que você iria realizar um conjunto de operações em cada elemento. Poderia preencher alguém os espaços em branco aqui?
- Como o que exatamente seria um O (n ^ 2) operação de fazer?
- E o que diabos significa se uma operação é O (n log (n))?
- E será que alguém tem que fumar crack para escrever um O (x!)?
Solução
Uma maneira de pensar sobre isso é o seguinte:
O (n ^ 2) significa que para cada elemento, você está fazendo algo com todos os outros elementos, tais como compará-los. Bubble sort é um exemplo disso.
O (N log N) significa que para cada elemento, você está fazendo algo que só precisa de olhar para log N dos elementos. Isso geralmente é porque você sabe algo sobre os elementos que permitem fazer uma escolha eficiente. A maioria dos tipos eficientes são um exemplo disso, como merge sort.
O (N!) Meios para fazer algo para todas as permutações possíveis dos N elementos. Caixeiro viajante é um exemplo disso, onde existem N! maneiras de visitar os nós, e a solução de força bruta é de olhar para o custo total de todas as permutações possíveis para encontrar o melhor um.
Outras dicas
A grande coisa que meios Big-O notação para o código é a forma como ele será ampliado quando você dobrar a quantidade de "coisas" que opera. Aqui está um exemplo concreto:
Big-O | computations for 10 things | computations for 100 things ---------------------------------------------------------------------- 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, tome quicksort que é O (n log (n)) vs bubble sort que é O (n ^ 2). Ao classificar 10 coisas, quicksort é 3 vezes mais rápido do que bubble sort. Mas quando classificando 100 coisas, é 14 vezes mais rápido! Claramente escolhendo o algoritmo mais rápido é importante, então. Quando você começa a bases de dados com milhões de linhas, pode significar a diferença entre a sua consulta em execução em 0,2 segundos, contra levando 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 calcular 100 coisas um dia, dobrando a velocidade do processador só você fica 125 coisas em um dia. No entanto, bata esse cálculo para O (n ^ 2) e você está fazendo 1000 coisas por dia.
esclarecimento: Na verdade, Big-O não diz nada sobre o desempenho comparativo de algoritmos diferentes no mesmo ponto tamanho específico, mas sim sobre o desempenho comparativo do mesmo algoritmo em diferentes pontos do tamanho:
computations computations computations Big-O | for 10 things | for 100 things | for 1000 things ---------------------------------------------------------------------- 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 que é útil para visualizá-lo:
Além disso, em
Isso pode ser muito matemático, mas aqui é a minha tentativa. (I am um matemático.)
Se algo é O ( f ( n )), então ele está correndo o tempo em n elementos será igual ao A f ( n ) + B (medido em, digamos, ciclos de clock ou operações de CPU). É a chave para a compreensão de que você também tem essas constantes A e B , que surgem a partir da implementação específica. B representa essencialmente a "sobrecarga constante" de sua operação, por exemplo, alguns pré-processamento que você faça isso não depende do tamanho da coleção. A representa a velocidade de seu algoritmo real de processamento de item.
A chave, porém, é que você usar a notação O grande descobrir quão bem algo vai escalar . Então, essas constantes não vai realmente importa: se você está tentando descobrir como escalar de 10 a 10 mil itens, que se preocupa com a constante sobrecarga B ? Da mesma forma, outras preocupações (veja abaixo) certamente superam o peso da constante multiplicativa A .
Então, o negócio real é f ( n ). Se f não cresce em tudo com n , por exemplo, f ( n ) = 1, então você vai escalar fantasticamente --- o seu tempo de execução vai ser só A + B . Se f cresce linearmente com
Na prática, aqui estão alguns exemplos bons:
- O (1): recuperar um elemento de uma matriz. Nós sabemos exatamente onde ele está na memória, então apenas ir buscá-la. Não importa se a coleção tem 10 itens ou 10000; ele ainda está no índice (digamos) 3, de modo que apenas saltar para o local 3 na memória.
- O ( n ): recuperar um elemento de uma lista ligada. Aqui, A = 0,5, porque, em média, you''ll tem que passar por 1/2 da lista ligada antes de encontrar o elemento que você está procurando.
- O ( n 2 ): vários "burras" algoritmos de ordenação. Porque geralmente sua estratégia envolve, para cada elemento ( n ), você olha para todos os outros elementos (assim vezes outro n , dando n < sup> 2 ), então se posicionar no lugar certo.
- O ( n log ( n )): vários "inteligentes" algoritmos de ordenação. Acontece que você só precisa olhar para, digamos, 10 elementos em um 10 -element coleção 10 a inteligentemente espécie-se em relação ao todos else na coleção. Porque todo mundo é também vamos olhar para 10 elementos, eo comportamento emergente é orquestrado apenas para a direita assim que este é o suficiente para produzir uma lista ordenada.
- O ( n !): Um algoritmo que "tenta de tudo," uma vez que existem (proporcional) n ! combinações possíveis de n elementos que podem resolver um determinado problema. Por isso só percorre todas essas combinações, tenta-los, em seguida, pára sempre que ele consegue.
A resposta de don.neufeld é muito bom, mas eu provavelmente vou explicá-lo em duas partes: primeiro, há uma hierarquia aproximada do O () é que a maioria dos algoritmos de cair. Em seguida, você pode olhar para cada um desses para chegar a esboços do que típico algoritmos de que a complexidade de tempo fazer.
Para fins práticos, a única O () é que nunca parece importar são:
- O (1) "constante de tempo" - o tempo necessário é independente do tamanho da entrada. Como uma categoria difícil, eu incluiria algoritmos tais como pesquisas de hash e União-Encontre aqui, embora nenhum deles são realmente O (1).
- O (log (n)) "logarítmica" - torna-se mais lento à medida que você começa entradas maiores, mas uma vez que sua entrada fica bastante grande, isso não vai mudar o suficiente para se preocupar. Se o seu tempo de execução é ok com dados razoavelmente porte, você pode afundar-lo com o máximo de dados adicionais como você quer e ele ainda vai ser ok.
- O (n) "linear" - a mais de entrada, o que leva mais tempo, em uma troca mesmo. Três vezes o tamanho da entrada levará cerca de três vezes mais tempo.
- O (n log (n)) "melhor do que quadrática" - o aumento do tamanho da entrada dói, mas ainda é administrável. O algoritmo é provavelmente decente, é apenas que o problema subjacente é mais difícil (as decisões são menos localizada no que diz respeito aos dados de entrada) do que aqueles problemas que podem ser resolvidos em tempo linear. Se os seus tamanhos de entrada estão ficando lá em cima, não assuma que você poderia necessariamente lidar com o dobro do tamanho sem alterar sua arquitetura ao redor (por exemplo, movendo coisas para cálculos em lote durante a noite, ou não fazer as coisas per-frame). É ok, se o tamanho da entrada aumenta um pouco, embora; apenas atente para múltiplos.
- O (n ^ 2) "quadrática" - é realmente só vai funcionar até um determinado tamanho de sua entrada, então preste atenção para o quão grande ele poderia conseguir. Além disso, o algoritmo pode sugar - pensar muito para ver se há um algoritmo O (n log (n)), que iria dar-lhe o que você precisa. Uma vez que você está aqui, me sinto muito grato pela incrível hardware temos sido dotado. Não muito tempo atrás, o que você está tentando fazer teria sido impossível para todos os efeitos práticos.
- O (n ^ 3) "cúbico" - não qualitativamente muito diferente de O (n ^ 2). As mesmas observações se aplicam, só que mais assim. Há uma boa chance de que um algoritmo mais inteligente poderia raspar desta vez para baixo para algo menor, por exemplo, O (n ^ 2 log (n)) ou O (n ^ 2,8 ...), mas, novamente, há uma boa chance de que ele não vai valer a pena. (Você já está limitado no seu tamanho de entrada prático, de modo que os fatores constantes que podem ser necessárias para os algoritmos mais inteligentes provavelmente vai inundar as suas vantagens para os casos práticos Além disso, o pensamento é lento;. Permitindo que a mastigação computador nele podem lhe poupar tempo em geral.)
- O (2 ^ n) "exponencial" - o problema é ou fundamentalmente computacionalmente difícil ou você está sendo um idiota. Estes problemas têm um sabor reconhecível para eles. Seus tamanhos de entrada são limitadas a um limite rígido bastante específico. Você vai saber rapidamente se você se encaixa esse limite.
E é isso. Existem muitas outras possibilidades que se encaixam entre estes (ou são maiores do que O (2 ^ n)), mas eles não acontecem muitas vezes na prática, e eles não são qualitativamente muito diferente de um deles. algoritmos cúbicos já é um bocado de um estiramento; Eu só incluiu-los, porque eu correr em-los com freqüência suficiente para valer a pena mencionar (por exemplo matriz de multiplicação).
O que está realmente acontecendo para estas classes de algoritmos? Bem, eu acho que você teve um bom começo, embora existam muitos exemplos que não caberiam essas caracterizações. Mas para o acima, eu diria que geralmente é algo como:
- O (1) - você está olhando apenas para o mais em um pedaço de tamanho fixo dos seus dados de entrada, e, possivelmente, nada disso. Exemplo: o máximo de uma lista ordenada.
- ou o tamanho da entrada é limitada. Exemplo: adição de dois números. (Note-se que a adição de N números é tempo linear.)
- O (log n) - cada elemento da sua entrada diz-lhe o suficiente para ignorar uma grande parte do resto da entrada. Exemplo: quando você olha para um elemento da matriz em busca binária, o seu valor lhe diz que você pode ignorar "metade" de sua matriz sem olhar para nada disso. Ou semelhante, o elemento você olhar para dá-lhe o suficiente de um resumo de uma fração da entrada restante que você não vai precisar de olhar para ele.
- Não há nada de especial sobre metades, embora -. Se você só pode ignorar 10% de sua entrada em cada etapa, ainda é logarítmica
- O (n) - você faz uma certa quantidade fixa de trabalho por elemento de entrada. (Mas veja abaixo).
- O (n log (n)) - existem algumas variantes.
- Você pode dividir a entrada em duas pilhas (em não mais do que o tempo 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:. Clássica mergesort recursiva
- Cada passagem de tempo linear ao longo dos dados você fica a meio caminho para sua solução. Exemplo: quicksort se você pensar em termos de distância máxima de cada elemento na sua posição ordenada final, em cada etapa de particionamento (e sim, eu sei que ele é realmente O (n ^ 2) por causa das escolhas de articulação degenerados Mas em termos práticos, isso. cai em meu O (n log (n)) categoria.)
- O (n ^ 2) - você tem que olhar para cada par de elementos de entrada.
- Ou você não faz, mas você acha que fazer, e você estiver usando o algoritmo errado.
- O (n ^ 3) - hum ... eu não tenho uma caracterização ágil destes. É provavelmente um dos seguintes:
- Você está multiplicando matrizes
- Você está olhando para cada par de entradas, mas a operação você faz requer olhando para todas as entradas novamente
- toda a estrutura gráfico da sua entrada é relevante
- O (2 ^ n) - é preciso considerar todos os possíveis subconjunto de suas entradas .
Nenhum destes são rigorosos. algoritmos de tempo, especialmente, não lineares (O (n)): eu poderia vir acima com um número de exemplos onde você tem que olhar para todas as entradas, em seguida, a metade deles, em seguida, metade das pessoas, etc. Ou o contrário - - você dobra juntos pares de entradas, em seguida, recurse na saída. Estes não se encaixa na descrição acima, desde que você não está olhando para cada entrada de uma vez, mas ainda sai em tempo linear. Ainda assim, 99,2% do tempo, meio tempo linear olhando para cada entrada de uma vez.
Um monte de estes são fáceis de demonstrar com os não-programação algo, como baralhar cartões.
Classificando um baralho de cartas, passando por toda a plataforma para encontrar o ás de espadas, em seguida, passar por todo o convés para encontrar o 2 de espadas, e assim por diante seria pior caso n ^ 2, se o pavimento já estava para trás ordenados. Você olhou para todas as 52 cartas 52 vezes.
Em geral, os algoritmos muito ruins não são necessariamente intencional, eles são comumente um desvio de outra coisa, como a chamada de um método que é linear dentro de algum outro método que repete o mesmo conjunto linearmente.
Ok - existem algumas respostas muito boas aqui, mas quase todos eles parecem fazer o mesmo erro e é um que está permeando uso comum.
Informalmente, nós escrevemos que f (n) = O (g (n)) se, até um fator de escala e para todo n maior do que alguns n0, g (n) é maior que f (n). Isto é, f (n) cresce há mais rápido que, ou é delimitada por cima por, g (n). Isso não nos diz nada sobre o quão rápido f (n) cresce, exceto pelo fato de que ele não é garantido para ser pior do que g (n).
Um exemplo concreto: n = O (2 ^ n). Nós todos sabemos que n cresce muito menos rapidamente do que 2 ^ n, de modo que nos credencia a dizer que é delimitada por cima pela função exponencial. Há um monte de espaço entre n e 2 ^ n, por isso não é muito apertado limite, mas ainda é um limite legítimo.
Por que nós (cientistas da computação) de uso de limites ao invés de ser exata? Porque: a) limites são muitas vezes mais fácil de provar e b) dá-nos um curto-mão para expressar propriedades de algoritmos. Se eu disser que meu novo algoritmo é O (n.log n) que significa que, no pior dos casos a sua run-time serão delimitadas de cima por n.log n em n entradas, para n grande o suficiente (embora ver os meus comentários abaixo quando eu pode não significar pior caso).
Se em vez disso, queremos dizer que uma função cresce exatamente o mais rapidamente alguma outra função, usamos theta para fazer esse ponto (Vou escrever T (f (n)) para significar \ Theta de f (n) em remarcação). T (g (n)) é abreviada para ser limitado por
Que é f (n) = t (g (n)) <=> f (n) = O (g (n)) e g (n) = O (f (n)). No 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ê escrever "que alguém tem que fumar crack para escrever um O (x!)? A resposta é não - porque, basicamente, tudo que você escreve será delimitada de cima pela função fatorial. O tempo de execução de quicksort é O (n!) -. Não é apenas um apertado obrigado
Há também uma outra dimensão de sutileza aqui. Normalmente nós estamos falando sobre o pior de entrada caso quando usamos (g (n)) notação O, de modo que nós estamos fazendo uma instrução composta: no pior caso tempo de execução não será pior do que um algoritmo que leva g (n) etapas, de novo escalonamento de módulo e para n grande o suficiente. Mas às vezes nós queremos falar sobre o tempo de execução do média e até mesmo melhores casos.
Vanilla quicksort é, como sempre, um exemplo bom. É T (n ^ 2), no pior caso (ele vai realmente levar pelo menos n ^ 2 passos, mas não significativamente mais), mas T (n.log n) no caso da média, o que quer dizer o número esperado de passos é proporcional à n.log n. No melhor caso, também é T (n.log n) - mas você poderia melhorar isso para, por exemplo, verificar se a matriz já foi resolvido, caso em que o melhor caso de tempo de execução seria T (n)
Como isso se relaciona à sua pergunta sobre as realizações práticas desses limites? Bem, infelizmente, O () notação couros constantes que implementações do mundo real têm de lidar com. Assim, embora nós podemos dizer que, por exemplo, para um T (n ^ 2) a operação temos que visitar cada par possível de elementos, não sabemos quantas vezes nós temos para visitá-los (exceto que não é uma função de n). Para que pudéssemos ter de visitar cada par 10 vezes, ou 10 ^ 10 vezes, eo T (n ^ 2) declaração não faz distinção. funções de ordem mais baixos também estão escondidos - poderíamos ter que visitar cada par de elementos de uma só 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 em tudo, porque n ^ 2 fica muito maior do que 100n que nem percebe o impacto da 100n sobre o tempo de execução. No entanto, muitas vezes lidar com 'suficientemente pequeno' n, tais que os fatores constantes e assim por diante make umareal, diferença significativa.
Por exemplo, quick (custo médio T (n.log n)) e heapsort (custo médio T (n.log n)) são ambos algoritmos de classificação com o mesmo custo médio - ainda quick é tipicamente muito mais rápido do que heapsort. Isso ocorre porque heapsort faz mais algumas comparações por elemento de quicksort.
Isto não quer dizer que a notação O () é inútil, apenas imprecisa. É uma ferramenta bastante contundente para empunhar para pequenas n.
(Como nota final a este tratado, lembre-se que O () notação apenas descreve o crescimento de qualquer função - não tem necessariamente de ser o tempo, poderia ser memória, mensagens trocadas em um sistema ou número de distribuídos CPUs necessário para um algoritmo paralelo.)
Eu tento explicar, dando exemplos de código simples em C #.
Para List<int> numbers = new List<int> {1,2,3,4,5,6,7,12,543,7};
O (1) se parece com
return numbers.First();
O (n) se parece com
int result = 0;
foreach (int num in numbers)
{
result += num;
}
return result;
O (n log (n)) se parece com
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) se parece com
int result = 0;
foreach (int outerNum in numbers)
{
foreach (int innerNum in numbers)
{
result += outerNum * innerNum;
}
}
return result;
O (n!) Parece, uhm, para cansado para chegar a qualquer coisa simples.
Mas eu espero que você começa o ponto geral?
A forma como eu descrevê-lo aos meus amigos não técnicos é assim:
Considere além de vários dígitos. Bom complemento, lápis e papel antiquado. O tipo que você aprendeu quando você era 7-8 anos de idade. Dados dois números de três ou quatro dígitos, você pode descobrir o que eles adicionar até com bastante facilidade.
Se você me deu dois números 100 dígitos, e perguntou-lhe o que eles somam, descobrir isso seria bastante simples, mesmo se você tinha que usar lápis e papel. Um brilhante garoto poderia fazer uma adição tão em apenas alguns minutos. Isso só exigiria cerca de 100 operações.
Agora, considere a multiplicação de vários dígitos. Você provavelmente aprendeu que em torno de 8 ou 9 anos de idade. Você (espero) fez muitos exercícios repetitivos para aprender a mecânica por trás dele.
Agora, imagine que eu lhe dei esses mesmos dois números 100 dígitos e lhe disse para multiplicá-los juntos. Isso seria uma muito, muito tarefa mais difícil, algo que levaria horas para fazer - e que você seria improvável que o faça sem erros. A razão para isto é que (esta versão) multiplicação é O (n ^ 2); cada dígito do número de fundo tem de ser multiplicado por cada dígito do número de topo, deixando um total de cerca de n ^ 2 operações. No caso dos números 100 dígitos, que é 10.000 multiplicações.
Não, um O (n) algoritmo não significa que ele irá executar uma operação em cada elemento. notação Big-O dá-lhe uma maneira de falar sobre a "velocidade" de vocês algoritmo independente da sua máquina real.
O (n) significa que o tempo seu algoritmo levará cresce linearmente com o aumento de entrada. O (n ^ 2) significa que o tempo que o algoritmo leva cresce com o quadrado da sua entrada. E assim por diante.
A maneira que eu penso sobre isso, é que você tem a tarefa de limpar um problema causado por algum mal vilão V que pega N, e você tem que estimar o quanto mais tempo vai demorar para terminar o seu problema quando ele aumenta N.
O (1) -> aumentar N realmente não faz qualquer diferença em tudo
O (log (N)) -> cada vez V dobra N, você tem que gastar uma quantidade extra de tempo T para completar a tarefa. V dobra N novamente, e você gasta a mesma quantidade.
O (N) -.> Cada vez V dobra N, você gasta o dobro do tempo
O (n ^ 2) -> cada vez V dobra N, você gasta 4x tanto tempo. (Que não é justo !!!)
O (N log (N)) -> cada vez V dobra N, você gasta o dobro do tempo, mais um pouco mais
.Estes são limites de um algoritmo; cientistas da computação quero descrever quanto tempo vai levar para grandes valores de N. (que fica importante quando você são números de factoring que são usados ??na criptografia - se os computadores acelerar por um fator de 10, quantos mais bits fazer você tem que usar para garantir que ainda irá levá-los 100 anos para quebrar sua criptografia e não apenas 1 ano?)
Alguns dos limites pode ter expressões estranhas se ele faz a diferença para as pessoas envolvidas. Eu vi coisas assim (log (log (N)) log N (N)) em algum lugar O no Art of Computer Programming para alguns algoritmos de Knuth. (Não lembro qual deles fora do topo da minha cabeça)
Uma coisa que não tenha sido tocado no entanto, por algum motivo:
Quando você vê algoritmos com coisas como O (2 ^ n) ou O (n ^ 3) ou outros valores desagradáveis ??que muitas vezes significa que você vai ter que aceitar uma resposta imperfeita para o seu problema, a fim de obter um desempenho aceitável .
soluções corretas que explodem como esta são comuns quando se trata de problemas de otimização. A resposta quase-corrigir entregue em um prazo razoável é melhor do que uma resposta correta entregue muito depois de a máquina decaiu ao pó.
Considere xadrez: Eu não sei exatamente o que a solução correta é considerado mas é provavelmente algo como O (n ^ 50) ou ainda pior. É teoricamente impossível para qualquer computador para realmente calcular a resposta correta - mesmo se você usar cada partícula do universo como um elemento de computação executar uma operação no mínimo tempo possível para a vida do universo você ainda tem um monte de zeros à esquerda . (Se um computador quântico pode resolvê-lo é outra questão.)
O "Intuitition" por trás Big-O
Imagine uma "competição" entre duas funções ao longo x, como x se aproxima do infinito:. F (x) eg (x)
Agora, se de algum ponto da (alguns x) uma função sempre tem um valor maior que o outro, então vamos chamar essa função "mais rápido" do que o outro.
Assim, por exemplo, se para todo x> 100 você vê que f (x)> g (x), então f (x) é "mais rápido" do que g (x).
Neste caso, diríamos g (x) = O (f (x)). f (x) representa uma espécie de "limite de velocidade" das sortes para g (x), uma vez que, eventualmente, ele passa-lo e deixa-lo para trás para sempre.
Este não é exatamente a definição de big-O notação , que também afirma que f (x) só tem de ser maior do que C * g (x) para alguma constante C (que é apenas outra maneira de dizer que você não pode ajudar g (x) vencer a competição pela multiplicação por um factor constante - f (x) será sempre vencer no final). A definição formal também utiliza valores absolutos. Mas eu espero que eu consegui fazê-lo intuitiva.
- E será que alguém tem que fumar crack para escrever um O (x!)?
Não, é só usar Prolog. Se você escrever um algoritmo de ordenação em Prolog por apenas descrevendo que cada elemento deve ser maior do que o anterior, e deixe retrocesso fazer a triagem para você, que vai ser O (x!). Também conhecido como "tipo de permutação".
Eu gosto de resposta de Don Neufeld, mas acho que posso acrescentar algo sobre O (n log n).
Um algoritmo que utiliza uma divisão simples e estratégia de conquistar é provavelmente vai ser O (log n). O exemplo mais simples deste é encontrar uma coisa em uma lista ordenada. Você não começa no início e procurar por ele. Você vai para o meio, você decidir se você deve, em seguida, ir para frente ou para trás, saltar a meio caminho para o último lugar que você olhou, e repita isso até encontrar o item que você está procurando.
Se você olhar para as quicksort ou mergesort algoritmos, você vai ver que eles tanto tomar a abordagem de dividir a lista a ser classificada pela metade, classificando cada metade (usando o mesmo algoritmo, de forma recursiva), e então recombinar as duas metades . Este tipo de recursiva dividir e conquistar estratégia será O (n log n).
Se você pensar sobre isso com cuidado, verá que quicksort faz um O (n) particionamento algoritmo em todo o n itens, em seguida, um O (n) o particionamento duas vezes no n / 2 itens, em seguida, 4 vezes em n / 4 itens, etc ... até chegar a um n partições em um item (que é degenerada). O número de vezes que você dividir n ao meio para chegar a 1 é aproximadamente log n, e cada passo é O (n), dividir de modo recursivo e conquistar é O (n log n). Mergesort constrói a outra maneira, começando com n recombinações de 1 item, e terminando com uma recombinação de n itens, onde a recombinação de duas listas ordenadas é O (n).
Como para fumar crack para escrever um O (n!) Algoritmo, você é a menos que você não tem escolha. O problema caixeiro-viajante dado acima é acreditado para ser um problema tão grande.
A maioria dos livros Jon Bentley (por exemplo, Pérolas de programação ) cobrir tais coisas de uma forma muito pragmática. Este palestra dada por ele inclui uma tal análise de um quicksort.
Enquanto não totalmente relevante para a questão, Knuth veio com uma interessante ideia : ensinando Big-O notação em aulas de cálculo do ensino médio, apesar de eu achar essa idéia bastante excêntrico.
Pense nisso como empilhar blocos de Lego (n) na vertical e saltar sobre eles.
O (1) meios em cada etapa, você não faz nada. As estadias de altura do mesmo.
O (n) meios em cada passo, empilhar blocos, onde c é uma constante C1.
O (n ^ 2) meios em cada passo, é pilha C2 x n blocos, onde C2 é uma constante, e n é o número de blocos empilhados.
O (nlogn) meios em cada passo, é pilha C3 x n x log n blocos, onde C3 é uma constante, e n é o número de blocos empilhados.
Para entender O (n log n), lembre-se que log n log-base-2 meio de n. Em seguida, olhar para cada parte:
O (n) é, mais ou menos, quando você opera em cada item no conjunto.
O (log n) é quando o número de operações é o mesmo que o expoente ao qual você aumentar 2, para obter o número de itens. A busca binária, por exemplo, tem que cortar o conjunto ao 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. tipos eficientes operam frequentemente, fazendo um laço 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 ao par de comentários no meu post acima:
Domenic - Estou neste site, e eu me importo. Não por causa de pedantismo, mas porque - como programadores - normalmente se preocupam com precisão. Usando O () notação incorretamente no estilo que alguns têm feito aqui torna tipo de sentido; podemos muito bem dizer algo leva n ^ 2 unidades de tempo como O (n ^ 2) sob as convenções usadas aqui. Usando a O () não acrescenta nada. Não é apenas uma pequena discrepância entre o uso comum e precisão matemática que eu estou falando, é a diferença entre o que seja significativa e não.
Eu sei que muitos, muitos excelentes programadores que usam esses termos com precisão. Dizendo 'Oh, estamos programadores, portanto, nós não nos importamos' barateia o conjunto da empresa.
onebyone - Bem, não realmente, embora eu levo o seu ponto. Não é O (1) para n arbitrariamente grande, que é uma espécie da definição de O (). Ele só vai para mostrar que O () tem aplicabilidade limitada para n limitada, onde preferimos realmente falar sobre o número de passos dados em vez de um limite sobre esse número.
Informe o seu log de idade de oito anos (n) significa o número de vezes que você tem que cortar um comprimento n log em dois para ele para chegar até o tamanho n = 1: p
O (N log N) é geralmente de triagem O (n ^ 2) é geralmente comparando todos os pares de elementos
Suponha que você tenha um computador que poderia resolver um problema de um determinado tamanho. Agora imagine que podemos dobrar o desempenho algumas vezes. Quanto maior um problema que podemos resolver com cada duplicação?
Se podemos resolver um problema do dobro do tamanho, que é O (n).
Se temos algum multiplicador que não é um, isso é algum tipo de complexidade polinomial. Por exemplo, se cada duplicação nos permite aumentar o tamanho do problema por cerca de 40%, é O (n ^ 2), e cerca de 30% seria O (n ^ 3).
Se nós apenas adicionar ao tamanho do problema, é exponencial ou pior. Por exemplo, se cada um dos meios de duplicação podemos resolver um problema 1 maior, é O (2 ^ n). (É por isso que brute-forcing uma chave de cifra torna-se efetivamente impossível com teclas de tamanho razoável:. Uma chave de 128 bits requer cerca de 16 vezes quintilhões tanto processamento como um 64-bit)
Lembre-se da fábula da tartaruga e da lebre (tartaruga e coelho)?
No longo prazo, a tartaruga ganha, mas no curto prazo as vitórias lebre.
Isso é como O (log N) (tartaruga) vs. O (N) (lebre).
Se dois métodos diferem em sua big-O, então não há um nível de N em que um deles vai ganhar, mas big-O não diz nada sobre o quão grande que N é.
Para permanecer sincera à pergunta eu responderia a pergunta da maneira que eu iria responder uma criança de 8 anos de idade
Suponha que um vendedor de sorvete prepara uma série de sorvetes (digamos N) de diferentes formas dispostas de forma ordenada. Você quer comer o sorvete deitado no meio
Caso 1: - Você pode comer um sorvete apenas se tiver comido todo o gelo cremes menor do que Você vai ter que comer metade de todos os sorvetes preparados (entrada) .Answer depende diretamente do tamanho da entrada Solução será da ordem O (n)
Caso 2: - Você pode comer diretamente o sorvete no meio
Solução será ó (1)
Caso 3: Você pode comer um sorvete apenas se tiver comido todos os sorvetes menores do que e cada vez que você comer um sorvete você permitir que outra criança (novo toda criança) para comer todos os seus sorvetes Tempo total seria N + N + N ....... (N / 2) tempos Solução será O (N2)
log (n) significa o crescimento logarítmico. Um exemplo seria divisão e conquista. Se você tem 1000 números classificadas em uma matriz (ex. 3, 10, 34, 244, 1203 ...) e deseja procurar um número na lista (encontrar a sua posição), você poderia começar com a verificação do valor do número no índice 500. Se for menor do que o que você procura, salto a 750. Se for maior do que o que você procura, saltar para 250. Então você repetir o processo até encontrar o seu valor (e chave). Toda vez que saltar metade do espaço de busca, podemos abater longe testar muitos outros valores, pois sabemos o número 3004 não pode estar acima de número 5000 (lembre-se, é uma lista ordenada).
n log (n), em seguida, meios n * log (n).
Vou tentar escrever realmente uma explicação para um menino de verdade de oito anos, além de termos técnicos e conceitos matemáticos.
Como o que exatamente seria uma operação
O(n^2)fazer?
Se você estiver em uma festa, e há pessoas n no partido, incluindo você. Quantos apertos de mão é necessário para que todos tenham todos handshaked mais, dado que as pessoas provavelmente iria esquecer que eles handshaked em algum ponto.
Nota:. Esta aproximada a um n(n-1) rendimento simplex que é perto o suficiente para n^2
E o que diabos significa se uma operação é
O(n log(n))?
Seu time favorito ganhou, eles estão em pé na fila, e há jogadores n na equipe. Quantas hanshakes que iria levá-lo ao aperto de mão a cada jogador, uma vez que você vai HANSHAKE cada um várias vezes, quantas vezes, quantos dígitos são o número do n jogadores.
Nota:. Isso vai render n * log n to the base 10
E faz alguém tem que fumam crack para escrever um
O(x!)?
Você é um garoto rico e em seu guarda-roupa há um monte de panos, há gavetas x para cada tipo de roupa, as gavetas estão próximos uns dos outros, a primeira gaveta tem um item, cada gaveta tem tantos panos como na gaveta à sua esquerda e mais um, então você tem algo como chapéu 1, perucas 2, .. calças (x-1), camisas seguida x. Agora em quantas maneiras você pode vestir-se usando um único item de cada gaveta.
Nota: este exemplo representa quantas folhas em uma árvore de decisão, onde number of children = depth, que é feito através 1 * 2 * 3 * .. * x
