Eu preferiria a menor definição formal possível e a matemática simples.

Nota rápida, isso quase certamente está confundindo a notação Big O (que é um limite superior) com a notação Theta "Θ" (que é um limite de dois lados). Na minha experiência, isso é realmente típico de discussões em ambientes não acadêmicos. Desculpas por qualquer confusão causada.

A complexidade do Big O pode ser visualizada com este gráfico:

A definição mais simples que posso dar para a notação Big-O é esta:

A notação Big-O é uma representação relativa da complexidade de um algoritmo.

Existem algumas palavras importantes e escolhidas deliberadamente nessa frase:

• relativo: você só pode comparar maçãs com maçãs. Você não pode comparar um algoritmo para fazer multiplicação aritmética com um algoritmo que classifica uma lista de números inteiros. Mas uma comparação de dois algoritmos para realizar operações aritméticas (uma multiplicação, uma adição) lhe dirá algo significativo;
• representação: Big-O (em sua forma mais simples) reduz a comparação entre algoritmos para uma única variável. Essa variável é escolhida com base em observações ou suposições. Por exemplo, os algoritmos de classificação geralmente são comparados com base em operações de comparação (comparação de dois nós para determinar sua ordem relativa). Isso pressupõe que a comparação seja cara. Mas e se a comparação for barata, mas a troca for cara? Muda a comparação; e
• complexidade: se levar um segundo para classificar 10.000 elementos, quanto tempo levarei para classificar um milhão? A complexidade, neste caso, é uma medida relativa a outra coisa.

Volte e releia o texto acima quando ler o restante.

O melhor exemplo de Big-O em que consigo pensar é fazer aritmética. Pegue dois números (123456 e 789012). As operações aritméticas básicas que aprendemos na escola foram:

• Adição;
• subtração;
• multiplicação; e
• divisão.

Cada um deles é uma operação ou um problema. Um método para resolvê-los é chamado de algoritmo .

A adição é a mais simples. Você alinha os números (à direita) e adiciona os dígitos em uma coluna, escrevendo o último número dessa adição no resultado. A parte 'dezenas' desse número é transferida para a próxima coluna.

Vamos supor que a adição desses números seja a operação mais cara neste algoritmo. É lógico que, para somar esses dois números, temos que somar 6 dígitos (e possivelmente levar um sétimo). Se somarmos dois números de 100 dígitos, temos que fazer 100 adições. Se adicionarmos dois números de 10.000 dígitos, precisamos fazer 10.000 adições.

Veja o padrão? A complexidade (sendo o número de operações) é diretamente proporcional ao número de dígitos n no número maior. Chamamos isso de O (n) ou complexidade linear .

Subtração é semelhante (exceto que você pode precisar pedir emprestado em vez de carregar).

Multiplicação é diferente. Você alinha os números, pega o primeiro dígito no número inferior e multiplica-o por vez contra cada dígito no número superior e assim por diante. Então, para multiplicar nossos dois números de 6 dígitos, precisamos fazer 36 multiplicações. Podemos precisar adicionar até 10 ou 11 colunas para obter o resultado final também.

Se tivermos dois números de 100 dígitos, precisamos fazer 10.000 multiplicações e 200 adições. Para dois números de um milhão de dígitos, precisamos fazer um trilhão (10 ¹² ) de multiplicações e dois milhões de adições.

À medida que o algoritmo escala com n ao quadrado , isso é O (n ² ) ou complexidade quadrática . Este é um bom momento para introduzir outro conceito importante:

Nós nos preocupamos apenas com a parte mais significativa da complexidade.

O astuto pode ter percebido que poderíamos expressar o número de operações como: n ² + 2n. Mas, como você viu em nosso exemplo, com dois números de um milhão de dígitos cada, o segundo termo (2n) se torna insignificante (representando 0,0002% do total de operações nesse estágio).

Pode-se notar que assumimos o pior cenário aqui. Ao multiplicar números de 6 dígitos, se um deles tiver 4 dígitos e o outro tiver 6 dígitos, teremos apenas 24 multiplicações. Ainda assim, calculamos o pior cenário para esse 'n', ou seja, quando ambos são números de 6 dígitos. Portanto, a notação Big-O é sobre o pior cenário de um algoritmo.

A lista telefônica

O próximo melhor exemplo que posso pensar é na lista telefônica, normalmente chamada de Páginas Brancas ou similar, mas varia de país para país. Mas eu estou falando sobre o que lista as pessoas por sobrenome e, em seguida, iniciais ou primeiro nome, possivelmente endereço e depois números de telefone.

Agora, se você estivesse instruindo um computador a procurar o número de telefone de "John Smith" em uma lista telefônica que contém 1.000.000 de nomes, o que você faria? Ignorando o fato de que você poderia adivinhar o quanto os S's começaram (vamos supor que você não pode), o que você faria?

Uma implementação típica pode estar a abrir-se para o meio, pegue a 500.000 ^ª e compará-lo com "Smith". Se for "Smith, John", tivemos muita sorte. Muito mais provável é que "John Smith" esteja antes ou depois desse nome. Se for depois, dividiremos a última metade da lista telefônica ao meio e repetiremos. Se for antes, dividimos a primeira metade da lista telefônica pela metade e repetimos. E assim por diante.

Isso é chamado de pesquisa binária e é usado todos os dias na programação, independentemente de você perceber ou não.

Portanto, se você quiser encontrar um nome em uma lista telefônica de um milhão de nomes, poderá encontrar qualquer nome fazendo isso no máximo 20 vezes. Ao comparar algoritmos de busca, decidimos que essa comparação é o nosso 'n'.

• Para uma lista telefônica de 3 nomes, são necessárias 2 comparações (no máximo).
• Para 7, são necessários no máximo 3.
• Para 15 são necessários 4.
• ...
• Para 1.000.000, são necessários 20.

Isso é incrivelmente bom, não é?

Em termos de Big-O, isso é O (log n) ou complexidade logarítmica . Agora, o logaritmo em questão pode ser ln (base e), log ₁₀ , log ₂ ou alguma outra base. Não importa que ainda seja O (log n), assim como O (2n ² ) e O (100n ² ) ainda são ambos O (n ² ).

Neste ponto, vale a pena explicar que o Big O pode ser usado para determinar três casos com um algoritmo:

• Melhor caso: na pesquisa de catálogo telefônico, o melhor é encontrar o nome em uma comparação. Este é O (1) ou complexidade constante ;
• Caso esperado: Conforme discutido acima, este é O (log n); e
• Pior caso: Este também é O (log n).

Normalmente, não nos importamos com o melhor caso. Estamos interessados ​​no pior e esperado caso. Às vezes, um ou outro destes será mais importante.

Voltar para a lista telefônica.

E se você tiver um número de telefone e quiser encontrar um nome? A polícia tem uma lista telefônica reversa, mas essas pesquisas são negadas ao público em geral. Ou são eles? Tecnicamente, você pode inverter a pesquisa de um número em uma lista telefônica comum. Quão?

Você começa com o primeiro nome e compara o número. Se é uma partida, ótimo, se não, você passa para a próxima. Você precisa fazer isso dessa maneira, porque a lista telefônica não é solicitada (pelo número de telefone mesmo assim).

Portanto, para encontrar um nome com o número de telefone (pesquisa inversa):

• Melhor caso: O (1);
• Caso Esperado: O (n) (para 500.000); e
• Pior caso: O (n) (para 1.000.000).

O Vendedor Viajante

Este é um problema bastante famoso na ciência da computação e merece uma menção. Nesse problema, você tem N cidades. Cada uma dessas cidades está vinculada a uma ou mais cidades por uma estrada a uma certa distância. O problema do vendedor ambulante é encontrar o passeio mais curto que visite todas as cidades.

Parece simples? Pense de novo.

Se você tiver 3 cidades A, B e C com estradas entre todos os pares, poderá:

• A → B → C
• A → C → B
• B → C → A
• B → A → C
• C → A → B
• C → B → A

Bem, na verdade, há menos do que isso porque alguns deles são equivalentes (A → B → C e C → B → A são equivalentes, por exemplo, porque eles usam as mesmas estradas, apenas ao contrário).

Na realidade, existem 3 possibilidades.

• Leve isso para 4 cidades e você tem (IIRC) 12 possibilidades.
• Com 5 são 60.
• 6 se torna 360.

Essa é uma função de uma operação matemática chamada fatorial . Basicamente:

• 5! = 5 × 4 × 3 × 2 × 1 = 120
• 6! = 6 × 5 × 4 × 3 × 2 × 1 = 720
• 7! = 7 × 6 × 5 × 4 × 3 × 2 × 1 = 5040
• ...
• 25! = 25 × 24 ×… × 2 × 1 = 15.511.210.043.330.985.984.000.000
• ...
• 50! = 50 × 49 ×… × 2 × 1 = 3,04140932 × 10 ⁶⁴

Portanto, o problema do vendedor ambulante é O (n!) Ou complexidade fatorial ou combinatória .

Quando você chega a 200 cidades, não resta tempo suficiente no universo para resolver o problema com os computadores tradicionais.

Algo para pensar sobre.

Tempo polinomial

Outro ponto que eu queria mencionar rapidamente é que qualquer algoritmo que tenha uma complexidade de O (n ^a ) possui complexidade polinomial ou é solucionável em tempo polinomial .

O (n), O (n ² ) etc. são todos tempo polinomial. Alguns problemas não podem ser resolvidos no tempo polinomial. Certas coisas são usadas no mundo por causa disso. Criptografia de Chave Pública é um excelente exemplo. É computacionalmente difícil encontrar dois fatores principais de um número muito grande. Caso contrário, não poderíamos usar os sistemas de chave pública que usamos.

Enfim, é isso para a minha (espero inglês simples) explicação do Big O (revisado).

Ele mostra como um algoritmo é escalado com base no tamanho da entrada.

O (n ² ) : conhecido como complexidade quadrática

• 1 item: 1 segundo
• 10 itens: 100 segundos
• 100 itens: 10000 segundos

Observe que o número de itens aumenta em um fator de 10, mas o tempo aumenta em um fator de 10 ² . Basicamente, n = 10 e então O (n ² ) nos fornece o fator de escala n ² que é 10 ² .

O (n) : conhecido como complexidade linear

• 1 item: 1 segundo
• 10 itens: 10 segundos
• 100 itens: 100 segundos

Desta vez, o número de itens aumenta em um fator de 10, e o tempo também. n = 10 e, portanto, o fator de escala de O (n) é 10.

O (1) : conhecido como complexidade constante

• 1 item: 1 segundo
• 10 itens: 1 segundo
• 100 itens: 1 segundo

O número de itens ainda está aumentando em um fator de 10, mas o fator de escala de O (1) é sempre 1.

O (log n) : conhecido como complexidade logarítmica

• 1 item: 1 segundo
• 10 itens: 2 segundos
• 100 itens: 3 segundos
• 1000 itens: 4 segundos
• 10000 itens: 5 segundos

O número de cálculos é aumentado apenas por um log do valor de entrada. Portanto, neste caso, assumindo que cada cálculo leva 1 segundo, o log da entrada né o tempo necessário, portanto log n.

Essa é a essência disso. Eles reduzem a matemática para que não seja exatamente n ² ou o que eles dizem que é, mas esse será o fator dominante na escala.

A notação Big-O (também chamada de notação "crescimento assintótico") é como as funções "se parecem" quando você ignora fatores constantes e coisas próximas à origem . Nós o usamos para falar sobre como as coisas são dimensionadas .

Fundamentos

para entradas "suficientemente grandes" ...

• f(x) ∈ O(upperbound)significa f"não cresce mais rápido que"upperbound
• f(x) ∈ Ɵ(justlikethis)significa f"cresce exatamente como"justlikethis
• f(x) ∈ Ω(lowerbound)significa f"não cresce mais devagar que"lowerbound

A notação big-O não se preocupa com fatores constantes: diz-se que a função 9x²"cresce exatamente como" 10x². A notação assintótica big-O também não se importa com coisas não assintóticas ("coisas próximas à origem" ou "o que acontece quando o tamanho do problema é pequeno"): diz-se que a função 10x²"cresce exatamente como" 10x² - x + 2.

Por que você deseja ignorar as partes menores da equação? Porque eles ficam completamente diminuídos pelas grandes partes da equação quando você considera escalas cada vez maiores; sua contribuição se torna reduzida e irrelevante. (Veja a seção de exemplo.)

Dito de outra forma, é tudo sobre a proporção à medida que você vai para o infinito. Se você dividir o tempo real que leva pelo O(...), obterá um fator constante no limite de grandes entradas. Intuitivamente, isso faz sentido: as funções "escalam como" umas às outras se você puder multiplicar uma para obter a outra. É quando dizemos ...

actualAlgorithmTime(N) ∈ O(bound(N))
                                       e.g. "time to mergesort N elements 
                                             is O(N log(N))"

... isso significa que, para tamanhos de problema "grandes o suficiente" N (se ignorarmos coisas próximas à origem), existe alguma constante (por exemplo, 2,5, totalmente composta), de modo que:

actualAlgorithmTime(N)                 e.g. "mergesort_duration(N)       "
────────────────────── < constant            ───────────────────── < 2.5 
       bound(N)                                    N log(N)         

Existem muitas opções de constante; geralmente a "melhor" opção é conhecida como "fator constante" do algoritmo ... mas geralmente o ignoramos como ignoramos termos não maiores (consulte a seção Fatores constantes para saber por que eles geralmente não importam). Você também pode pensar na equação acima como um limite, dizendo " No pior cenário, o tempo necessário nunca será pior do que aproximadamente N*log(N), dentro de um fator de 2,5 (um fator constante com o qual não nos importamos muito " ) . .

Em geral, O(...)é o mais útil, porque geralmente nos preocupamos com o pior comportamento. Se f(x)representa algo "ruim" como o uso do processador ou da memória, " f(x) ∈ O(upperbound)" significa " upperboundé o pior cenário de uso do processador / memória".

Formulários

Como uma construção puramente matemática, a notação big-O não se limita a falar sobre tempo e memória de processamento. Você pode usá-lo para discutir os assintóticos de qualquer coisa em que a escala seja significativa, como:

• o número de possíveis apertos de mão entre as Npessoas em uma festa ( Ɵ(N²)especificamente N(N-1)/2, mas o que importa é que ele "cresce como" N²)
• número probabilístico esperado de pessoas que viram algum marketing viral em função do tempo
• como a latência do site é escalada com o número de unidades de processamento em uma CPU, GPU ou cluster de computador
• como a produção de calor na CPU morre em função da contagem de transistores, tensão etc.
• quanto tempo um algoritmo precisa executar, em função do tamanho da entrada
• quanto espaço um algoritmo precisa executar, em função do tamanho da entrada

Exemplo

Para o exemplo de aperto de mão acima, todos em uma sala apertam a mão de todos os outros. Nesse exemplo #handshakes ∈ Ɵ(N²),. Por quê?

Faça um backup: o número de apertos de mão é exatamente n-escolha-2 ou N*(N-1)/2(cada uma das N pessoas aperta as mãos de N-1 outras pessoas, mas esses apertos de mão de contagem dupla dividem por 2):

No entanto, para um número muito grande de pessoas, o termo linear Né diminuído e efetivamente contribui com 0 para a proporção (no gráfico: a fração de caixas vazias na diagonal sobre o total de caixas fica menor à medida que o número de participantes se torna maior). Portanto, o comportamento da escala é order N²ou o número de apertos de mão "cresce como N²".

#handshakes(N)
────────────── ≈ 1/2
     N²

É como se as caixas vazias na diagonal do gráfico (N * (N-1) / 2 marcas de verificação) não estivessem lá ( marcas ^de verificação N2 assintoticamente).

(digressão temporária do "inglês simples" :) Se você quiser provar isso para si mesmo, poderá executar uma álgebra simples na proporção para dividi-la em vários termos ( limsignifica "considerado no limite de", ignore-o se você não o vi, é apenas uma notação para "e N é realmente muito grande"):

    N²/2 - N/2         (N²)/2   N/2         1/2
lim ────────── = lim ( ────── - ─── ) = lim ─── = 1/2
N→∞     N²       N→∞     N²     N²      N→∞  1
                               ┕━━━┙
             this is 0 in the limit of N→∞:
             graph it, or plug in a really large number for N

tl; dr: O número de apertos de mão 'se parece com' x² para valores grandes, que, se escrevêssemos a razão # apertos de mão / x², o fato de não precisarmos exatamente de apertos de mão x² nem apareceria no decimal por um tempo arbitrariamente grande.

por exemplo, para x = 1 milhão, razão # apertos de mão / x²: 0,499999 ...

Intuição de construção

Isso nos permite fazer declarações como ...

"Para entradas grandes o suficiente = N, não importa qual seja o fator constante, se eu dobrar o tamanho da entrada ...

• ... Dobro o tempo que um algoritmo O (N) ("tempo linear") leva. "

  N → (2N) = 2 ( N )

• ... Eu double-quadrado (quadruple), o tempo de um O (N²) ( "tempo de quadrática") algoritmo leva." (Por exemplo, um problema 100x tão grande leva 100² = 10000x desde ... possivelmente insustentável)

  N² → (2N) ² = 4 ( N² )

• ... Cubei duas vezes (octuple) o tempo que um algoritmo O (N³) ("tempo cúbico") leva. " (Por exemplo, um problema 100x tão grande leva 100³ = 1000000x quanto tempo ... muito insustentável)

  cN³ → c (2N) ³ = 8 ( cN³ )

• ... eu adiciono uma quantia fixa ao tempo que um algoritmo O (log (N)) ("tempo logarítmico") leva. " (Barato!)

  c log (N) → c log (2N) = (c log (2)) + ( c log (N) ) = (quantidade fixa) + ( c log (N) )

• ... Não mudo o tempo que um algoritmo O (1) ("tempo constante") leva. " (O mais barato!)

  c * 1 → c * 1

• ... eu "(basicamente) duplico" o tempo que um algoritmo O (N log (N)) leva. " (Bastante comum)

  é menor que O (N ^1.000001 ), que você pode querer chamar de basicamente linear

• ... Aumentei ridiculamente o tempo que um algoritmo O (2 ^N ) ("tempo exponencial") leva. " (Você dobraria (ou triplicaria etc.) o tempo apenas aumentando o problema em uma única unidade)

  2 ^N → 2 ^2N = (4 ^N ) ............ de outra maneira ...... 2 ^N → 2 ^{N + 1} = 2 ^N 2 ¹ = 2 2 ^N

[para os inclinados matematicamente, você pode passar o mouse sobre os spoilers para obter notas secundárias menores]

(com crédito para https://stackoverflow.com/a/487292/711085 )

(tecnicamente, o fator constante pode ter alguma importância em alguns exemplos mais esotéricos, mas eu escrevi as coisas acima (por exemplo, no log (N)) para que isso não ocorra)

Essas são as ordens de crescimento que os programadores e cientistas da computação aplicada usam como pontos de referência. Eles vêem isso o tempo todo. (Portanto, embora você possa tecnicamente pensar que "dobrar a entrada torna o algoritmo O (√N) 1,414 vezes mais lento", é melhor pensar nele como "isso é pior que logarítmico, mas melhor que linear".)

Fatores constantes

Normalmente, não nos importamos com os fatores constantes específicos, porque eles não afetam a maneira como a função cresce. Por exemplo, dois algoritmos podem levar O(N)algum tempo para serem concluídos, mas um pode ser duas vezes mais lento que o outro. Normalmente, não nos importamos muito, a menos que o fator seja muito grande, pois a otimização é um negócio complicado ( quando a otimização é prematura? ); Além disso, o mero ato de escolher um algoritmo com um grande O maior geralmente melhora o desempenho em ordens de magnitude.

Alguns algoritmos assintoticamente superiores (por exemplo, um tipo sem comparação O(N log(log(N)))) podem ter um fator constante tão grande (por exemplo 100000*N log(log(N))) ou sobrecarga que é relativamente grande como O(N log(log(N)))com um oculto + 100*N, que raramente valem a pena usar mesmo em "big data".

Por que O (N) às vezes é o melhor que você pode fazer, ou seja, por que precisamos de estruturas de dados

O(N)algoritmos são, de certo modo, os "melhores" algoritmos se você precisar ler todos os seus dados. O próprio ato de ler um monte de dados é uma O(N)operação. Carregá-lo na memória é geralmente O(N)(ou mais rápido, se você tiver suporte de hardware, ou não houver tempo, se já tiver lido os dados). No entanto, se você tocar ou até olhar para todos os dados (ou mesmo para todos os outros dados), seu algoritmo levará O(N)tempo para realizar essa pesquisa. Não importa quanto tempo seu algoritmo real leve, será pelo menos O(N)porque passou esse tempo olhando todos os dados.

O mesmo pode ser dito para o próprio ato de escrever . Todos os algoritmos que imprimem N coisas levarão N tempo porque a saída é pelo menos tão longa (por exemplo, imprimir todas as permutações (maneiras de reorganizar) um conjunto de N cartas de jogo é fatorial :) O(N!).

Isso motiva o uso de estruturas de dados : uma estrutura de dados requer a leitura dos dados apenas uma vez (normalmente, O(N)tempo), além de uma quantidade arbitrária de pré-processamento (por exemplo, O(N)ou O(N log(N))ou O(N²)), que tentamos manter pequenos. Posteriormente, modificar a estrutura de dados (inserções / exclusões / etc.) e fazer consultas sobre os dados leva muito pouco tempo, como O(1)ou O(log(N)). Você prossegue para fazer um grande número de consultas! Em geral, quanto mais trabalho você estiver disposto a fazer antes do tempo, menos trabalho precisará fazer mais tarde.

Por exemplo, digamos que você tenha as coordenadas de latitude e longitude de milhões de segmentos de estrada e deseje encontrar todos os cruzamentos de ruas.

• Método ingênuo: se você tivesse as coordenadas de um cruzamento de ruas e quisesse examinar ruas próximas, teria que percorrer os milhões de segmentos a cada vez e verificar a adjacência de cada um.
• Se você precisasse fazer isso apenas uma vez, não seria um problema ter que executar o método ingênuo de O(N)trabalho apenas uma vez, mas se desejar fazê-lo várias vezes (nesse caso, Nvezes, uma vez para cada segmento), nós teria que fazer o O(N²)trabalho, ou 1000000² = 1000000000000 operações. Não é bom (um computador moderno pode executar cerca de um bilhão de operações por segundo).
• Se usarmos uma estrutura simples chamada tabela de hash (uma tabela de pesquisa de velocidade instantânea, também conhecida como mapa de hash ou dicionário), pagaremos um pequeno custo pré-processando tudo a O(N)tempo. Posteriormente, leva apenas um tempo constante, em média, para procurar algo por sua chave (nesse caso, nossa chave são as coordenadas de latitude e longitude, arredondadas em uma grade; pesquisamos os espaços de grade adjacentes dos quais existem apenas 9, que é um constante).
• Nossa tarefa passou de inviável O(N²)para gerenciável O(N), e tudo o que tivemos que fazer foi pagar um custo menor para fazer uma tabela de hash.
• analogia : a analogia nesse caso em particular é um quebra-cabeça: criamos uma estrutura de dados que explora algumas propriedades dos dados. Se nossos segmentos de estrada são como peças de quebra-cabeça, os agrupamos combinando cor e padrão. Em seguida, exploramos isso para evitar trabalhos extras mais tarde (comparando peças de quebra-cabeças de cores semelhantes entre si, e não todas as peças de quebra-cabeça).

A moral da história: uma estrutura de dados nos permite acelerar as operações. Ainda mais, estruturas de dados avançadas podem permitir combinar, atrasar ou até ignorar operações de maneiras incrivelmente inteligentes. Problemas diferentes teriam analogias diferentes, mas todos envolveriam a organização dos dados de uma maneira que explora alguma estrutura de que gostamos, ou que impusemos artificialmente a ela para a contabilidade. Trabalhamos com antecedência (basicamente planejando e organizando) e agora tarefas repetidas são muito mais fáceis!

Exemplo prático: visualizando ordens de crescimento durante a codificação

A notação assintótica é, em sua essência, bastante separada da programação. A notação assintótica é uma estrutura matemática para pensar em como as coisas são dimensionadas e podem ser usadas em muitos campos diferentes. Dito isto ... é assim que você aplica a notação assintótica à codificação.

O básico: sempre que interagimos com todos os elementos de uma coleção de tamanho A (como uma matriz, um conjunto, todas as chaves de um mapa etc.), ou executamos iterações A de um loop, isso é um fator multiplicativo do tamanho A Por que digo "um fator multiplicativo"? - porque loops e funções (quase por definição) têm tempo de execução multiplicativo: o número de iterações, os tempos de trabalho realizado no loop (ou para funções: o número de vezes que você chama o vezes, o trabalho realizado na função). (Isso ocorre se não fizermos nada sofisticado, como ignorar loops ou sair do loop cedo ou alterar o fluxo de controle na função com base em argumentos, o que é muito comum.) Aqui estão alguns exemplos de técnicas de visualização, com o pseudocódigo que o acompanha.

(aqui, xs representam unidades de trabalho em tempo constante, instruções do processador, códigos de intérprete, qualquer que seja)

for(i=0; i<A; i++)        // A * ...
    some O(1) operation     // 1

--> A*1 --> O(A) time

visualization:

|<------ A ------->|
1 2 3 4 5 x x ... x

other languages, multiplying orders of growth:
  javascript, O(A) time and space
    someListOfSizeA.map((x,i) => [x,i])               
  python, O(rows*cols) time and space
    [[r*c for c in range(cols)] for r in range(rows)]

Exemplo 2:

for every x in listOfSizeA:   // A * (...
    some O(1) operation         // 1
    some O(B) operation         // B
    for every y in listOfSizeC: // C * (...
        some O(1) operation       // 1))

--> O(A*(1 + B + C))
    O(A*(B+C))        (1 is dwarfed)

visualization:

|<------ A ------->|
1 x x x x x x ... x

2 x x x x x x ... x ^
3 x x x x x x ... x |
4 x x x x x x ... x |
5 x x x x x x ... x B  <-- A*B
x x x x x x x ... x |
................... |
x x x x x x x ... x v

x x x x x x x ... x ^
x x x x x x x ... x |
x x x x x x x ... x |
x x x x x x x ... x C  <-- A*C
x x x x x x x ... x |
................... |
x x x x x x x ... x v

Exemplo 3:

function nSquaredFunction(n) {
    total = 0
    for i in 1..n:        // N *
        for j in 1..n:      // N *
            total += i*k      // 1
    return total
}
// O(n^2)

function nCubedFunction(a) {
    for i in 1..n:                // A *
        print(nSquaredFunction(a))  // A^2
}
// O(a^3)

Se fizermos algo um pouco complicado, você ainda poderá imaginar visualmente o que está acontecendo:

for x in range(A):
    for y in range(1..x):
        simpleOperation(x*y)

x x x x x x x x x x |
x x x x x x x x x   |
x x x x x x x x     |
x x x x x x x       |
x x x x x x         |
x x x x x           |
x x x x             |
x x x               |
x x                 |
x___________________|

Aqui, o menor contorno reconhecível que você pode desenhar é o que importa; um triângulo é uma forma bidimensional (0,5 A ^ 2), assim como um quadrado é uma forma bidimensional (A ^ 2); o fator constante de dois aqui permanece na razão assintótica entre os dois, no entanto, nós o ignoramos como todos os fatores ... (Existem algumas nuances infelizes nesta técnica que não entendo aqui; isso pode enganar você.)

Claro que isso não significa que loops e funções sejam ruins; pelo contrário, eles são os blocos de construção das linguagens de programação modernas, e nós as amamos. No entanto, podemos ver que a maneira como tecemos loops, funções e condicionais, juntamente com nossos dados (fluxo de controle, etc.) imita o uso de tempo e espaço do nosso programa! Se o uso do tempo e do espaço se tornar um problema, é quando recorremos à inteligência e encontramos um algoritmo ou estrutura de dados fácil que não tínhamos considerado, para reduzir a ordem do crescimento de alguma forma. No entanto, essas técnicas de visualização (embora elas nem sempre funcionem) podem lhe dar um palpite ingênuo no pior dos casos.

Aqui está outra coisa que podemos reconhecer visualmente:

<----------------------------- N ----------------------------->
x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x
x x x x x x x x x x x x x x x x
x x x x x x x x
x x x x
x x
x

Podemos apenas reorganizar isso e ver que é O (N):

<----------------------------- N ----------------------------->
x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x
x x x x x x x x x x x x x x x x|x x x x x x x x|x x x x|x x|x

Ou talvez você faça log (N) passes dos dados, pelo tempo total de O (N * log (N)):

   <----------------------------- N ----------------------------->
 ^  x x x x x x x x x x x x x x x x|x x x x x x x x x x x x x x x x
 |  x x x x x x x x|x x x x x x x x|x x x x x x x x|x x x x x x x x
lgN x x x x|x x x x|x x x x|x x x x|x x x x|x x x x|x x x x|x x x x
 |  x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x
 v  x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x

Sem relação, mas vale a pena mencionar novamente: se executarmos um hash (por exemplo, uma pesquisa de dicionário / hashtable), esse é um fator de O (1). Isso é bem rápido.

[myDictionary.has(x) for x in listOfSizeA]
 \----- O(1) ------/    

--> A*1 --> O(A)

Se fizermos algo muito complicado, como uma função recursiva ou um algoritmo de dividir e conquistar, você poderá usar o Teorema Mestre (geralmente funciona) ou, em casos ridículos, o Teorema Akra-Bazzi (quase sempre funciona) . tempo de execução do seu algoritmo na Wikipedia.

Mas os programadores não pensam assim porque, eventualmente, a intuição do algoritmo se torna uma segunda natureza. Você começará a codificar algo ineficiente e imediatamente pensará "estou fazendo algo grosseiramente ineficiente? ". Se a resposta for "sim" E você prevê que isso realmente importa, você pode dar um passo atrás e pensar em vários truques para acelerar as coisas (a resposta é quase sempre "use uma hashtable", raramente "use uma árvore", e muito raramente algo um pouco mais complicado).

Complexidade amortizada e média

Existe também o conceito de "amortizado" e / ou "caso médio" (observe que estes são diferentes).

Caso médio : isso não passa de usar a notação big-O para o valor esperado de uma função, em vez da própria função. No caso usual em que você considera todas as entradas igualmente prováveis, o caso médio é apenas a média do tempo de execução. Por exemplo, com quicksort, mesmo que o pior caso seja O(N^2)para algumas entradas realmente ruins, o caso médio é o habitual O(N log(N))(as entradas realmente ruins são muito pequenas em número, tão poucas que não as notamos no caso médio).

Pior caso amortizado : algumas estruturas de dados podem ter uma complexidade de pior caso grande, mas garantem que, se você realizar muitas dessas operações, a quantidade média de trabalho que você realizar será melhor que a pior. Por exemplo, você pode ter uma estrutura de dados que normalmente leva O(1)tempo constante . No entanto, ocasionalmente ele 'soluça' e leva O(N)tempo para uma operação aleatória, porque talvez precise fazer alguma contabilidade ou coleta de lixo ou algo assim ... mas promete que, se soluçar, não soluçará novamente para N mais operações. O pior custo ainda é O(N)por operação, mas o custo amortizado em muitas execuções éO(N)/N =O(1)por operação. Como as grandes operações são suficientemente raras, pode-se considerar que a quantidade maciça de trabalho ocasional se confunde com o restante do trabalho como um fator constante. Dizemos que o trabalho é "amortizado" por um número suficientemente grande de chamadas e desaparece assintoticamente.

A analogia para a análise amortizada:

Você dirige um carro. Ocasionalmente, você precisa gastar 10 minutos indo para o posto de gasolina e depois gastar 1 minuto para reabastecer o tanque com gás. Se você fizesse isso toda vez que fosse a algum lugar com seu carro (passasse 10 minutos dirigindo até o posto de gasolina, passasse alguns segundos enchendo uma fração de galão), seria muito ineficiente. Mas se você encher o tanque uma vez a cada poucos dias, os 11 minutos gastos no transporte são "amortizados" por um número suficientemente grande de viagens, para que você possa ignorá-lo e fingir que todas as suas viagens foram talvez 5% mais longas.

Comparação entre o caso médio e o pior caso amortizado:

• Caso médio: fazemos algumas suposições sobre nossos insumos; ou seja, se nossas entradas tiverem probabilidades diferentes, nossos produtos / tempos de execução terão probabilidades diferentes (das quais calculamos a média). Normalmente, assumimos que todas as nossas entradas são igualmente prováveis ​​(probabilidade uniforme), mas se as entradas do mundo real não se ajustarem às nossas suposições de "entrada média", os cálculos médios de saída / tempo de execução podem não ter sentido. Se você antecipar entradas uniformemente aleatórias, é útil pensar nisso!
• Pior caso amortizado: se você usar uma estrutura de dados do pior caso amortizado, o desempenho será garantido dentro do pior caso amortizado ... eventualmente (mesmo se as entradas forem escolhidas por um demônio do mal que sabe tudo e está tentando Dane-se você). Geralmente, usamos isso para analisar algoritmos que podem ter um desempenho muito "instável" com grandes soluços inesperados, mas com o tempo se saem tão bem quanto outros algoritmos. (No entanto, a menos que sua estrutura de dados tenha limites superiores para muitos trabalhos extraordinários em que está disposta a procrastinar, talvez um invasor malvado possa forçar você a acompanhar a quantidade máxima de trabalho procrastinado de uma só vez.

No entanto, se você estiver razoavelmente preocupado com um invasor, há muitos outros vetores de ataque algorítmico com os quais se preocupar além da amortização e do caso médio.)

Caso médio e amortização são ferramentas incrivelmente úteis para pensar e projetar com o dimensionamento em mente.

(Consulte Diferença entre caso médio e análise amortizada, se estiver interessado neste subtópico.)

Big-O multidimensional

Na maioria das vezes, as pessoas não percebem que há mais de uma variável no trabalho. Por exemplo, em um algoritmo de pesquisa de cadeia, seu algoritmo pode levar tempo O([length of text] + [length of query]), ou seja, é linear em duas variáveis ​​como O(N+M). Outros algoritmos mais ingênuos podem ser O([length of text]*[length of query])ou O(N*M). Ignorar várias variáveis ​​é um dos descuidos mais comuns que vejo na análise de algoritmos e pode prejudicá-lo ao projetar um algoritmo.

A história toda

Lembre-se de que big-O não é a história toda. Você pode acelerar drasticamente alguns algoritmos usando o armazenamento em cache, tornando-os alheios ao cache, evitando gargalos trabalhando com RAM em vez de disco, usando paralelismo ou fazendo trabalho com antecedência - essas técnicas geralmente são independentes da ordem de crescimento notação "big-O", embora você frequentemente veja o número de núcleos na notação big-O de algoritmos paralelos.

Lembre-se também de que, devido a restrições ocultas do seu programa, talvez você não se importe com o comportamento assintótico. Você pode estar trabalhando com um número limitado de valores, por exemplo:

• Se você estiver classificando algo como 5 elementos, não deseja usar o O(N log(N))quicksort rápido ; você deseja usar a classificação por inserção, que tem bom desempenho em pequenas entradas. Essas situações geralmente aparecem em algoritmos de dividir e conquistar, onde você divide o problema em subproblemas cada vez menores, como classificação recursiva, transformações rápidas de Fourier ou multiplicação de matrizes.
• Se alguns valores são efetivamente delimitados devido a algum fato oculto (por exemplo, o nome humano médio é delimitado suavemente com talvez 40 letras, e a idade humana é delimitada suavemente em torno de 150). Você também pode impor limites à sua entrada para efetivamente tornar os termos constantes.

Na prática, mesmo entre algoritmos com desempenho assintótico igual ou semelhante, seu mérito relativo pode realmente ser impulsionado por outras coisas, como: outros fatores de desempenho (quicksort e mergesort são ambos O(N log(N)), mas o quicksort tira proveito dos caches da CPU); considerações de não desempenho, como facilidade de implementação; se uma biblioteca está disponível e quão respeitável e mantida é a biblioteca.

Os programas também serão executados mais lentamente em um computador de 500 MHz vs 2 GHz. Realmente não consideramos isso como parte dos limites dos recursos, porque pensamos na escala em termos de recursos da máquina (por exemplo, por ciclo de clock), não por segundo real. No entanto, existem coisas semelhantes que podem "secretamente" afetar o desempenho, como se você estiver executando em emulação ou se o compilador otimizou ou não o código. Isso pode fazer com que algumas operações básicas demorem mais tempo (mesmo em relação uma à outra) ou até acelerar ou desacelerar algumas operações assintoticamente (mesmo em relação uma à outra). O efeito pode ser pequeno ou grande entre diferentes implementações e / ou ambientes. Você muda idiomas ou máquinas para obter esse pequeno trabalho extra? Isso depende de centenas de outras razões (necessidade, habilidades, colegas de trabalho, produtividade do programador,

As questões acima, como o efeito da escolha de qual linguagem de programação é usada, quase nunca são consideradas como parte do fator constante (nem deveriam ser); no entanto, é preciso estar ciente deles, porque às vezes (embora raramente) eles podem afetar as coisas. Por exemplo, em cpython, a implementação da fila de prioridade nativa é assintoticamente não ideal (em O(log(N))vez de O(1)escolher sua inserção ou localização min); você usa outra implementação? Provavelmente não, pois a implementação C é provavelmente mais rápida e provavelmente existem outros problemas semelhantes em outros lugares. Existem trocas; às vezes eles importam e às vezes não.

( editar : A explicação "inglês simples" termina aqui.)

Adendos de matemática

Para completude, a definição precisa da notação big-O é a seguinte: f(x) ∈ O(g(x))significa que "f é assintoticamente limitado por const * g": ignorando tudo abaixo de algum valor finito de x, existe uma constante tal que |f(x)| ≤ const * |g(x)|. (Os outros símbolos são os seguintes: assim como Osignifica ≤, Ωsignifica ≥. Existem variantes em minúsculas: osignifica <e ωsignifica>.) f(x) ∈ Ɵ(g(x))Significa ambos f(x) ∈ O(g(x))e f(x) ∈ Ω(g(x))(superior e inferior com g): existem algumas constantes como f sempre estará na "banda" entre const1*g(x)e const2*g(x). É a afirmação assintótica mais forte que você pode fazer e aproximadamente equivalente a== . (Desculpe, decidi adiar a menção dos símbolos de valor absoluto até agora, por uma questão de clareza; especialmente porque nunca vi valores negativos surgirem no contexto da ciência da computação.)

As pessoas costumam usar = O(...), que é talvez a notação 'comp-sci' mais correta e totalmente legítima de usar; "f = O (...)" é lido "f é ordem ... / f é xxx limitado por ..." e é considerado "f é uma expressão cujos assintóticos são ...". Fui ensinado a usar o mais rigoroso ∈ O(...). ∈significa "é um elemento de" (ainda lido como antes). Neste caso particular, O(N²)contém elementos como { 2 N², 3 N², 1/2 N², 2 N² + log(N), - N² + N^1.9, ...} e é infinitamente grande, mas ainda é um conjunto.

O e Ω não são simétricos (n = O (n²), mas n² não é O (n)), mas Ɵ são simétricos e (como essas relações são todas transitivas e reflexivas) Ɵ, portanto, são simétricas, transitivas e reflexivas e, portanto, particiona o conjunto de todas as funções em classes de equivalência . Uma classe de equivalência é um conjunto de coisas que consideramos iguais. Ou seja, dada qualquer função em que você possa pensar, você pode encontrar um 'representante assintótico' canônico / único da classe (geralmente aceitando o limite ... eu acho ); Assim como você pode agrupar todos os números inteiros em probabilidades ou pares, você pode agrupar todas as funções com Ɵ em x-ish, log (x) ^ 2-ish, etc ... basicamente ignorando termos menores (mas às vezes você pode ficar preso a funções mais complicadas que são classes separadas para si mesmas).

A =notação pode ser a mais comum e até é usada em artigos de cientistas da computação de renome mundial. Além disso, geralmente ocorre que, em um ambiente casual, as pessoas dizem O(...)quando querem dizer Ɵ(...); isso é tecnicamente verdade, já que o conjunto de coisas Ɵ(exactlyThis)é um subconjunto de O(noGreaterThanThis)... e é mais fácil digitar. ;-)

EDIT: Nota rápida, isso certamente confunde a notação Big O (que é um limite superior) com a notação Theta (que é um limite superior e inferior). Na minha experiência, isso é realmente típico de discussões em ambientes não acadêmicos. Desculpas por qualquer confusão causada.

Em uma frase: À medida que o tamanho do seu trabalho aumenta, quanto tempo leva para ser concluído?

Obviamente, isso é apenas usar "tamanho" como entrada e "tempo gasto" como saída - a mesma idéia se aplica se você quiser falar sobre uso de memória, etc.

Aqui está um exemplo em que temos N camisetas que queremos secar. Vamos assumir que é incrivelmente rápido colocá-los na posição de secagem (ou seja, a interação humana é insignificante). Esse não é o caso na vida real, é claro ...

• Usando uma linha de lavagem do lado de fora: supondo que você tenha um quintal infinitamente grande, a lavagem seca no tempo O (1). Por mais que você tenha, ele terá o mesmo sol e ar fresco, portanto o tamanho não afeta o tempo de secagem.

• Usando uma máquina de secar roupa: você coloca 10 camisas em cada carga, e elas são feitas uma hora depois. (Ignore os números reais aqui - eles são irrelevantes.) Portanto, secar 50 camisas leva cerca de 5 vezes mais do que secar 10 camisas.

• Colocando tudo em um armário de ventilação: se colocarmos tudo em uma pilha grande e deixar o calor geral fazê-lo, levará muito tempo para as camisas do meio ficarem secas. Eu não gostaria de adivinhar os detalhes, mas suspeito que seja pelo menos O (N ^ 2) - à medida que você aumenta a carga de lavagem, o tempo de secagem aumenta mais rapidamente.

Um aspecto importante da notação "grande O" é que ele não diz qual algoritmo será mais rápido para um determinado tamanho. Pegue uma hashtable (chave de string, valor inteiro) vs uma matriz de pares (string, inteiro). É mais rápido encontrar uma chave na hashtable ou um elemento na matriz, com base em uma string? (ou seja, para a matriz, "encontre o primeiro elemento em que a parte da string corresponde à chave especificada.") As tabelas de hash geralmente são amortizadas (~ = "em média") O (1) - uma vez configuradas, deve demorar cerca de ao mesmo tempo para localizar uma entrada em uma tabela de 100 entradas e em uma tabela de 1.000.000 de entradas. Encontrar um elemento em uma matriz (com base no conteúdo e não no índice) é linear, ou seja, O (N) - em média, você terá que examinar metade das entradas.

Isso torna uma hashtable mais rápida que uma matriz para pesquisas? Não necessariamente. Se você tiver uma coleção muito pequena de entradas, uma matriz poderá ser mais rápida - poderá verificar todas as seqüências de caracteres no tempo necessário para calcular apenas o código de hash da que você está visualizando. À medida que o conjunto de dados aumenta, no entanto, a hashtable acaba vencendo a matriz.

Big O descreve um limite superior no comportamento de crescimento de uma função, por exemplo, o tempo de execução de um programa, quando as entradas se tornam grandes.

Exemplos:

• O (n): Se eu dobrar o tamanho da entrada, o tempo de execução dobrará

• O (n ² ): se o tamanho da entrada dobrar, o tempo de execução quadruplica

• O (log n): se o tamanho da entrada dobrar, o tempo de execução aumentará em um

• O (2 ⁿ ): Se o tamanho da entrada aumentar em um, o tempo de execução duplicará

O tamanho da entrada geralmente é o espaço em bits necessário para representar a entrada.

A notação Big O é mais comumente usada pelos programadores como uma medida aproximada de quanto tempo um cálculo (algoritmo) levará para ser concluído, expresso em função do tamanho do conjunto de entradas.

Big O é útil para comparar quão bem dois algoritmos serão dimensionados à medida que o número de entradas for aumentado.

Mais precisamente, a notação Big O é usada para expressar o comportamento assintótico de uma função. Isso significa como a função se comporta à medida que se aproxima do infinito.

Em muitos casos, o "O" de um algoritmo se enquadra em um dos seguintes casos:

• O (1) - O tempo para concluir é o mesmo, independentemente do tamanho do conjunto de entradas. Um exemplo é acessar um elemento da matriz por índice.
• O (Log N) - O tempo para concluir aumenta aproximadamente de acordo com o log2 (n). Por exemplo, 1024 itens levam aproximadamente duas vezes mais que 32 itens, porque Log2 (1024) = 10 e Log2 (32) = 5. Um exemplo é encontrar um item em uma árvore de pesquisa binária (BST).
• O (N) - tempo para concluir a escala linear com o tamanho do conjunto de entrada. Em outras palavras, se você dobrar o número de itens no conjunto de entradas, o algoritmo leva aproximadamente o dobro do tempo. Um exemplo é contar o número de itens em uma lista vinculada.
• O (N Log N) - O tempo para concluir aumenta o número de itens vezes o resultado do Log2 (N). Um exemplo disso é a classificação de heap e a classificação rápida .
• O (N ^ 2) - O tempo para concluir é aproximadamente igual ao quadrado do número de itens. Um exemplo disso é a classificação por bolhas .
• O (N!) - O tempo para concluir é o fatorial do conjunto de entradas. Um exemplo disso é a solução de força bruta do problema do vendedor ambulante .

Big O ignora fatores que não contribuem de maneira significativa para a curva de crescimento de uma função, à medida que o tamanho da entrada aumenta em direção ao infinito. Isso significa que as constantes adicionadas ou multiplicadas pela função são simplesmente ignoradas.

Big O é apenas uma maneira de se "expressar" de uma maneira comum: "Quanto tempo / espaço é necessário para executar meu código?".

Muitas vezes você pode ver O (n), O (n ² ), O (nlogn) e assim por diante, todos estes são apenas maneiras de mostrar; Como um algoritmo muda?

O (n) significa Big O é n, e agora você pode pensar: "O que é n !?" Bem "n" é a quantidade de elementos. Imagem que você deseja procurar por um item em uma matriz. Você precisaria procurar em Cada elemento e como "Você é o elemento / item correto?" na pior das hipóteses, o item está no último índice, o que significa que demorou tanto tempo quanto há itens na lista; portanto, para ser genérico, dizemos "oh, ei, n é uma quantidade razoável de valores!" .

Então, você pode entender o que "n ² " significa, mas para ser ainda mais específico, brinque com o pensamento de que você tem um algoritmo simples e o mais simples de classificação; Tipo de bolha. Esse algoritmo precisa examinar a lista inteira, para cada item.

Minha lista

1. 1
2. 6
3. 3

O fluxo aqui seria:

• Compare 1 e 6, qual é o maior? Ok 6 está na posição correta, avançando!
• Compare 6 e 3, oh, 3 é menos! Vamos mudar isso, Ok, a lista mudou, precisamos começar do início agora!

Este é O n ² porque, é necessário olhar para todos os itens da lista onde há "n" itens. Para cada item, você olha todos os itens mais uma vez; para comparar, também é "n"; portanto, para cada item, você olha "n" vezes significando n * n = n ²

Espero que isso seja tão simples quanto você quiser.

Mas lembre-se, o Big O é apenas uma maneira de se expandir na maneira de tempo e espaço.

Big O descreve a natureza de escala fundamental de um algoritmo.

Há muitas informações que o Big O não informa sobre um determinado algoritmo. Ele é direto ao ponto e fornece apenas informações sobre a natureza de escala de um algoritmo, especificamente como o uso de recursos (tempo de reflexão ou memória) de um algoritmo é escalado em resposta ao "tamanho da entrada".

Considere a diferença entre um motor a vapor e um foguete. Não são apenas variedades diferentes da mesma coisa (como, por exemplo, um motor Prius vs. um motor Lamborghini), mas são tipos dramaticamente diferentes de sistemas de propulsão, em sua essência. Um motor a vapor pode ser mais rápido que um foguete de brinquedo, mas nenhum motor a pistão será capaz de atingir as velocidades de um veículo de lançamento orbital. Isso ocorre porque esses sistemas têm características de escala diferentes em relação à relação de combustível necessária ("uso de recursos") para atingir uma determinada velocidade ("tamanho de entrada").

Por que isso é tão importante? Porque o software lida com problemas que podem diferir em tamanho por fatores de até um trilhão. Considere isso por um momento. A proporção entre a velocidade necessária para viajar até a Lua e a velocidade de caminhada humana é inferior a 10.000: 1, e é absolutamente pequena se comparada à faixa de tamanhos de entrada que o software pode enfrentar. E como o software pode enfrentar uma faixa astronômica em tamanhos de entrada, existe o potencial para a complexidade do Big O de um algoritmo, é uma natureza de dimensionamento fundamental, para superar os detalhes de implementação.

Considere o exemplo de classificação canônica. A classificação por bolha é O (n ² ) enquanto a classificação por mesclagem é O (n log n). Digamos que você tenha dois aplicativos de classificação, o aplicativo A, que usa classificação de bolha, e o aplicativo B, que usa classificação de mesclagem, e digamos que para tamanhos de entrada de cerca de 30 elementos, o aplicativo A é 1.000x mais rápido que o aplicativo B na classificação. Se você nunca precisar classificar muito mais do que 30 elementos, é óbvio que deve preferir o aplicativo A, pois é muito mais rápido nesses tamanhos de entrada. No entanto, se você achar que pode classificar dez milhões de itens, o que você esperaria é que o aplicativo B realmente seja milhares de vezes mais rápido que o aplicativo A nesse caso, devido inteiramente à maneira como cada algoritmo é escalonado.

Aqui está o bestiário inglês comum que costumo usar ao explicar as variedades comuns de Big-O

Em todos os casos, prefira algoritmos mais altos na lista àqueles mais baixos da lista. No entanto, o custo da mudança para uma classe de complexidade mais cara varia significativamente.

O (1):

Nenhum crescimento. Independentemente do tamanho do problema, você pode resolvê-lo na mesma quantidade de tempo. Isso é um pouco análogo à transmissão, onde é necessária a mesma quantidade de energia para transmitir a uma determinada distância, independentemente do número de pessoas que estão dentro do alcance da transmissão.

O (log n ):

Essa complexidade é igual a O (1), exceto que é apenas um pouco pior. Para todos os fins práticos, você pode considerar isso como uma escala constante muito grande. A diferença no trabalho entre processar mil e 1 bilhão de itens é apenas um fator seis.

O ( n ):

O custo da solução do problema é proporcional ao tamanho do problema. Se o seu problema dobrar de tamanho, o custo da solução dobrará. Como a maioria dos problemas precisa ser digitalizada no computador de alguma forma, como entrada de dados, leitura de disco ou tráfego de rede, esse geralmente é um fator de escala acessível.

O ( n log n ):

Essa complexidade é muito semelhante a O ( n ) . Para todos os fins práticos, os dois são equivalentes. Esse nível de complexidade geralmente ainda seria considerado escalável. Ajustando suposições, alguns algoritmos O ( n log n ) podem ser transformados em algoritmos O ( n ) . Por exemplo, limitar o tamanho das chaves reduz a classificação de O ( n log n ) para O ( n ) .

O ( n ² ):

Cresce como um quadrado, onde n é o comprimento do lado de um quadrado. Essa é a mesma taxa de crescimento que o "efeito de rede", onde todos em uma rede podem conhecer todos os demais na rede. O crescimento é caro. A maioria das soluções escalonáveis ​​não pode usar algoritmos com esse nível de complexidade sem fazer ginástica significativa. Isso geralmente se aplica a todas as outras complexidades polinomiais - O ( n ^k ) - também.

O (2 ⁿ ):

Não escala. Você não tem esperança de resolver nenhum problema de tamanho não trivial. Útil para saber o que evitar e para os especialistas encontrarem algoritmos aproximados que estão em O ( n ^k ) .

Big O é uma medida de quanto tempo / espaço um algoritmo usa em relação ao tamanho de sua entrada.

Se um algoritmo for O (n), o tempo / espaço aumentará na mesma taxa que sua entrada.

Se um algoritmo é O (n ² ), o tempo / espaço aumenta na taxa de sua entrada ao quadrado.

e assim por diante.

O que é uma explicação simples em inglês do Big O? Com o mínimo de definição formal possível e matemática simples.

Uma explicação clara em inglês da necessidade de notação Big-O:

Quando programamos, estamos tentando resolver um problema. O que codificamos é chamado de algoritmo. A notação Big O permite comparar o pior desempenho de nossos algoritmos de maneira padronizada. As especificações de hardware variam com o tempo e as melhorias no hardware podem reduzir o tempo necessário para a execução de um algoritmo. Mas substituir o hardware não significa que nosso algoritmo seja melhor ou aprimorado ao longo do tempo, pois nosso algoritmo ainda é o mesmo. Portanto, para nos permitir comparar algoritmos diferentes, para determinar se um é melhor ou não, usamos a notação Big O.

Uma explicação em inglês simples do que é a notação O grande:

Nem todos os algoritmos são executados na mesma quantidade de tempo e podem variar com base no número de itens na entrada, que chamaremos de n . Com base nisso, consideramos a análise de pior caso, ou um limite superior do tempo de execução, à medida que n se torna cada vez maior. Devemos estar cientes do que n é, porque muitas das grandes notações O fazem referência a ele.

É muito difícil medir a velocidade dos programas de software e, quando tentamos, as respostas podem ser muito complexas e cheias de exceções e casos especiais. Esse é um grande problema, porque todas essas exceções e casos especiais são perturbadores e inúteis quando queremos comparar dois programas diferentes entre si para descobrir qual é o "mais rápido".

Como resultado de toda essa complexidade inútil, as pessoas tentam descrever a velocidade dos programas de software usando as expressões menores e menos complexas (matemáticas) possíveis. Essas expressões são aproximações muito grosseiras: embora, com um pouco de sorte, elas capturem a "essência" de se um software é rápido ou lento.

Por serem aproximações, usamos a letra "O" (Big Oh) na expressão, como uma convenção para sinalizar ao leitor que estamos fazendo uma simplificação grosseira. (E para garantir que ninguém pense erroneamente que a expressão é de alguma forma precisa).

Se você ler "Oh" como significando "na ordem de" ou "aproximadamente", você não errará muito. (Eu acho que a escolha do Big-Oh pode ter sido uma tentativa de humor).

A única coisa que essas expressões "Big-Oh" tentam fazer é descrever o quanto o software fica mais lento à medida que aumentamos a quantidade de dados que o software precisa processar. Se dobrarmos a quantidade de dados que precisam ser processados, o software precisa duas vezes mais para concluir o trabalho? Dez vezes mais? Na prática, há um número muito limitado de grandes expressões Oh com as quais você encontrará e precisa se preocupar:

O bom:

• O(1) Constante : O programa leva o mesmo tempo para ser executado, independentemente do tamanho da entrada.
• O(log n) Logarítmica : o tempo de execução do programa aumenta apenas lentamente, mesmo com grandes aumentos no tamanho da entrada.

O mal:

• O(n) Linear : o tempo de execução do programa aumenta proporcionalmente ao tamanho da entrada.
• O(n^k) Polinômio : - O tempo de processamento cresce cada vez mais rápido - como uma função polinomial - à medida que o tamanho da entrada aumenta.

... e o feio:

• O(k^n) Exponencial O tempo de execução do programa aumenta muito rapidamente, mesmo com aumentos moderados no tamanho do problema - é prático processar pequenos conjuntos de dados com algoritmos exponenciais.
• O(n!) Fatorial O tempo de execução do programa será mais longo do que você pode esperar, exceto pelos conjuntos de dados mais pequenos e mais triviais.

Uma resposta simples e direta pode ser:

Big O representa o pior tempo / espaço possível para esse algoritmo. O algoritmo nunca ocupará mais espaço / tempo acima desse limite. Big O representa a complexidade do tempo / espaço no caso extremo.

Ok, meus 2 centavos.

Big-O, é a taxa de aumento de recursos consumidos pelo programa, wrt problem-instance-size

Recurso: pode ser o tempo total da CPU, o espaço máximo de RAM. Por padrão, refere-se ao tempo da CPU.

Digamos que o problema seja "Encontre a soma",

int Sum(int*arr,int size){
      int sum=0;
      while(size-->0) 
         sum+=arr[size]; 

      return sum;
}

instância do problema = {5,10,15} ==> tamanho da instância do problema = 3, iterações em loop = 3

instância do problema = {5,10,15,20,25} ==> tamanho da instância do problema = 5 iterações em loop = 5

Para entrada do tamanho "n", o programa está crescendo na velocidade de "n" iterações na matriz. Portanto, Big-O é N expresso como O (n)

Digamos que o problema seja "Encontre a combinação",

    void Combination(int*arr,int size)
    { int outer=size,inner=size;
      while(outer -->0) {
        inner=size;
        while(inner -->0)
          cout<<arr[outer]<<"-"<<arr[inner]<<endl;
      }
    }

instância do problema = {5,10,15} ==> tamanho da instância do problema = 3, iterações totais = 3 * 3 = 9

instância do problema = {5,10,15,20,25} ==> tamanho da instância do problema = 5, iterações totais = 5 * 5 = 25

Para entrada do tamanho "n", o programa está crescendo na velocidade de iterações "n * n" na matriz. Portanto, Big-O é N ² expresso como O (n ² )

A notação Big O é uma maneira de descrever o limite superior de um algoritmo em termos de espaço ou tempo de execução. O n é o número de elementos no problema (ou seja, tamanho de uma matriz, número de nós em uma árvore etc.). Estamos interessados ​​em descrever o tempo de execução à medida que n aumenta.

Quando dizemos que algum algoritmo é O (f (n)), estamos dizendo que o tempo de execução (ou espaço necessário) por esse algoritmo é sempre menor do que alguns tempos constantes f (n).

Dizer que a pesquisa binária tem um tempo de execução de O (logn) é dizer que existe alguma constante c que você pode multiplicar o log (n) por que sempre será maior que o tempo de execução da pesquisa binária. Nesse caso, você sempre terá algum fator constante nas comparações de log (n).

Em outras palavras, onde g (n) é o tempo de execução do seu algoritmo, dizemos que g (n) = O (f (n)) quando g (n) <= c * f (n) quando n> k, em que c e k são algumas constantes.

" O que é uma explicação clara do Big O em inglês? Com ​​a menor definição formal possível e a matemática simples. "

Uma pergunta tão lindamente simples e curta parece pelo menos merecer uma resposta igualmente curta, como um aluno pode receber durante as aulas.

A notação Big O simplesmente diz quanto tempo * um algoritmo pode executar dentro, em termos de apenas a quantidade de dados de entrada **.

(* em um maravilhoso senso de tempo sem unidade !)
(** o que importa, porque as pessoas sempre querem mais , se vivem hoje ou amanhã)

Bem, o que há de tão maravilhoso na notação Big O, se é isso que ela faz?

• Na prática, a análise do Big O é muito útil e importante porque o Big O coloca o foco diretamente no algoritmo do própria complexidade e completamente ignora qualquer coisa que é meramente uma constante de proporcionalidade-como um motor de JavaScript, a velocidade de uma CPU, sua conexão com a Internet, e todas essas coisas que se tornam rapidamente tornar-se tão ridiculamente desatualizado como um Modelo T . O Big O concentra-se no desempenho apenas da maneira que importa tanto para as pessoas que vivem no presente ou no futuro.

• A notação Big O também destaca os princípios mais importantes da programação / engenharia de computadores, fato que inspira todos os bons programadores a continuar pensando e sonhando: a única maneira de obter resultados além da marcha lenta da tecnologia é inventar uma melhor algoritmo .

Exemplo de algoritmo (Java):

// Given a list of integers L, and an integer K
public boolean simple_search(List<Integer> L, Integer K)
{
    // for each integer i in list L
    for (Integer i : L)
    {
        // if i is equal to K
        if (i == K)
        {
            return true;
        }
    }

    return false;
}

Descrição do algoritmo:

• Esse algoritmo pesquisa uma lista, item por item, procurando por uma chave,

• Iterando cada item da lista, se for a chave, retorne True,

• Se o loop terminar sem encontrar a chave, retorne False.

A notação Big-O representa o limite superior da Complexidade (Tempo, Espaço, ..)

Para encontrar The Big-O on Complexity do tempo:

• Calcule quanto tempo (em relação ao tamanho da entrada) leva o pior caso:

• Pior caso: a chave não existe na lista.

• Tempo (pior caso) = 4n + 1

• Tempo: O (4n + 1) = O (n) | no Big-O, as constantes são negligenciadas

• O (n) ~ Linear

Há também o Big-Omega, que representa a complexidade do Best-Case:

• Melhor caso: a chave é o primeiro item.

• Tempo (melhor caso) = 4

• Tempo: Ω (4) = O (1) ~ Instantâneo \ Constante

Big O

f (x) = O ( g (x)) quando x vai para a (por exemplo, a = + ∞) significa que existe uma função k tal que:

1. f (x) = k (x) g (x)

2. k é delimitado em alguma vizinhança de a (se a = + ∞, isso significa que existem números N e M de tal forma que para cada x> N, | k (x) | <M).

Em outras palavras, em inglês simples: f (x) = O ( g (x)), x → a, significa que em uma vizinhança de a, f se decompõe no produto de g e em alguma função limitada.

O pequeno

A propósito, aqui está para comparação a definição de pequeno o.

f (x) = o ( g (x)) quando x passa para a significa que existe uma função k tal que:

1. f (x) = k (x) g (x)

2. k (x) vai para 0 quando x vai para a.

Exemplos

• sin x = O (x) quando x → 0.

• sen x = O (1) quando x → + ∞,

• x ² + x = O (x) quando x → 0,

• x ² + x = O (x ² ) quando x → + ∞,

• ln (x) = o (x) = O (x) quando x → + ∞.

Atenção!A notação com o sinal de igual "=" usa uma "igualdade falsa": é verdade que o (g (x)) = O (g (x)), mas falso que O (g (x)) = o (g (x)) Da mesma forma, não há problema em escrever "ln (x) = o (x) quando x → + ∞", mas a fórmula "o (x) = ln (x)" não faria sentido.

Mais exemplos

• O (1) = O (n) = O (n ² ) quando n → + ∞ (mas não o contrário, a igualdade é "falsa"),

• O (n) + O (n ² ) = O (n ² ) quando n → + ∞

• O (O (n ² )) = O (n ² ) quando n → + ∞

• O (n ² ) O (n ³ ) = O (n ⁵ ) quando n → + ∞

Aqui está o artigo da Wikipedia: https://en.wikipedia.org/wiki/Big_O_notation

A notação Big O é uma maneira de descrever a rapidez com que um algoritmo será executado, dado um número arbitrário de parâmetros de entrada, que chamaremos de "n". É útil na ciência da computação porque máquinas diferentes operam em velocidades diferentes e simplesmente dizer que um algoritmo leva 5 segundos não diz muito, porque enquanto você pode estar executando um sistema com um processador octo-core de 4,5 Ghz, eu posso estar executando um sistema de 800 Mhz de 15 anos, que pode demorar mais, independentemente do algoritmo. Então, em vez de especificar a rapidez com que um algoritmo é executado em termos de tempo, dizemos com que rapidez ele é executado em termos de número de parâmetros de entrada, ou "n". Ao descrever os algoritmos dessa maneira, podemos comparar as velocidades dos algoritmos sem ter que levar em consideração a velocidade do próprio computador.

Não tenho certeza de que estou contribuindo ainda mais com o assunto, mas ainda pensei em compartilhar: Certa vez, achei neste post do blog algumas explicações e exemplos bastante úteis (embora muito básicos) sobre o Big O:

Por meio de exemplos, isso ajudou a introduzir o básico básico no meu crânio em forma de concha de tartaruga, então eu acho que é uma leitura bastante decente de 10 minutos para levá-lo na direção certa.

Você quer saber tudo o que há para saber sobre o grande O? Eu também.

Então, para falar do grande O, usarei palavras que tenham apenas uma batida nelas. Um som por palavra. Palavras pequenas são rápidas. Você conhece essas palavras, e eu também. Usaremos as palavras com um som. Eles são pequenos. Tenho certeza que você saberá todas as palavras que usaremos!

Agora, vamos você e eu conversar sobre trabalho. Na maioria das vezes, eu não gosto de trabalho. Você gosta de trabalhar? Pode ser o caso, mas tenho certeza de que não.

Eu não gosto de ir trabalhar. Eu não gosto de gastar tempo no trabalho. Se eu tivesse do meu jeito, gostaria apenas de brincar e fazer coisas divertidas. Você sente o mesmo que eu?

Agora, às vezes, tenho que ir trabalhar. É triste mas verdade. Então, quando estou no trabalho, tenho uma regra: tento fazer menos trabalho. Tão perto de nenhum trabalho quanto eu puder. Então eu vou jogar!

Então, aqui está a grande notícia: o grande O pode me ajudar a não trabalhar! Eu posso jogar mais tempo, se eu souber grande O. Menos trabalho, mais diversão! É isso que O grande me ajuda a fazer.

Agora eu tenho algum trabalho. Eu tenho esta lista: um, dois, três, quatro, cinco, seis. Eu devo adicionar todas as coisas nesta lista.

Uau, eu odeio trabalho. Mas tudo bem, eu tenho que fazer isso. Então aqui vou eu.

Um mais dois é três ... mais três são seis ... e quatro é ... eu não sei. Eu me perdi. É muito difícil para mim fazer na minha cabeça. Eu não ligo muito para esse tipo de trabalho.

Então não vamos fazer o trabalho. Vamos você e eu pensarmos o quão difícil é. Quanto trabalho eu teria que fazer para adicionar seis números?

Bem vamos ver. Devo adicionar um e dois e depois adicionar a três e depois adicionar a quatro ... No total, conto seis adições. Eu tenho que fazer seis adições para resolver isso.

Aí vem o grande O, para nos dizer o quão difícil é essa matemática.

Big O diz: precisamos fazer seis adições para resolver isso. Um complemento, para cada coisa de um a seis. Seis pequenos pedaços de trabalho ... cada pedaço de trabalho é um complemento.

Bem, não farei o trabalho para adicioná-los agora. Mas eu sei o quão difícil seria. Seriam seis adições.

Oh não, agora eu tenho mais trabalho. Sheesh. Quem faz esse tipo de coisa ?!

Agora eles me pedem para adicionar de um a dez! Porque eu faria isso? Eu não queria adicionar um a seis. Acrescentar de um a dez ... bem ... isso seria ainda mais difícil!

Quanto mais difícil seria? Quanto mais trabalho eu teria que fazer? Preciso de mais ou menos etapas?

Bem, acho que teria que fazer dez adições ... uma para cada coisa, de uma a dez. Dez é mais que seis. Eu teria que trabalhar muito mais para adicionar de um a dez, do que um a seis!

Eu não quero adicionar agora. Eu só quero pensar em quão difícil pode ser adicionar isso. E, espero, jogar o mais rápido possível.

Para adicionar de um a seis, isso é algum trabalho. Mas você vê, para adicionar de um a dez, isso é mais trabalho?

Big O é seu amigo e meu. Big O nos ajuda a pensar em quanto trabalho temos que fazer, para que possamos planejar. E, se somos amigos de O grande, ele pode nos ajudar a escolher um trabalho que não é tão difícil!

Agora devemos fazer um novo trabalho. Ah não. Eu não gosto dessa coisa de trabalho.

O novo trabalho é: adicione todas as coisas de um a n.

Esperar! O que é n? Eu senti falta disso? Como posso adicionar de um a n se você não me diz o que é n?

Bem, eu não sei o que é n. Eu não fui informado. Você estava? Não? Ah bem. Então não podemos fazer o trabalho. Ufa.

Mas, embora não façamos o trabalho agora, podemos adivinhar o quão difícil seria, se soubéssemos que n. Teríamos que somar n coisas, certo? Claro!

Agora vem o grande O, e ele nos dirá o quão difícil é esse trabalho. Ele diz: adicionar todas as coisas de uma a N, uma a uma, é O (n). Para adicionar todas essas coisas, [eu sei que devo adicionar n vezes.] [1] Isso é grande O! Ele nos diz como é difícil fazer algum tipo de trabalho.

Para mim, penso em grande como um grande e lento chefe. Ele pensa no trabalho, mas não o faz. Ele pode dizer: "Esse trabalho é rápido". Ou, ele pode dizer: "Esse trabalho é tão lento e difícil!" Mas ele não faz o trabalho. Ele apenas olha o trabalho e depois nos diz quanto tempo pode levar.

Eu me importo muito com o grande O. Por quê? Eu não gosto de trabalhar! Ninguém gosta de trabalhar. É por isso que todos nós amamos o grande O! Ele nos diz o quão rápido podemos trabalhar. Ele nos ajuda a pensar em quão difícil é o trabalho.

Mais trabalho. Agora, não vamos fazer o trabalho. Mas, vamos fazer um plano para fazê-lo, passo a passo.

Eles nos deram um baralho de dez cartas. Eles estão todos misturados: sete, quatro, dois, seis ... nem um pouco heterossexuais. E agora ... nosso trabalho é classificá-los.

Ergh. Parece muito trabalho!

Como podemos classificar esse baralho? Eu tenho um plano.

Vou olhar para cada par de cartas, par a par, através do baralho, do primeiro ao último. Se a primeira carta de um par for grande e a próxima carta desse par for pequena, eu as troco. Senão, eu vou para o próximo par, e assim por diante ... e logo, o baralho está pronto.

Quando o baralho termina, pergunto: troquei as cartas nesse passe? Nesse caso, devo fazer tudo de novo, de cima para baixo.

Em algum momento, em algum momento, não haverá trocas, e nosso tipo de baralho estará pronto. Muito trabalho!

Bem, quanto trabalho isso seria para classificar os cartões com essas regras?

Eu tenho dez cartas. E, na maioria das vezes - ou seja, se eu não tiver muita sorte - devo percorrer o baralho inteiro até dez vezes, com até dez trocas de cartas por vez.

Big O, me ajude!

Big O entra e diz: para um baralho de n cartas, classificá-lo desta maneira será feito em O (N ao quadrado).

Por que ele diz n ao quadrado?

Bem, você sabe que n ao quadrado é n vezes n. Agora, entendi: n cartas marcadas, até o que pode ser n vezes no baralho. São dois loops, cada um com n etapas. Isso é n ao quadrado muito trabalho a ser feito. Muito trabalho, com certeza!

Agora, quando O grande diz que será necessário trabalhar com O (n ao quadrado), ele não significa que n acrescenta ao quadrado no nariz. Pode ser um pouco menos, em alguns casos. Mas, na pior das hipóteses, estará perto de n passos quadrados de trabalho para classificar o convés.

Agora, aqui é onde grande O é nosso amigo.

Big O aponta o seguinte: quando n cresce, quando ordenamos as cartas, o trabalho fica MUITO MAIS DURO do que o antigo trabalho de adicionar essas coisas. Como nós sabemos disso?

Bem, se n ficar muito grande, não nos importamos com o que podemos adicionar a n ou n ao quadrado.

Para n grande, n ao quadrado é mais grande que n.

Big O nos diz que classificar as coisas é mais difícil do que adicioná-las. O (n quadrado) é maior que O (n) para o grande n. Isso significa: se n ficar muito grande, classificar um conjunto misto de n coisas DEVE levar mais tempo do que apenas adicionar n coisas mistas.

Big O não resolve o trabalho para nós. Big O nos diz o quão difícil é o trabalho.

Eu tenho um baralho de cartas. Eu os classifiquei. Você ajudou. Obrigado.

Existe uma maneira mais rápida de classificar os cartões? O grande O pode nos ajudar?

Sim, existe uma maneira mais rápida! Demora algum tempo para aprender, mas funciona ... e funciona muito rápido. Você pode tentar também, mas não se apresse em cada passo.

Nesta nova maneira de classificar um baralho, não verificamos pares de cartas como fizemos há um tempo atrás. Aqui estão suas novas regras para classificar esse deck:

Um: escolho uma carta na parte do baralho em que trabalhamos agora. Você pode escolher um para mim, se quiser. (A primeira vez que fazemos isso, “a parte do deck em que trabalhamos agora” é o deck inteiro, é claro.)

Dois: Eu mostro o baralho na carta que você escolheu. O que é essa cena; como eu mostro? Bem, vou da carta inicial para baixo, uma a uma, e procuro uma carta que seja mais alta que a carta de exibição.

Terceiro: eu vou da carta final para cima e procuro uma carta mais baixa que a carta de exibição.

Depois de encontrar essas duas cartas, troco-as e procuro mais cartas para trocar. Ou seja, volto ao passo dois e jogo no cartão que você escolheu um pouco mais.

Em algum momento, esse loop (de dois a três) terminará. Termina quando as duas partes desta pesquisa se encontram no cartão de jogo. Então, acabamos de espalhar o baralho com a carta que você escolheu na etapa Um. Agora, todas as cartas perto do início são mais baixas que a carta de exibição; e as cartas perto do fim são mais altas que as cartas de exibição. Truque legal!

Quatro (e essa é a parte divertida): agora tenho dois baralhos pequenos, um mais baixo que o cartão de jogo e outro mais alto. Agora vou para o primeiro passo, em cada pequeno deck! Ou seja, começo do passo Um no primeiro pequeno deck, e quando esse trabalho é concluído, começo do passo Um no próximo pequeno deck.

Eu quebro o convés em partes e separo cada parte, cada vez mais pequena, e em algum momento não tenho mais trabalho a fazer. Agora isso pode parecer lento, com todas as regras. Mas confie em mim, não é nada lento. É muito menos trabalho do que a primeira maneira de classificar as coisas!

Como é chamado esse tipo? Chama-se Classificação Rápida! Esse tipo foi feito por um homem chamado CAR Hoare e ele chamou de Quick Sort. Agora, o Quick Sort é usado o tempo todo!

A Classificação Rápida divide os decks grandes em pequenos. Ou seja, divide grandes tarefas em pequenas.

Hummm. Pode haver uma regra lá, eu acho. Para tornar pequenas tarefas grandes, divida-as.

Este tipo é bastante rápido. Quão rápido? Big O nos diz: esse tipo precisa de trabalho de O (n log n) a ser feito, no caso médio.

É mais ou menos rápido que o primeiro? Big O, por favor me ajude!

O primeiro tipo foi O (n quadrado). Mas a Classificação Rápida é O (n log n). Você sabe que n log n é menor que n ao quadrado, para n grande, certo? Bem, é assim que sabemos que o Quick Sort é rápido!

Se você precisar classificar um baralho, qual é a melhor maneira? Bem, você pode fazer o que quiser, mas eu escolheria Classificação rápida.

Por que escolho a classificação rápida? Eu não gosto de trabalhar, é claro! Quero que o trabalho seja feito o mais rápido possível.

Como sei se o Quick Sort é menos trabalhoso? Eu sei que O (n log n) é menor que O (n ao quadrado). Os O's são mais pequenos, portanto, o Quick Sort é menos trabalhoso!

Agora você conhece meu amigo, Big O. Ele nos ajuda a fazer menos trabalho. E se você conhece O grande, também pode fazer menos trabalho!

Você aprendeu tudo isso comigo! Você é tão esperto! Muito obrigado!

Agora que o trabalho está pronto, vamos brincar!

[1]: Existe uma maneira de trapacear e adicionar todas as coisas de um a n, tudo de uma vez. Um garoto chamado Gauss descobriu isso aos oito anos. Eu não sou tão inteligente assim, então não me pergunte como ele fez isso .

Eu tenho uma maneira mais simples de entender a complexidade do tempo que a métrica mais comum para calcular a complexidade do tempo é a notação Big O. Isso remove todos os fatores constantes para que o tempo de execução possa ser estimado em relação a N à medida que N se aproxima do infinito. Em geral, você pode pensar assim:

statement;

É constante. O tempo de execução da instrução não será alterado em relação a N

for ( i = 0; i < N; i++ )
  statement;

É linear. O tempo de execução do loop é diretamente proporcional a N. Quando N dobra, o tempo de execução também.

for ( i = 0; i < N; i++ ) 
{
for ( j = 0; j < N; j++ )
  statement;
}

É quadrático. O tempo de execução dos dois loops é proporcional ao quadrado de N. Quando N dobra, o tempo de execução aumenta em N * N.

while ( low <= high ) 
{
 mid = ( low + high ) / 2;
 if ( target < list[mid] )
 high = mid - 1;
 else if ( target > list[mid] )
  low = mid + 1;
else break;
}

É logarítmico. O tempo de execução do algoritmo é proporcional ao número de vezes que N pode ser dividido por 2. Isso ocorre porque o algoritmo divide a área de trabalho ao meio a cada iteração.

void quicksort ( int list[], int left, int right )
{
  int pivot = partition ( list, left, right );
  quicksort ( list, left, pivot - 1 );
  quicksort ( list, pivot + 1, right );
}

É N * log (N). O tempo de execução consiste em N loops (iterativos ou recursivos) que são logarítmicos, portanto, o algoritmo é uma combinação de linear e logarítmico.

Em geral, fazer algo com cada item em uma dimensão é linear, fazer algo com cada item em duas dimensões é quadrático e dividir a área de trabalho pela metade é logarítmico. Existem outras medidas do Big O, como raiz cúbica, exponencial e quadrada, mas elas não são tão comuns. A notação O grande é descrita como O () onde está a medida. O algoritmo quicksort seria descrito como O (N * log (N)).

Nota: Nada disso levou em consideração as melhores, médias e piores medidas. Cada um teria sua própria notação Big O. Observe também que esta é uma explicação MUITO simplista. Big O é o mais comum, mas também é mais complexo que eu mostrei. Também existem outras notações, como ômega grande, ovo pequeno e grande teta. Você provavelmente não os encontrará fora de um curso de análise de algoritmos.

• Veja mais em: Aqui

Diga que você compra Harry Potter: Complete 8-Film Collection [Blu-ray] da Amazon e baixa a mesma coleção de filmes on-line ao mesmo tempo. Você deseja testar qual método é mais rápido. A entrega demora quase um dia para chegar e o download foi concluído cerca de 30 minutos antes. Ótimo! Então é uma corrida acirrada.

E se eu pedir vários filmes em Blu-ray como O Senhor dos Anéis, Crepúsculo, A Trilogia do Cavaleiro das Trevas, etc. e baixar todos os filmes on-line ao mesmo tempo? Dessa vez, a entrega ainda leva um dia para ser concluída, mas o download on-line leva três dias para ser concluído. Para compras on-line, o número de itens comprados (entrada) não afeta o tempo de entrega. A saída é constante. Chamamos isso de O (1) .

Para download online, o tempo de download é diretamente proporcional aos tamanhos dos arquivos de filme (entrada). Chamamos isso de O (n) .

A partir das experiências, sabemos que as compras on-line são melhores que o download on-line. É muito importante entender a notação O grande, pois ajuda a analisar a escalabilidade e a eficiência dos algoritmos.

Nota: A notação Big O representa o pior cenário de um algoritmo. Vamos supor que O (1) e O (n) são os piores cenários do exemplo acima.

Referência : http://carlcheo.com/compsci

Suponha que estamos falando de um algoritmo A , que deve fazer algo com um conjunto de dados de tamanho n .

Então O( <some expression X involving n> )significa, em inglês simples:

Se você tiver azar ao executar A, pode levar até X (n) operações para concluir.

Por acaso, existem certas funções (pense nelas como implementações de X (n) ) que tendem a ocorrer com bastante frequência. Estes são bem conhecidos e facilmente comparadas (Exemplos: 1, Log N, N, N^2, N!, etc ..)

Ao compará-los ao falar sobre A e outros algoritmos, é fácil classificar os algoritmos de acordo com o número de operações que eles podem (no pior caso) exigir para concluir.

Em geral, nosso objetivo será encontrar ou estruturar um algoritmo A de forma que ele tenha uma função X(n)que retorne o menor número possível.

Se você tem uma noção adequada de infinito em sua cabeça, há uma descrição muito breve:

A notação O grande indica o custo de resolver um problema infinitamente grande.

E além disso

Fatores constantes são insignificantes

Se você atualizar para um computador que possa executar seu algoritmo duas vezes mais rápido, a notação O grande não notará isso. As melhorias constantes dos fatores são pequenas demais para serem notadas na escala com a qual a grande notação O funciona. Observe que essa é uma parte intencional do design da grande notação O.

Embora qualquer coisa "maior" que um fator constante possa ser detectada, no entanto.

Quando estiver interessado em fazer cálculos cujo tamanho é "grande" o suficiente para ser considerado aproximadamente infinito, a notação O grande é aproximadamente o custo de resolver seu problema.

Se o que precede não faz sentido, você não tem uma noção intuitiva compatível do infinito em sua cabeça e provavelmente desconsidera todas as anteriores; a única maneira que sei de tornar essas idéias rigorosas ou de explicá-las, se ainda não são intuitivamente úteis, é primeiro ensinar-lhe grande notação de O ou algo semelhante. (embora, depois de entender bem a grande notação O no futuro, valha a pena revisar essas idéias)

O que é uma explicação simples em inglês da notação "Big O"?

Nota muito rápida:

O O em "Big O" refere-se a "Ordem" (ou precisamente "ordem de"),
para que você possa ter uma idéia literal de que ela é usada para pedir algo para compará-los.

• "Big O" faz duas coisas:

  1. Estima quantas etapas do método seu computador aplica para realizar uma tarefa.
  2. Facilitar o processo para comparar com os outros, a fim de determinar se é bom ou não?
  3. "Big O 'alcança os dois acima com padronizado Notations.

• Existem sete notações mais usadas

  1. O (1), significa que o computador realiza uma tarefa com 1passo, é excelente, pedido nº 1
  2. O (logN), significa que o seu computador conclui uma tarefa com as logNetapas necessárias.
  3. O (N), conclua uma tarefa com Netapas, é justo, Ordem No.3
  4. O (NlogN), finaliza uma tarefa com O(NlogN)etapas, não é bom, pedido nº 4
  5. O (N ^ 2), conclua uma tarefa com N^2etapas, é ruim, pedido no.5
  6. O (2 ^ N), conclua uma tarefa com 2^Netapas, é horrível, Pedido No.6
  7. O (N!), Faça uma tarefa com N!passos, é terrível, Ordem No.7

Suponha que você receba notação O(N^2), não apenas esteja claro que o método executa N * N etapas para realizar uma tarefa, mas também verá que ele não é bom devido O(NlogN)à sua classificação.

Observe a ordem no final da linha, apenas para sua melhor compreensão. Existem mais de 7 notações, se todas as possibilidades forem consideradas.

No CS, o conjunto de etapas para realizar uma tarefa é chamado de algoritmos.
Na terminologia, a notação Big O é usada para descrever o desempenho ou a complexidade de um algoritmo.

Além disso, o Big O estabelece o pior caso ou mede as etapas do limite superior.
Você pode consultar o Big-Ω (Big-Omega) para melhor caso.

Notação Big-Ω (Big-Omega) (artigo) | Khan Academy

• Sumário
  "Big O" descreve o desempenho do algoritmo e o avalia.

  ou abordá-lo formalmente, "Big O" classifica os algoritmos e padroniza o processo de comparação.

Maneira mais simples de ver (em inglês simples)

Estamos tentando ver como o número de parâmetros de entrada afeta o tempo de execução de um algoritmo. Se o tempo de execução do seu aplicativo for proporcional ao número de parâmetros de entrada, é dito que ele está no Big O de n.

A afirmação acima é um bom começo, mas não completamente verdadeira.

Uma explicação mais precisa (matemática)

Suponha

n = número de parâmetros de entrada

T (n) = A função real que expressa o tempo de execução do algoritmo como uma função de n

c = uma constante

f (n) = Uma função aproximada que expressa o tempo de execução do algoritmo como uma função de n

Então, no que diz respeito ao Big O, a aproximação f (n) é considerada boa o suficiente, desde que a condição abaixo seja verdadeira.

lim     T(n) ≤ c×f(n)
n→∞

A equação é lida à medida que n se aproxima do infinito, T de n é menor ou igual a c vezes f de n.

Na grande notação O, isso é escrito como

T(n)∈O(n)

Isto é lido como T de n está em grande O de n.

Voltar ao Inglês

Com base na definição matemática acima, se você diz que seu algoritmo é um Big O de n, significa que é uma função de n (número de parâmetros de entrada) ou mais rápido . Se o seu algoritmo for Big O de n, também será automaticamente o Big O de n quadrado.

Big O of n significa que meu algoritmo é executado pelo menos tão rápido quanto isso. Você não pode olhar para a notação Big O do seu algoritmo e dizer lenta. Você só pode dizer que é rápido.

Confira este tutorial em vídeo sobre o Big O da UC Berkley. É na verdade um conceito simples. Se você ouvir o professor Shewchuck (também conhecido como professor de nível de Deus) explicando, você dirá "Oh, é só isso!".

Encontrei uma explicação realmente ótima sobre a notação O grande, especialmente para alguém que não gosta muito de matemática.

https://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/

A notação Big O é usada na Ciência da Computação para descrever o desempenho ou a complexidade de um algoritmo. Big O descreve especificamente o pior cenário possível e pode ser usado para descrever o tempo de execução necessário ou o espaço usado (por exemplo, na memória ou no disco) por um algoritmo.

Qualquer um que tenha lido Programming Pearls ou qualquer outro livro de Ciência da Computação e não tenha uma base em Matemática terá atingido um muro quando alcançou capítulos que mencionam O (N log N) ou outra sintaxe aparentemente louca. Esperamos que este artigo ajude você a entender os conceitos básicos do Big O e dos logaritmos.

Como programador primeiro e matemático segundo (ou talvez terceiro ou quarto), encontrei a melhor maneira de entender o Big O completamente, produzindo alguns exemplos em código. Portanto, abaixo estão algumas ordens comuns de crescimento, juntamente com descrições e exemplos sempre que possível.

O (1)

O (1) descreve um algoritmo que sempre será executado no mesmo tempo (ou espaço), independentemente do tamanho do conjunto de dados de entrada.

bool IsFirstElementNull(IList<string> elements) {
    return elements[0] == null;
}

EM)

O (N) descreve um algoritmo cujo desempenho aumentará linearmente e em proporção direta ao tamanho do conjunto de dados de entrada. O exemplo abaixo também demonstra como o Big O favorece o pior cenário de desempenho; uma string correspondente poderia ser encontrada durante qualquer iteração do loop for e a função retornaria mais cedo, mas a notação Big O sempre assumirá o limite superior onde o algoritmo executará o número máximo de iterações.

bool ContainsValue(IList<string> elements, string value) {
    foreach (var element in elements)
    {
        if (element == value) return true;
    }

    return false;
} 

O (N ² )

O (N ² ) representa um algoritmo cujo desempenho é diretamente proporcional ao quadrado do tamanho do conjunto de dados de entrada. Isso é comum em algoritmos que envolvem iterações aninhadas no conjunto de dados. Iterações aninhadas mais profundas resultarão em O (N ³ ), O (N ⁴ ) etc.

bool ContainsDuplicates(IList<string> elements) {
    for (var outer = 0; outer < elements.Count; outer++)
    {
        for (var inner = 0; inner < elements.Count; inner++)
        {
            // Don't compare with self
            if (outer == inner) continue;

            if (elements[outer] == elements[inner]) return true;
        }
    }

    return false;
}

O (2 ^N )

O (2 ^N ) denota um algoritmo cujo crescimento dobra com cada aditivo no conjunto de dados de entrada. A curva de crescimento de uma função O (2 ^N ) é exponencial - começando muito rasa e depois subindo meteoricamente. Um exemplo de uma função O (2 ^N ) é o cálculo recursivo dos números de Fibonacci:

int Fibonacci(int number) {
    if (number <= 1) return number;

    return Fibonacci(number - 2) + Fibonacci(number - 1);
}

Logaritmos

Os logaritmos são um pouco mais difíceis de explicar, então usarei um exemplo comum:

Pesquisa binária é uma técnica usada para pesquisar conjuntos de dados classificados. Ele funciona selecionando o elemento do meio do conjunto de dados, essencialmente a mediana, e o compara com um valor de destino. Se os valores corresponderem, retornará sucesso. Se o valor de destino for maior que o valor do elemento de análise, ele pegará a metade superior do conjunto de dados e executará a mesma operação contra ele. Da mesma forma, se o valor alvo for menor que o valor do elemento de sonda, ele executará a operação na metade inferior. Ele continuará dividindo o conjunto de dados pela metade a cada iteração até que o valor seja encontrado ou até que ele não possa mais dividir o conjunto de dados.

Este tipo de algoritmo é descrito como O (log N). A metade iterativa dos conjuntos de dados descritos no exemplo de pesquisa binária produz uma curva de crescimento que atinge o pico no início e se achata lentamente à medida que o tamanho dos conjuntos de dados aumenta, por exemplo, um conjunto de dados de entrada contendo 10 itens leva um segundo para concluir, um conjunto de dados contendo 100 itens leva dois segundos e um conjunto de dados contendo 1000 itens leva três segundos. Dobrar o tamanho do conjunto de dados de entrada tem pouco efeito sobre seu crescimento, pois após uma única iteração do algoritmo, o conjunto de dados será dividido pela metade e, portanto, em pé de igualdade com um conjunto de dados de entrada com metade do tamanho. Isso torna algoritmos como a pesquisa binária extremamente eficientes ao lidar com grandes conjuntos de dados.

Essa é uma explicação muito simplificada, mas espero que cubra os detalhes mais importantes.

Digamos que seu algoritmo que lida com o problema dependa de alguns "fatores", por exemplo, vamos torná-lo N e X.

Dependendo de N e X, seu algoritmo exigirá algumas operações, por exemplo, no PIOR caso, são 3(N^2) + log(X)operações.

Como o Big-O não se importa muito com o fator constante (também conhecido como 3), o Big-O do seu algoritmo é O(N^2 + log(X)). Ele basicamente traduz 'a quantidade de operações que seu algoritmo precisa para as piores escalas de escala com isso'.

Prefácio

algoritmo : procedimento / fórmula para resolver um problema

Como analisamos algoritmos e como podemos comparar algoritmos entre si?

exemplo: você e um amigo são solicitados a criar uma função para somar os números de 0 a N. Você cria f (x) e seu amigo cria g (x). Ambas as funções têm o mesmo resultado, mas um algoritmo diferente. Para comparar objetivamente a eficiência dos algoritmos, usamos a notação Big-O .

Notação Big-O: descreve a rapidez com que o tempo de execução aumentará em relação à entrada à medida que a entrada for arbitrariamente grande.

3 principais tópicos:

1. Compare a rapidez com que o tempo de execução cresce NÃO compara os tempos de execução exatos (depende do hardware)
2. Apenas preocupado com o tempo de execução cresce em relação à entrada (n)
3. À medida que n se torna arbitrariamente grande, concentre-se nos termos que crescerão mais rapidamente à medida que n se tornar maior (pense no infinito) AKA análise assintótica

Complexidade do espaço: além da complexidade do tempo, também nos preocupamos com a complexidade do espaço (quanta memória / espaço um algoritmo usa). Em vez de verificar o tempo das operações, verificamos o tamanho da alocação de memória.