O que é um inglês simples explicação do "Big O" notação?

https://stackoverflow.com/questions/487258

20-08-2019
|

Pergunta

Eu prefiro tão pouco a definição formal possível e simples de matemática.

Solução

Nota rápida, isto é, quase certamente confuso Big O notation (o que é um limite superior) com Theta notação de "Θ" (que é um dois laterais-bound).Na minha experiência, isso é realmente típico de discussões em não-acadêmico.Pedimos desculpas por qualquer confusão causada.

Grande S de complexidade podem ser visualizados com este gráfico:

Big O Analysis

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

Big O notation é um parente representação da complexidade de um algoritmo.

Existem algumas importantes e deliberadamente escolhido palavras na frase:

em relação: apenas pode comparar maçãs com maçãs.Você não pode comparar um algoritmo para fazer aritmética de multiplicação de um algoritmo que ordena uma lista de inteiros.Mas uma comparação de dois algoritmos para fazer operações aritméticas (uma multiplicação, uma adição) irá dizer-lhe algo significativo;

representação: Big-O (na 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, algoritmos de ordenação são normalmente comparadas com base em operações de comparação (comparação de dois nós para determinar a sua relativa de ordenação).Isso pressupõe que a comparação é caro.Mas se a comparação é barato, mas a troca é caro?Ele muda a comparação;e

complexidade: se ele me leva um segundo a classificação de 10.000 elementos quanto tempo será que vai demorar muito para classificar um milhão?A complexidade desta instância é uma medida relativa para outra coisa.

Voltar e reler o acima, quando você ler o resto.

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

adição;

subtração;

multiplicação;e

divisão.

Cada uma destas é uma operação ou um problema.Um método de resolução destes é chamado de algoritmo.

A adição é a mais simples.Que linha o número para cima (para a direita) e somar os dígitos em uma coluna de escrever o último número da adição no resultado.O 'dezenas' parte desse número é transferido para o próximo da coluna.

Vamos supor que a adição destes números é o mais caro do funcionamento deste algoritmo.É lógico que para adicionar esses dois números juntos temos que adicionar 6 dígitos (e, possivelmente, levar um 7º).Se somarmos dois de 100 números de dígitos, juntos, temos de fazer 100 adições.Se acrescentarmos dois De 10.000 números de dígitos que temos de fazer de 10.000 adições.

Ver o padrão?O a complexidade (sendo o número de operações) é diretamente proporcional ao número de dígitos n em maior número.Nós chamamos isso de O(n) ou complexidade linear.

A subtração é similar, exceto que você pode precisar pedir emprestado em vez de transportar).

A multiplicação é diferente.Você linha os números até o primeiro algarismo da parte inferior do número e multiplicar por sua vez contra cada dígito no número de cima e assim por diante através de cada dígito.Para multiplicar os nossos dois de 6 dígitos, números de nós deve fazer 36 multiplicações.Precisamos fazer como muitos como 10 ou 11 coluna adiciona para obter o resultado final também.

Se temos dois 100 dígitos e precisamos fazer de 10.000 multiplicações e 200 acrescenta.Para um ou dois milhões de algarismos precisamos fazer um trilhão (10¹²) multiplicações e dois milhões, acrescenta.

Como o algoritmo de escalas com n-ao quadrado, isso é O(n²) ou a complexidade quadrática.Este é um bom momento para introduzir outro conceito importante:

Nós só se preocupam 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 o do nosso exemplo com dois números de um milhão de dígitos cada, o segundo termo de (2n) torna-se insignificante (contabilização de 0,0002% do total de operações por estágio).

Pode-se notar que assumimos que o cenário de pior caso aqui.Enquanto a multiplicação de 6 dígitos, números, se um deles é de 4 dígitos e o outro é de 6 dígitos, então temos apenas 24 multiplicações.Ainda podemos calcular o pior cenário para o 'n', eu.e quando ambos são 6 dígitos.Daí o Grande-O a notação é sobre o cenário de Pior caso de um algoritmo

O Livro De Telefone

O melhor exemplo que posso pensar é o livro de telefone, normalmente chamados de Páginas Brancas ou similares, mas isso vai variar de país para país.Mas eu estou falando sobre o que as listas de pessoas pelo sobrenome e, em seguida, as iniciais ou o primeiro nome, possivelmente, o endereço e os números de telefone.

Agora, se você estivesse instruindo um computador para procurar o número de telefone do "João da silva", em um livro de telefone que contém 1.000.000 de nomes, o que você faria?Ignorando o fato de que você pode imaginar quanto no S do iniciado (vamos supor que você não pode), o que faria?

Uma implementação típica pode ser abrir-se ao meio, tirar as 500.000^th e compará-lo com "Smith".Se ele passa a ser "silva, João", ficamos muito felizes.Muito mais provável é que "John Smith" vai ser antes ou depois do nome.Se depois de nós, em seguida, divida a última metade do livro de telefone em meia, repetir.Se antes, em seguida, dividimos a primeira metade do livro de telefone em meia, repetir.E assim por diante.

Isso é chamado de busca binária e é usado todos os dias na programação quer você perceba ou não.

Então, se você deseja encontrar um nome na lista telefônica de um milhão de nomes que você pode realmente encontrar qualquer nome fazendo isso em mais de 20 vezes.Na comparação de algoritmos de busca decidimos que esta comparação é o nosso 'n'.

Para um livro de telefone, de 3 de nomes que leva 2 comparações (no máximo).

Para 7 demora no máximo 3.

15 ela tem 4.

…

Para 1.000.000 leva 20.

Que é incrivelmente bom, não é?

No Big-O termo é esse O(n log n) ou logarítmica complexidade.Agora o logaritmo em questão poderia ser ln (base e), log₁₀, log₂ ou alguma outra base.Não importa se é ainda O(n log n) como O(2n²) e O(100n²) ainda são O(n²).

Vale a pena, neste momento, explicar que O Grande pode ser usado para determinar três casos com um algoritmo:

Melhor Caso: No livro de telefone de pesquisa, o melhor caso é que encontramos o nome de uma comparação.Este é O(1) ou constante de complexidade;

Caso Esperado: Como discutido acima, este é O(n log n);e

Pior Caso: Este também é O(n log n).

Normalmente, nós não nos preocupamos com o melhor caso.Estamos interessados em que o esperado e pior caso.Às vezes, um ou outro destes será mais importante.

De volta para o livro de telefone.

O que se você tiver um número de telefone e quer encontrar um nome?A polícia tem um reverso do telefone livro, mas tais look-ups são negados ao público em geral.Ou são eles?Tecnicamente, você pode inverter o olhar-um número comum de livro de telefone.Como?

Você pode começar o primeiro nome e comparar o número.Se é um jogo, ótimo, se não, você se move para a próxima.Você tem que fazê-lo desta forma porque o telefone livro não ordenado (através do número de telefone de qualquer maneira).

Então, para encontrar um nome dado a um número de telefone (reverse lookup):

Melhor Caso: O(1);

Caso Esperado: O(n) (para 500.000);e

Pior Caso: O(n) (por 1,000,000).

O Caixeiro-Viajante

Este é um famoso problema em ciência da computação e merece uma menção.Neste problema que você tem N cidades.Cada uma dessas cidades está vinculada a 1 ou mais outras cidades, por uma estrada de uma certa distância.O problema do Caixeiro viajante é encontrar o menor tour que visita cada cidade.

Parece simples?Pense novamente.

Se você tem 3 cidades A, B e C, com estradas entre todos os pares em seguida, você pode ir:

A → B → C

A → C → B

B → C → A

B → A → C

C → A → B

C → B → A

Bem, na verdade há menos de que uma vez que alguns destes são equivalentes (A → B → C e C → B → A é equivalente, por exemplo, porque eles usam o mesmo estradas, apenas no sentido inverso).

Na verdade, existem 3 possibilidades.

Leve isso para 4 cidades e que você tem (iirc) 12 possibilidades.

Com 5 60.

6 se torna 360.

Esta é uma função de uma operação matemática chamada de uma factorial.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⁶⁴

Assim, o Grande-O do problema do Caixeiro viajante é O(n!) ou fatorial ou complexidade combinatória.

Pelo tempo que você chegar a 200 cidades não há tempo suficiente no universo para resolver o problema com os computadores tradicionais.

Algo para se pensar.

Em Tempo Polinomial

Outro ponto que eu queria fazer rápida menção é que qualquer algoritmo que tem uma complexidade de O(n^um) é dito ter o polinômio de complexidade ou é solucionável em em tempo polinomial.

O(n), O(n²) etc.estão todos em tempo polinomial.Alguns problemas não podem ser resolvidos em tempo polinomial.Certas coisas são utilizados no mundo devido a isso. Criptografia De Chave Pública é um excelente exemplo.É computacionalmente difícil encontrar dois fatores primos de um número muito grande.Se não fosse, nós não poderíamos usar a chave pública dos sistemas de usar.

De qualquer maneira, isso é para o meu (espero planície inglês) explicação da Grande S (revista).

Outras dicas

Ele mostra como uma escala de algoritmo.

Sobre²): 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 assim O (n²) nos dá o fator de escala n² que é 10².

Sobre): 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 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. Então, neste caso, assumindo que cada cálculo leva 1 segundo, o log da entrada n é o tempo necessário, daí 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.

Big O notation (também chamado de "crescimento assintótico" notation) é quais as funções "aparência" quando você ignorar fatores constantes e coisas perto de origem.Nós a usamos para falar sobre como coisa escala.

Noções básicas

para "suficientemente" grande entradas...

f(x) ∈ O(upperbound) significa f "não cresce mais rápido do que o" upperbound
f(x) ∈ Ɵ(justlikethis) média f "cresce exatamente como" justlikethis
f(x) ∈ Ω(lowerbound) significa f "cresce sem mais lento do que o" lowerbound

grande-O a notação não se importa com os fatores constantes:a função 9x² é dito para "crescer exatamente como" 10x².Não é grande-O assimptótico a notação de cuidados sobre não assintótica coisas ("coisas de perto a origem" ou "o que acontece quando o problema é de tamanho pequeno"):a função 10x² é dito para "crescer exatamente como" 10x² - x + 2.

Por que você iria querer ignorar as pequenas partes da equação?Porque eles se tornam completamente ofuscado pela grande partes da equação, que considere escala cada vez maior;sua contribuição torna-se insignificante e irrelevante.(Consulte o exemplo de secção.)

Dito de outra forma, é tudo sobre o taxa de como você vai para o infinito. Se você dividir o tempo real que leva o O(...), você vai obter um fator constante no limite de grandes entradas. Intuitivamente isto faz sentido:funções de "escala como" o outro, se você pode multiplicar um para começar o outro.Isto é, quando dizemos...

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

...isto significa que para o "grande o suficiente" problema tamanhos N (se ignorarmos coisas perto de origem), de que existe algum constante (por exemplo,2.5, totalmente feita) tal que:

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

Existem muitas opções de constante;muitas vezes a "melhor" escolha é conhecido como o "fator constante" do algoritmo...mas nós, muitas vezes, ignoram como ignorarmos não maior de termos (ver Fatores Constantes da seção para a qual geralmente não se importa).Você também pode considerar a equação acima como uma ligação, dizendo que "No cenário de pior caso, o tempo nunca vai ser pior do que cerca de N*log(N), dentro de um fator de 2,5 (um fator constante, nós não se importa muito)".

Em geral, O(...) é o mais útil, porque muitas vezes preocupam com pior comportamento.Se f(x) representa algo "ruim", como o processador ou o uso de memória e, em seguida,"f(x) ∈ O(upperbound)"meios "upperbound é o cenário de pior caso de um processador de uso de memória".

Aplicações

Como puramente construção matemática, big-O a notação não se limita a falar sobre o tempo de processamento e memória.Você pode usá-lo para discutir o asymptotics de qualquer coisa onde o dimensionamento é significativa, tais como:

o número de possíveis apertos de mão entre N pessoas em uma festa (Ɵ(N²), especificamente N(N-1)/2, mas o que importa é que ele "escalas como" N²)
probabilística número esperado de pessoas que viram alguns de marketing viral como uma função do tempo
como a latência do site é proporcional ao número de unidades de processamento de uma CPU ou GPU ou computador de cluster
como a saída de calor escalas de CPU morre como uma função do número de transistores, tensão, etc.
quanto tempo um algoritmo necessita para executar, como uma função do tamanho da entrada
quanto espaço um algoritmo necessita para executar, como uma função do tamanho da entrada

Exemplo

O handshake exemplo acima, todos em uma sala, batidos de todos os outros da mão.Nesse exemplo, #handshakes ∈ Ɵ(N²).Por quê?

Volta-se um pouco:o número de apertos de mão é exatamente n-escolher-2 ou N*(N-1)/2 (cada uma das N pessoas que sacode as mãos de N-1 outras pessoas, mas esta dupla contagem de apertos de mão para dividir por 2):

No entanto, para um grande número de pessoas, o termo linear N é ofuscado e contribui de maneira efetiva a 0 para a relaçã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 torna-se maior).Portanto, a escala de comportamento é order N², ou o número de apertos de mão "cresce como N2".

#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 foram até lá (N² marcas de verificação assintoticamente).

(temporário digressão de "plain English":) Se você queria provar isso a si mesmo, você pode realizar algumas simples álgebra em relação à divida-o em vários termos (lim significa "considerado no limite", simplesmente ignorá-lo se você ainda não viu, é só a notação "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 'parece' x2 tanto para grandes valores, que se nós fossemos escrever o rácio #apertos de mão/x2, o fato de que não precisamos de exatamente x2 apertos de mão não show em decimal para uma arbitrariamente grande de tempo.

exemplo:para x=1 milhão de dólares, a proporção #apertos de mão/x2:0.499999...

A Construção De Intuição

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

"Para grande o suficiente inputsize=N, não importa o que o fator constante é, se eu duplo o tamanho da entrada...

...Eu dobro o tempo de uma S(N) ("tempo linear") algoritmo leva."

N → (2N) = 2(N)
...Eu duplo-quadrado (quádruplo) o tempo O(N2) ("quadrática tempo") algoritmo leva." (e.g.um problema 100x tão grande leva 1002=10000x enquanto o...possivelmente, insustentável)

N2 → (2N)2 = 4(N2)
...Eu duas vezes em cubos (octuple) a um tempo O(N3) ("cúbicos de tempo") algoritmo leva." (e.g.um problema 100x tão grande leva 1003=1000000x enquanto o...muito insustentável)

cN3 → c(2N)3 = 8(cN3)
...Eu adição de um valor fixo para a hora que O(log(N)) ("logaritmo do tempo") algoritmo leva." (barato!)

c log(N) → c log(2N) = (c log(2))+(c log(N)) = (montante fixo)+(c log(N))
...Eu não alterar o tempo de uma S(1) ("constante de tempo") algoritmo leva." (o mais barato!)

c*1 → c*1
...Eu "(basicamente) duplo" a hora é de O(N log(N)) algoritmo leva." (bastante comum)

é menos do que O(N^1.000001), que você pode estar disposto a chamada basicamente linear
...Eu ridiculamente aumentar o tempo de um S(2^N) ("tempo exponencial") algoritmo leva." (você duplos (ou triplos, etc.) o tempo só aumentando o problema por uma única unidade)

2^N → 2^2N = (4^N)............posto de outra forma...... 2^N → 2^N+1 = 2^N2¹ = 2 2^N

[para matematicamente inclinado, você pode passar o mouse sobre os spoilers para menores notas]

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

(tecnicamente, o fator constante poderia talvez o assunto em mais esotérico exemplos, mas eu já formulada coisas acima (por exemplo,em log(N)), tais que não)

Estes são o pão-e-manteiga pedidos de crescimento que os programadores e aplicada, cientistas da computação usam como pontos de referência.Eles vêem isso o tempo todo.(Então, enquanto você pode, tecnicamente, acho que a "Duplicação da entrada faz um S(√N) algoritmo 1.414 vezes mais lento", é melhor pensar nele como "isto é pior do que logarítmica mas melhor do que linear".)

Fatores constantes

Geralmente, não nos importamos com o que a constante específica fatores são, porque eles não afetam a forma como a função cresce.Por exemplo, dois algoritmos pode levar O(N) o tempo para concluir, mas um pode ser duas vezes mais lenta que as outras.Nós normalmente não me importo muito, a menos que o fator é muito grande, desde que a otimização é complicado de negócios ( Quando é a otimização prematura? );também o simples ato de escolher um algoritmo com melhor big-O, muitas vezes, melhorar o desempenho por ordens de magnitude.

Alguns assintoticamente superior algoritmos (por exemplo,um não-comparação O(N log(log(N))) de classificação) pode ter tão grande a um fator constante (por exemplo, 100000*N log(log(N))), ou sobrecarga que é relativamente grande, como O(N log(log(N))) com um ocultos + 100*N, que raramente se vale a pena usar mesmo em "big data".

Por que O(N) é, às vezes, o melhor que você pode fazer, por exemplo,por que precisamos de datastructures

O(N) algoritmos são, em algum sentido, o "melhor" de algoritmos se você precisa ler todos os seus dados.O muito acto de leitura um monte de dados é um O(N) operação.Carregar na memória é geralmente O(N) (ou mais rápido se você tem um hardware de suporte, ou nenhuma hora em tudo, se você já leu os dados).No entanto, se você tocar ou até mesmo olhar em cada pedaço de dados (ou até mesmo todos os outros pedaço de dados), o algoritmo leva O(N) tempo para executar esta procurando.Nomatter quanto tempo real de seu algoritmo leva, vai ser pelo menos O(N) porque ele passou o tempo olhando para todos os dados.

O mesmo pode ser dito para o próprio ato de escrever.Todos os algoritmos que imprimir N coisas vai levar tempo, porque a saída é pelo menos esse tempo (e.g.imprimir todas as permutações (formas de reorganizar, de um conjunto de N cartas de jogar é factorial: O(N!)).

Isso motiva o uso de estruturas de dados:uma estrutura de dados que requer a leitura de dados apenas uma vez (geralmente O(N) tempo), além de algumas quantidade arbitrária de pré-processamento (e.g. O(N) ou O(N log(N)) ou O(N²)) que tentamos manter as pequenas.A partir daí, modificando a estrutura de dados (inserções / deleções / etc.) e fazer consultas sobre os dados de levar muito pouco tempo, como O(1) ou O(log(N)).Você, em seguida, continuar a fazer um grande número de consultas!Em geral, quanto mais trabalho você está disposto a fazer antes do tempo, menos trabalho você vai ter que fazer mais tarde.

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

Ingênua método:Se você tinha as coordenadas de um cruzamento de rua, e queria examinar as ruas próximas, você teria que ir através de milhões de segmentos de cada vez, e verifique cada um de adjacência.
Se você só precisava fazer isso uma vez, não seria um problema para fazer a ingênua método de O(N) trabalho apenas uma vez, mas se você quiser fazê-lo muitas vezes (neste caso, N vezes, uma vez para cada segmento), teríamos que fazer O(N²) de trabalho, ou 10000002=1000000000000 operações.Não é bom (um computador moderno pode realizar cerca de um bilhão de operações por segundo).
Se usamos uma simples estrutura chamada tabela de hash (um instante de velocidade, tabela de pesquisa, também conhecido como um hashmap ou dicionário), pagamos um pequeno custo por pré-processamento tudo O(N) em tempo.Daí em diante, ele só leva tempo constante, em média, para procurar algo pela sua chave (neste caso, a nossa chave é a coordenadas de latitude e longitude, arredondado em forma de grade;procuramos adjacentes gridspaces de que há apenas 9, que é uma constante).
A nossa tarefa foi a partir de uma inviável O(N²) gerenciável O(N), e tudo o que tinha a fazer era pagar um menor custo para fazer uma tabela de hash.
analogia:A analogia, neste caso particular, é um quebra-cabeça:Criamos uma estrutura de dados que explora alguns propriedade dos dados.Se a nossa estrada os segmentos são como peças de quebra-cabeça, podemos agrupá-los por tipo de correspondência de cor e padrão.Nós, em seguida, explorar esta para evitar de fazer trabalho extra posterior (comparando peças do quebra-cabeça de como a cor uns com os outros, não para todas as outras única peça do quebra-cabeça).

Moral da história:uma estrutura de dados que nos permite acelerar as operações.Ainda mais avançados de estruturas de dados permite que você combinar, atraso, ou até mesmo ignorar operações incrivelmente inteligente maneiras.Problemas diferentes teriam diferentes analogias, mas eles envolvem organizando os dados em uma forma que explore de alguma estrutura que nós nos importamos, ou que temos artificialmente impostas para a contabilidade.Nós fazemos o trabalho antes do tempo (basicamente, o planejamento e organização), e agora repete as tarefas são muito, muito mais fácil!

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

Notação assintótica é, em sua essência, completamente separado da programação.Notação assintótica é um modelo matemático para pensar em como as coisas escala, e pode ser usado em muitos campos diferentes.O que disse...isto é como você aplicar notação assintótica para a codificação.

O básico:Sempre que interagimos com todos os elementos de uma coleção de tamanho Um (como uma matriz, um conjunto, todas as chaves de um mapa, etc.), ou executar Um iterações de um loop, que é um multiplcative fator de tamanho A.Por que eu digo "um factor multiplicativo"?--porque loops e funções (quase por definição), tem multiplicativo tempo de execução:o número de iterações, os tempos de trabalho realizado no ciclo (ou para funções de:o número de vezes que você chamar a função, tempos, o trabalho feito na função).(Isto é, se não fizermos nada extravagante, como ignorar loops ou o ciclo de sair mais 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 acompanhamento de pseudocódigo.

(aqui, o xs representa a constante de tempo de unidades de trabalho, instruções de processador, intérprete de opcodes, 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 vamos fazer algo um pouco complicado, você ainda pode ser capaz de 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 reconhecível de estrutura de tópicos que você pode desenhar é o que importa;um triângulo é uma forma dimensional (0,5 A^2), assim como um quadrado é uma forma dimensional (A^2);o fator constante de dois aqui permanece na anī relação entre os dois, no entanto podemos ignorá-lo como todos os fatores...(Há alguns infeliz nuances para esta técnica de eu não ir para aqui;ele pode enganá-lo.)

É claro que isso não significa que os ciclos e funções são ruins;pelo contrário, eles são os blocos de construção de linguagens de programação modernas, e nós os amamos.No entanto, podemos ver que a maneira de tecer laços e funções e condicionais em conjunto com os nossos dados (controlo de fluxo, etc.) imita o tempo e o espaço de utilização do nosso programa!Se o tempo e o uso do espaço se torna um problema, que é quando podemos recorrer à esperteza, e encontrar um fácil algoritmo ou estrutura de dados nós não havíamos considerado, para reduzir a ordem de crescimento, de alguma forma.No entanto, estas técnicas de visualização (embora eles nem sempre funcionam) pode dar-lhe um ingênuo supor o pior caso de tempo de execução.

Aqui é outra coisa que temos que 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 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ê fazer log(N) passa dos dados, para O(N*log(N)) tempo total:

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

Unrelatedly mas vale a pena mencionar novamente:Se realizamos um hash (e.g.um dicionário / hashtable de pesquisa), que é um fator de O(1).Isso é muito rápido.

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

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

Se fazemos algo de muito complicado, como com uma função recursiva ou dividir-e-conquistar algoritmo, ~~você pode usar o Mestre Teorema (funciona normalmente), ou no ridículo casos, o Akra-Bazzi Teorema (quase sempre funciona)~~ você olha para cima o tempo de execução de seu algoritmo Wikipédia.

Mas, os programadores não pense assim, porque, eventualmente, o algoritmo de intuição só se torna uma segunda natureza.Você vai começar a codificar algo ineficiente, e imediatamente pensa "estou fazendo algo ineficiente?".Se a resposta é "sim" E prevê que, na verdade, importando, então você pode dar um passo para trás e pensar de vários truques para fazer as coisas correr mais rápido (a resposta é quase sempre "usar um hashtable", raramente "o uso de uma árvore", e muito raramente algo um pouco mais complicado).

Amortizado e média-caso complexidade

Há também o conceito de "amortizado" e/ou "média de caso" (note que estes são diferentes).

Caso Médio:Isto não é mais do que a utilização de grandes-O a notação para o valor esperado de uma função, em vez de a própria função.No caso usual onde você considerar todos os insumos sejam igualmente prováveis, o caso médio é apenas a média do tempo de execução.Por exemplo, com o quicksort, mesmo que o pior caso é O(N^2) para alguns muito ruim entradas, o caso médio é o costume O(N log(N)) (o que é realmente muito ruim entradas são muito pequenos em número, para alguns que nós não notá-los no caso médio).

Amortizado De Pior Caso:Algumas estruturas de dados pode ter um pior caso, a complexidade é grande, mas a garantia de que se você faz muitas destas operações, a quantidade média de trabalho que você fizer vai ser melhor do que de pior caso.Por exemplo, você pode ter uma estrutura de dados que normalmente leva constante O(1) em tempo.No entanto, ocasionalmente, ele vai 'soluço' e tomar O(N) tempo para uma pessoa aleatória operação, porque talvez seja necessário fazer alguns contabilidade ou coleta de lixo, ou algo assim...mas você promete que se ele faz soluço, não soluçar novamente para N mais operações.O pior caso, o custo é ainda O(N) por operação, mas o custo amortizado ao longo de muitos é executado é O(N)/N = O(1) por operação.Porque as grandes operações são suficientemente raro, a enorme quantidade de trabalhos ocasionais podem ser considerados para se misturar com o resto do trabalho como um fator constante.Dizemos que o trabalho é "amortizado" mais de um número suficientemente grande de chamadas que ele desaparece assintoticamente.

A analogia para amortizado análise:

Você dirige um carro.Ocasionalmente, você precisa passar de 10 minutos vai a estação de gás e, em seguida, passar de 1 minuto e voltar a encher o tanque com gás.Se você fez isso toda vez que você foi em qualquer lugar, com seu carro (passar de 10 minutos de condução para o posto de gasolina, passar alguns segundos o preenchimento de um fração de um litro), seria muito ineficiente.Mas, se você preencher até o tanque de uma vez a cada poucos dias, 11 minutos gastos de condução para o posto de gasolina é "amortizado" mais de um número suficientemente grande de viagens, que você pode ignorá-la e fingir que todas as suas viagens foram, talvez 5% a mais.

Comparação entre a média do caso, e amortizados de pior caso:

Média-caso:Podemos fazer algumas suposições sobre a nossa insumos;i.e.se a nossa insumos têm diferentes probabilidades, então, o nosso saídas/tempos de execução têm diferentes probabilidades (que tomamos a média).Geralmente assumimos que nossos insumos são todos igualmente provável (uniforme de probabilidade), mas se o mundo real entradas não se encaixam em nossos pressupostos da "média de entrada", a saída média/tempo de execução de cálculos pode ser sem sentido.Se você antecipar uniformemente entradas aleatórias, porém, isso é útil pensar!
Amortizado pior caso:Se você usar um amortizado pior-caso estrutura de dados, o desempenho é garantido de ser amortizado pior...eventualmente, (mesmo se as entradas são escolhidos por um demônio que sabe de tudo e é tentando que se dane a mais).Geralmente usamos isso para analisar algoritmos que podem ser muito "instável" de desempenho com o inesperado grandes soluços, mas ao longo do tempo um desempenho tão bom como outros algoritmos.(No entanto, a menos que sua estrutura de dados tem limites para muito excelente trabalho que está disposto a adiar um mal invasor poderia talvez forçar você a pegar a quantidade máxima de procrastinated de trabalho, todos-em-uma vez.

Porém, se você estiver razoavelmente preocupado cerca de um invasor, mas há muitos outros algoritmos vetores de ataque para se preocupar além de amortização e média-caso).

Tanto a média de caso e amortização são ferramentas incrivelmente úteis para pensar e desenhar com a escala em mente.

(Ver Diferença entre a média do caso, e amortizados de análise se estiver interessado neste subtópico.)

Multidimensional grande-O

A maior parte do tempo, as pessoas não percebem que há mais do que uma variável no trabalho.Por exemplo, em uma seqüência de caracteres de pesquisa de algoritmo, o algoritmo pode levar tempo O([length of text] + [length of query]), i.é.é lineares em duas variáveis como O(N+M).Outros mais ingênuo algoritmos podem ser O([length of text]*[length of query]) ou O(N*M).Ignorando várias variáveis é uma das mais comuns descuidos eu vejo no algoritmo de análise, e pode desvantagem quando a concepção de um algoritmo.

Toda a história

Tenha em mente que o big-S não é a história toda.Você pode reduzir drasticamente a velocidade de alguns algoritmos usando cache, tornando-cache-se alheado, evitando gargalos ao trabalhar com a memória RAM em vez de disco, usando de paralelização, ou fazer o trabalho à frente do tempo, estas técnicas são muitas vezes independente do fim-de-crescimento "big-O" notação, embora muitas vezes você vai ver o número de núcleos na big O notation de algoritmos paralelos.

Também tenha em mente que, devido às escondidas restrições de seu programa, você não pode realmente se importa com o comportamento assintótico.Você pode estar trabalhando com um número limitado de valores, por exemplo:

Se você está de classificação de algo como 5 elementos, você não deseja usar o speedy O(N log(N)) quicksort;você deseja usar a inserção de classificação, que acontece funcionar bem em pequenas entradas.Nessas situações, muitas vezes vem até em dividir-e-conquistar algoritmos, onde você dividir o problema em menores e menores subproblems, tais como recursiva de classificação, transformação rápida de Fourier, ou a multiplicação de matrizes.
Se alguns valores são efetivamente limitada, devido a algumas oculto fato (por exemplo,o ser humano médio nome é baixinho, limitada, talvez, 40 cartas, e humanos, a idade é baixinho, limitada a cerca de 150).Você também pode impor limites sobre a sua entrada para efetivamente fazer termos constantes.

Na prática, mesmo entre os algoritmos que têm o mesmo ou semelhante assintótica de desempenho, o seu mérito relativo, na verdade, pode ser conduzido por outras coisas, tais como:outros fatores de desempenho (quicksort e mergesort são ambos O(N log(N)), mas o quicksort tira vantagem de caches da CPU);não-considerações sobre o desempenho, como a facilidade de implementação;se uma biblioteca está disponível, e como respeitável e mantida a biblioteca.

Os programas também irá executar mais lentamente em um 500MHz computador vs 2GHz computador.Nós realmente não considere isso como parte do recurso de limites, porque pensamos que o dimensionamento em termos de recursos de máquina (por exemplo,por ciclo de clock), e não por real segundo.No entanto, há outras coisas semelhantes que podem 'secretamente' afetar o desempenho, como por exemplo, se você estiver executando sob emulação, ou se o compilador de código otimizado ou não.Estes podem fazer algumas operações básicas levar mais tempo (até mesmo em relação ao outro), ou mesmo acelerar ou reduzir a velocidade de algumas operações assintoticamente (mesmo em relação ao outro).O efeito pode ser grande ou pequena entre diferentes implementação e/ou meio ambiente.Fazer você mudar o idioma, ou máquinas de ganhar pouco mais de trabalho?Que depende de uma centena de outros motivos (necessidade, habilidades, colegas de trabalho, a produtividade do programador, o valor monetário de seu tempo, a familiaridade, soluções alternativas, por que não assembly ou GPU, etc...), o que pode ser mais importante do que o desempenho.

As questões acima, como linguagem de programação, quase nunca são considerados como parte do fator constante (nem deve ser);ainda deve-se ter consciência deles, porque às vezes (embora raramente) que podem afetar as coisas.Por exemplo, no cpython, o nativo fila de prioridade de implementação é assintoticamente não-ideal (O(log(N)) em vez de O(1) para a sua opção de inserção ou de encontrar-min);você usar uma outra implementação?Provavelmente não, já que o C implementação é provavelmente mais rápido, e provavelmente existem outros problemas semelhantes em outros lugares.Existem compromissos;às vezes, eles são importantes e, por vezes, não.

(editar:O "plain English" explicação termina aqui.)

Matemática anexos

Para completar, a definição precisa do big O notation é como segue: f(x) ∈ O(g(x)) significa que "o f é assintoticamente superior delimitada pelo const*g":ignorando tudo abaixo alguns finito valor de x, existe uma constante tal que |f(x)| ≤ const * |g(x)|.(Os outros símbolos são como segue:assim como O significa ≤, Ω significa ≥.Existem minúsculas variantes: o significa <e ω significa >.) f(x) ∈ Ɵ(g(x)) significa tanto f(x) ∈ O(g(x)) e f(x) ∈ Ω(g(x)) (superior e inferior delimitada por g):existe algumas constantes tais que f sempre foi a "banda" entre const1*g(x) e const2*g(x).Ele é o mais forte assintótica declaração que você pode fazer e equivalente a ==.(Desculpe, eu eleitos para atrasar a menção de que o valor absoluto símbolos até agora, por uma questão de clareza;especialmente porque eu nunca vi valores negativos surgem em um computador de ciência de contexto.)

Muitas vezes as pessoas vão usar = O(...), que é, talvez, o mais correto", comp, sci' notação, e inteiramente legítimo do uso;"f = O(...)" ler "f é a ordem .../ f xxx-delimitada por ..." e é entendida como a "f é alguma expressão cujo asymptotics são ...".Eu fui ensinado a usar o mais rigoroso ∈ O(...). ∈ significa "é um elemento de" (lida, ainda, como antes). O(N²) é, na verdade, um classe de equivalência, ou seja, é um conjunto de coisas que nós consideramos ser o mesmo.Neste caso em 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 assim é um conjunto.O = a notação pode ser o mais comum e é usado até mesmo em jornais de renome mundial, cientistas da computação.Além disso, é muitas vezes o caso de que, num ambiente informal, as pessoas vão dizer O(...) quando eles significam Ɵ(...);isso é tecnicamente verdade desde que o conjunto de coisas Ɵ(exactlyThis) é um subconjunto de O(noGreaterThanThis)...e é mais fácil de digitar.;-)

Editar: Nota rápida, isso é quase certamente confuso Grande notação o (que é um limite superior) com a notação teta (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 concluí -lo?

Obviamente, isso está usando apenas "tamanho" como entrada e "tempo gasto" como a saída - a mesma ideia se aplica se você quiser falar sobre o uso da memória etc.

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

Usando uma linha de lavagem do lado de fora: supondo que você tenha um quintal infinitamente grande, lavando secos no tempo (1). Por mais que você tenha, ele terá o mesmo sol e ar fresco, para que o tamanho não afete o tempo de secagem.
Usando um secador: você coloca 10 camisas em cada carga e eles são feitos uma hora depois. (Ignore os números reais aqui - eles são irrelevantes.) Portanto, a secagem de 50 camisas leva cerca de 5 vezes mais que a secagem de 10 camisas.
Colocando tudo em um armário em exibição: se colocarmos tudo em uma pilha grande e deixar o calor geral fazer isso, levará muito tempo para as camisas do meio secarem. 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 "Big O" é que isso não Diga qual algoritmo será mais rápido para um determinado tamanho. Pegue uma hashtable (chave de string, valor inteiro) versus uma matriz de pares (string, número inteiro). É mais rápido encontrar uma chave na hashtable ou um elemento na matriz, com base em uma string? (isto é, para a matriz, "Encontre o primeiro elemento em que a parte da string corresponde à chave fornecida.") Hashtables geralmente são amortizados (~ = "em média") o (1) - uma vez que eles são configurados, deve aceitar O mesmo tempo para encontrar uma entrada em uma tabela de 100 entradas, como em uma tabela de 1.000.000 de entrada. 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 olhar para metade das entradas.

Isso torna um hashtable mais rápido que uma matriz para pesquisas? Não necessariamente. Se você tiver uma coleção muito pequena de entradas, uma matriz pode muito bem ser mais rápida - você poderá verificar todas as seqüências de strings no tempo necessário para calcular apenas o código de hash daquele que você está olhando. À medida que o conjunto de dados aumenta, no entanto, a hashtable acabará por superar a matriz.

Big O descreve um limite superior para o 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 dobra
Sobre²): Se o tamanho da entrada dobrar os quadruplos de tempo de execução
O (log n): se o tamanho da entrada dobrar o tempo de execução aumenta em um
O (2ⁿ): Se o tamanho da entrada aumentar em um, o tempo de execução dobra

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

A grande notação O é mais comumente usada pelos programadores como uma medida aproximada de quanto tempo um cálculo (algoritmo) levará para concluir expressos em função do tamanho do conjunto de entrada.

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

Mais precisamente Grande notação o é usado 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 cairá em um dos seguintes casos:

O (1) - O tempo para concluir é o mesmo, independentemente do tamanho do conjunto de entrada. Um exemplo é acessar um elemento de matriz por índice.
O (log n) - O tempo para concluir aumenta aproximadamente de acordo com o log2 (n). Por exemplo, 1024 itens leva aproximadamente o dobro que 32 itens, porque log2 (1024) = 10 e log2 (32) = 5. Um exemplo é encontrar um item em um Árvore de pesquisa binária (BST).
SOBRE) - Hora de concluir que escala linearmente com o tamanho do conjunto de entrada. Em outras palavras, se você dobrar o número de itens no conjunto de entrada, o algoritmo leva aproximadamente duas vezes mais. Um exemplo está contando o número de itens em uma lista vinculada.
O (n log n) - Tempo para concluir aumentos pelo número de itens vezes o resultado do log2 (n). Um exemplo disso é Classificação da pilha e ordenação rápida.
O (n^2) - O tempo para concluir é aproximadamente igual ao quadrado do número de itens. Um exemplo disso é Tipo de bolha.
SOBRE!) - Hora de concluir é o fatorial do conjunto de entrada. Um exemplo disso é o Solução de força de vendedor ambulante viajante.

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 para o infinito. Isso significa que as constantes que são 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 é preciso para executar meu código?".

Você pode ver frequentemente o (n), o (n²), O (nLogn) e assim por diante, todas essas são apenas maneiras de mostrar; Como um algoritmo muda?

O (n) significa grande 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ê teria que olhar 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 levou tanto tempo quanto itens na lista; portanto, para ser genérico, dizemos "Oh, ei, n é uma quantidade justa 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 simples, o mais simples dos algoritmos de classificação; Bubblesort. Esse algoritmo precisa procurar por toda a lista, para cada item.

Minha lista

O fluxo aqui seria:

Compare 1 e 6, o que é maior? Ok 6 está na posição certa, avançando!
Compare 6 e 3, oh, 3 é menos! Vamos mover isso, ok a lista mudou, precisamos começar do começo agora!

Isso é o n² Porque você precisa olhar para todos os itens da lista, existem itens "n". Para cada item, você olha para todos os itens mais uma vez, para comparar, isso também é "n"; portanto, para cada item, você olha "n" vezes que significa n*n = n²

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

Mas lembre -se, o Big O é apenas uma maneira de se expandir no modo 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 conta sobre um determinado algoritmo. Ele corta para o osso e fornece apenas informações sobre a natureza de escala de um algoritmo, especificamente como o uso do recurso (tempo de pensamento ou memória) de uma escala de algoritmo em resposta ao "tamanho da entrada".

Considere a diferença entre um motor a vapor e um foguete. Eles não são apenas variedades diferentes da mesma coisa (como, digamos, um motor Prius vs. um motor Lamborghini), mas são dramaticamente tipos 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 vapor poderá atingir as velocidades de um veículo de lançamento orbital. Isso ocorre porque esses sistemas têm características de escala diferentes com relação à relação de combustível necessária ("uso de recursos") para atingir uma determinada velocidade ("tamanho da entrada").

Por que isso é tão importante? Porque o software lida com problemas que podem diferir em tamanho por fatores até um trilhão. Considere isso por um momento. A proporção entre a velocidade necessária para viajar para a lua e a velocidade de caminhada humana é inferior a 10.000: 1, e isso é absolutamente pequeno em comparação com o alcance do software de tamanhos de entrada pode enfrentar. E como o software pode enfrentar um alcance astronômico nos tamanhos de entrada, há o potencial da grande complexidade O de um algoritmo, sua natureza de escala fundamental, para superar qualquer detalhe da implementação.

Considere o exemplo de classificação canônica. Bubble-sort é O (n²) enquanto a mesclagem é O (n log n). Digamos que você tenha dois aplicativos de classificação, o aplicativo A, que usa o Bubble-derrub e o aplicativo B, que usa Merge-Sort, 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 você prefere o aplicativo A, pois é muito mais rápido nesses tamanhos de entrada. No entanto, se você achar que pode ter que classificar dez milhões de itens, o que você esperaria é que o aplicativo B acaba sendo milhares de vezes mais rápido que o aplicativo A neste caso, inteiramente devido à maneira como cada algoritmo escala.

Aqui é o inglês simples bestiário que tendem a usar, ao explicar as variedades comuns de Grande-O

Em todos os casos, prefira os algoritmos mais acima da lista para aqueles inferior na lista.No entanto, o custo de se mudar para um mais caro complexidade classe varia significativamente.

O(1):

Nenhum crescimento.Independentemente de quão grande como o problema é, você pode resolvê-lo com a mesma quantidade de tempo.Isso é algo análogo à radiodifusão, onde leva a mesma quantidade de energia para transmissão através de uma determinada distância, independentemente do número de pessoas que se encontram dentro do intervalo de difusão.

O(log n):

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

O(n):

O custo de resolver o problema é proporcional ao tamanho do problema.Se o seu problema dobra de tamanho, o custo da solução duplos.Desde que a maioria dos problemas têm de ser digitalizados para o computador, de alguma forma, como a entrada de dados, leituras de disco ou tráfego de rede, isto é, geralmente, um preço acessível fator de escala.

O(n registo n):

Esta complexidade é muito semelhante ao O(n).Para todos os fins práticos, os dois são equivalentes.Este nível de complexidade geralmente ainda ser considerada escalável.Alterando alguns pressupostos O(n registo n) algoritmos podem ser transformados em O(n) algoritmos.Por exemplo, limitando o tamanho das chaves reduz a classificação de O(n registo n) para O(n).

O(n²):

Cresce como uma praça, onde n é o comprimento do lado de um quadrado.Essa é a mesma taxa de crescimento, como o "efeito de rede", onde todos em uma rede pode saber a todos os outros na rede.O crescimento é caro.A maioria das soluções escaláveis, não é possível usar algoritmos com este nível de complexidade, sem fazer significativo de ginástica.Geralmente, isto se aplica a todos os outros polinˆ omio de complexidades - O(n^k) - bem.

O(2ⁿ):

Não escala.Você não tem esperança de resolver qualquer não-trivial de tamanho problema.Útil para saber o que evitar, e de especialistas para encontrar algoritmos aproximados, que são, na 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 for O (n²) então o tempo/espaço aumenta à taxa de sua entrada ao quadrado.

e assim por diante.

É muito difícil medir a velocidade de programas de software, e quando tentamos, as respostas podem ser muito complexo e cheio de exceções e casos especiais.Este é um grande problema, pois todos os exceções e casos especiais são distração e são úteis quando queremos comparar dois programas diferentes um com o outro para descobrir qual é o "mais rápido".

Como resultado de tudo isso é inútil complexidade, as pessoas tentam descrever a velocidade de programas de software utilizando o menor e menos complexo (matemática) expressões possíveis.Essas expressões são muito, muito bruta de aproximações:Apesar de, com um pouco de sorte, que vai captar a "essência" da existência de um componente de software é rápido ou lento.

Porque eles são aproximações, usamos a letra "O" (Oh Grande) na expressão, como uma convenção de sinais para o leitor de que estamos fazendo uma simplificação grosseira.(E para se certificar de que ninguém erroneamente pensa que a expressão é, de qualquer forma precisa).

Se você ler o "Ah" como significando "no fim de" ou "aproximadamente" você não vai ir muito longe errado.(Eu acho que a escolha do Big-Oh, poderia ter sido uma tentativa de humor).

A única coisa que estes "Big-Oh" expressões tentar fazer é descrever o quanto o software diminui à medida que se aumenta a quantidade de dados que o software tem para o processo.Se dobrarmos a quantidade de dados que precisa ser processado, o software necessário o dobro do tempo para concluir o seu trabalho?Dez vezes mais tempo?Na prática, há um número muito limitado de big-Oh expressões que você vai encontrar e precisa de se preocupar com:

O bom:

O(1) Constante:O programa leva o mesmo tempo para ser executado, não importa o quão grande é a entrada.
O(log n) Logarítmica:O programa de tempo de execução aumenta lentamente, mesmo com o grande aumento no tamanho da entrada.

O bad:

O(n) Linear:O programa de tempo de execução aumenta proporcionalmente ao tamanho da entrada.
O(n^k) Polinômio:- Tempo de processamento cresce mais rápido e mais rápido - como um polinˆ omio de função - como o tamanho da entrada aumenta.

...e o feio:

O(k^n) Exponencial O programa de tempo de execução aumenta muito rapidamente com o mesmo moderado aumenta o tamanho do problema - ele só é prático para o processo de pequenos conjuntos de dados com algoritmos exponenciais.
O(n!) Factorial O programa de tempo de execução, será mais do que você pode dar ao luxo de esperar por qualquer coisa, mas muito menor e mais trivial-parecendo conjuntos de dados.

O que é uma explicação inglesa clara de Big O? Com o mínimo de definição formal possível e a matemática simples.

Uma explicação inglesa clara do Precisar Para notação Big-O:

Quando programamos, estamos tentando resolver um problema. O que codificamos é chamado de algoritmo. O Big O notação nos permite comparar o pior desempenho de casos de nossos algoritmos de maneira padronizada. As especificações de hardware variam ao longo do tempo e as melhorias no hardware podem reduzir o tempo que leva para executar um algoritmos. Mas a substituição do hardware não significa que nosso algoritmo seja melhor ou melhorado 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 grande notação O.

Uma explicação inglesa clara de o que Grande notação O é:

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 n. Com base nisso, consideramos a pior análise de caso, ou um limite superior do tempo de execução como n fique cada vez maior. Devemos estar cientes do que n é, porque muitas das grandes anotações O referenciam isso.

Uma resposta simples simples pode ser:

Big O representa o pior tempo/espaço possível para esse algoritmo. O algoritmo nunca terá 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, é taxa de aumento de recursos consumidos por programa, WRT-Instance-Size

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

Diga que o problema é "Encontre a soma",

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

      return sum;
}

Problema-Instance = {5,10,15} ==> Problema-Instance-Size = 3, iterações em loop = 3

Problema-Instance = {5,10,15,20,25} ==> Problema-instance-size = 5 iterações em loop = 5

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

Diga que o problema é "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;
      }
    }

Problema-Instance = {5,10,15} ==> Problema-Instance-Size = 3, Total-AERveations = 3*3 = 9

Problema-Instance = {5,10,15,20,25} ==> Problema-Instance-Size = 5, Total-Aretações = 5*5 = 25

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

Big O notation é uma maneira de descrever o limite superior de um algoritmo em termos de espaço ou de tempo de execução.O n é o número de elementos em a o problema (que eu.e o tamanho de uma matriz, número de nós em uma árvore, etc.) Estamos interessados em descrever o tempo de execução a medida que n se torna grande.

Quando dizemos que alguns algoritmo é O(f(n)), estamos dizendo que o tempo de execução (ou espaço necessário) por que o algoritmo é sempre mais baixo do que alguns constante vezes f(n).

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

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

"O que é uma explicação inglesa clara de Big O? Com o mínimo de 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.

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

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

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

Praticamente falando, a análise Big O é Tão útil e importante Porque Big O coloca o foco diretamente no algoritmo ter complexidade e completamente ignora Qualquer coisa que seja apenas uma proporcionalidade constante - como um mecanismo de JavaScript, a velocidade de uma CPU, sua conexão com a Internet e todas essas coisas que se tornam rapidamente tão ridicularizadas como um modelo T. Big O se concentra no desempenho apenas na maneira que importa igualmente para as pessoas que vivem no presente ou no futuro.
Grande notação O também ilumina diretamente o princípio mais importante da programação/engenharia de computadores, o fato que inspira todos os bons programadores a continuar pensando e sonhando: a única maneira de alcançar resultados além da lenta marcha da tecnologia é inventar um algoritmo melhor.

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:

Este algoritmo pesquisa uma lista, item por item, procurando uma chave,
Iterando em cada item da lista, se for a chave, retorne true,
Se o loop terminou sem encontrar a chave, retorne falsa.

A notação big-o representa o limite superior na complexidade (tempo, espaço, ..)

Para encontrar o Big-O na complexidade do tempo:

Calcule quanto tempo (em relação ao tamanho da entrada) o pior caso leva:
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 melhor caso:

Melhor caso: a chave é o primeiro item.
Tempo (melhor caso) = 4
Tempo: ω (4) = O (1) ~ Instant Constant

Grande o

f(x) = O (g(x)) Quando x vai para um (por exemplo, a = +∞) significa que há uma função k de tal modo que:

f(x) = k(x)g(x)
K é delimitado em algum bairro de A (se a = +∞, isso significa que existem números n e m de modo 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 um bairro de A, f se decompõe no produto de g e alguma função limitada.

Pequeno o

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

f(x) = O (g(x)) Quando x vai para um meio significa que há uma função k de tal forma que:

f(x) = k(x)g(x)
k(x) vai para 0 quando x vai para a.

Exemplos

sin x = o (x) quando x → 0.
sin 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 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 → +∞
Sobre²)Sobre³) = O (n⁵) quando n → +∞

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

O Big O notaçã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 diferentes máquinas 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 de 4,5 GHz octo, posso estar executando um sistema de 15 anos de idade, 800 MHz, que pode levar mais tempo, independentemente do algoritmo. Portanto, em vez de especificar a rapidez com que um algoritmo é executado em termos de tempo, dizemos a rapidez com que ele é executado em termos de número de parâmetros de entrada ou "n". Ao descrever 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 se estou contribuindo ainda mais para o assunto, mas ainda pensei em compartilhar: uma vez encontrei esta postagem do blog ter algumas explicações e exemplos bastante úteis (embora muito básicos) no Big O:

Por meio de exemplos, isso ajudou a colocar o básico nu no meu crânio de tartaruga, então acho que é uma leitura de 10 minutos de descendência para que você vá na direção certa.

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

Então, para falar de Big 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 palavras com um som. Eles são pequenos. Tenho certeza de que você saberá todas as palavras que usaremos!

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

Eu não gosto de ir trabalhar. Não gosto de passar o tempo no trabalho. Se eu tivesse o meu caminho, gostaria apenas de tocar 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. O mais perto de nenhum trabalho possível. Então eu vou jogar!

Então, aqui estão as grandes notícias: o Big O pode me ajudar a não trabalhar! Eu posso jogar mais do tempo, se souber Big O. Menos trabalho, mais jogo! Isso é o que Big O me ajuda a fazer.

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

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

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

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

Bem vamos ver. Devo adicionar um e dois, e depois adicionar isso a três e depois adicionar isso a quatro ... ao mesmo tempo, conto seis acrescentam. Eu tenho que fazer seis adição para resolver isso.

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

O Big O diz: devemos fazer seis contribui para resolver isso. Um add, para cada coisa de um a seis. Seis pequenos pedaços de trabalho ... Cada pedaço de trabalho é um add.

Bem, não farei o trabalho para adicioná -los agora. Mas eu sei o quão difícil seria. Seria seis acréscimos.

Oh não, agora 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. Adicionar de um a dez ... bem ... isso seria ainda mais difícil!

Quão mais difícil seria? Quanto mais trabalho eu teria que fazer? Eu preciso de mais ou menos etapas?

Bem, acho que teria que fazer dez acrescenta ... uma para cada coisa de um a dez. Dez é superior a 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 como pode ser difícil adicionar isso. E, espero, jogar o mais rápido possível.

Para adicionar de um a seis, isso é um 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 Big O, ele pode nos ajudar a escolher o trabalho que não é tão duro!

Agora devemos fazer um novo trabalho. Oh não. Eu não gosto disso.

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

Espere! O que é n? Eu perdi isso? Como posso adicionar de um a n se você não me disser o que é n?

Bem, eu não sei o que é n. Eu não fui informado. Você era? Não? Ah bem. Portanto, 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 n. Teríamos que adicionar n coisas, certo? É claro!

Agora, aqui vem Big O, e ele nos dirá como esse trabalho é difícil. 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 o quão difícil é fazer algum tipo de trabalho.

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

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

Uh oh, 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 confusos: sete, quatro, dois, seis ... não são retos. 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, emparelhar por par, através do baralho, do primeiro ao último. Se a primeira carta em um par for grande e a próxima carta nesse par é pequena, eu os troco. Caso contrário, eu vou para o próximo par, e assim por diante e assim por diante ... e logo, o baralho está pronto.

Quando o baralho está pronto, pergunto: trocei as cartas nesse passe? Nesse caso, devo fazer tudo mais uma vez, de cima.

Em algum momento, em algum momento, não haverá swaps, e nosso tipo de baralho seria feito. Muito trabalho!

Bem, quanto trabalho isso seria, 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 passar por todo o convés até dez vezes, com até dez trocas de cartas de cada vez pelo convés.

Big O, me ajude!

O Big O entra e diz: Para um baralho de N Cards, classificá -lo dessa maneira será feito no tempo O (n quadrado).

Por que ele diz n quadrado?

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

Agora, quando Big O diz que o trabalho (n quadrado), ele não significa que n quadrado acrescenta, no nariz. Pode ser um pouco menor, para alguns casos. Mas, na pior das hipóteses, estará perto de N Squared Step of Work para classificar o baralho.

Agora é aqui que Big O é nosso amigo.

Big O aponta o seguinte: à medida que N fica grande, quando classificamos cartões, o trabalho fica muito mais difícil do que o antigo trabalho de justiça. 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 Big n, n quadrado é mais grande que n.

Big O nos diz que classificar as coisas é mais difícil do que adicionar coisas. O (n quadrado) é mais que O (n) para Big n. Isso significa: se n ficar muito grande, para classificar um baralho 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 duro é o trabalho.

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

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

Sim, há uma maneira mais rápida! Leva algum tempo para aprender, mas funciona ... e funciona muito rápido. Você também pode tentar, mas reserve um tempo a cada passo e não perca seu lugar.

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

Um: eu 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 baralho em que trabalhamos agora" é o baralho inteiro, é claro.)

Dois: eu espalhei o baralho naquela carta que você escolheu. O que é essa divisão; Como faço para espalhar? Bem, eu vou do cartão de partida para baixo, um por um, e procuro um cartão mais alto que o cartão Splay.

Três: Eu vou do cartão final e procuro um cartão mais baixo que o cartão Splay.

Depois de encontrar esses dois cartões, trocei -os e procuro mais cartões para trocar. Isto é, eu volto para a etapa dois e divido no cartão que você escolheu um pouco mais.

Em algum momento, esse loop (de dois a três) terminará. Termina quando as duas metades desta pesquisa se encontram no cartão Splay. Então, acabamos de espalhar o baralho com a carta que você escolheu na etapa um. Agora, todas as cartas próximas ao início são mais baixas que o cartão Splay; E os cartões próximos ao final são mais altos que o cartão Splay. Truque legal!

Quatro (e essa é a parte divertida): agora tenho dois pequenos decks, um mais baixo que o cartão Splay e mais um alto. Agora eu vou para a etapa um, em cada pequeno deck! Ou seja, começo a partir da etapa um no primeiro pequeno deck e, quando esse trabalho é feito, começo a partir da etapa um no próximo deck pequeno.

Eu quebro o convés em partes e classifico cada parte, mais pequena e 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 é lento. É muito menos trabalho do que a primeira maneira de classificar as coisas!

Como é chamado esse tipo? É chamado de classificação rápida! Esse tipo foi feito por um homem chamado CARE HOARE E ele chamou de classificação rápida. Agora, a classificação rápida é usada o tempo todo!

A classificação rápida quebra grandes decks em pequenos. Ou seja, isso interrompe grandes tarefas em pequenas.

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

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

É mais ou menos rápido que o primeiro tipo? 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 é menos que n quadrado, para Big n, certo? Bem, é assim que sabemos que o tipo rápido é rápido!

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

Por que escolho uma classificação rápida? Eu não gosto de trabalhar, é claro! Eu quero o trabalho feito assim que puder fazer isso.

Como eu sei que o rastreio rápido é menos trabalho? Eu sei que o (n log n) é menor que o (n quadrado). Os O's são mais pequenos, então o tipo rápido é menos trabalho!

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

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

Agora esse trabalho está pronto, vamos jogar!

1]: Existe uma maneira de trapacear e adicionar todas as coisas de uma a N, todas ao mesmo tempo. Algum garoto chamado Gauss descobriu isso quando tinha oito anos. Eu não sou tão inteligente, porém, então Não me pergunte como ele fez isso.

Suponha que estamos falando de um algoritmo UMA, 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ê é azar ao executar um, pode levar as operações x (n) para concluir.

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

Comparando -os ao falar sobre UMA e outros algoritmos, é fácil classificar os algoritmos de acordo com o número de operações que eles poderia (no pior caso) exigem concluir.

Em geral, nosso objetivo será encontrar ou estruturar um algoritmo UMA de tal maneira que terá uma função X(n) Isso retorna o mais baixo possível.

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

statement;

É constante. O tempo de execução da declaração não mudará 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 mesmo acontece com o tempo de execução.

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 duplas, 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 pela metade com 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 grandes medidas de O, como raiz cúbica, exponencial e quadrada, mas não são tão comuns. Grande notação O é descrita como O () onde está a medida. O algoritmo do Quicksort seria descrito como O (n * log (n)).

NOTA: Nada disso levou em consideração as melhores, médias e piores medidas de caso. Cada um teria sua própria notação OS. Observe também que essa é uma explicação muito simplista. Big O é o mais comum, mas também é mais complexo que eu mostrei. Existem também outras anotações, como Big Omega, Little O e Big Theta. Você provavelmente não os encontrará fora de um curso de análise de algoritmo.

Veja mais em: Aqui

Digamos que você encomende Harry Potter: coleção completa de 8 filmes [Blu-ray] da Amazon e faça o download da mesma coleção de filmes on-line ao mesmo tempo. Você deseja testar qual método é mais rápido. A entrega leva quase um dia para chegar e o download foi concluído cerca de 30 minutos antes. Excelente! Então é uma corrida apertada.

E se eu pedir vários filmes de Blu-ray, como o Senhor dos Anéis, Twilight, The Dark Knight Trilogy, etc. e baixar todos os filmes on-line ao mesmo tempo? Desta vez, a entrega ainda leva um dia para ser concluída, mas o download on -line leva 3 dias para terminar. Para compras on -line, o número de item adquirido (entrada) não afeta o tempo de entrega. A saída é constante. Nós chamamos isso O (1).

Para download on -line, o tempo de download é diretamente proporcional aos tamanhos dos arquivos do filme (entrada). Nós chamamos isso Sobre).

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

Observação: Grande notação o representa o pior cenário de um algoritmo. Vamos supor que O (1) e Sobre) são os pior cenários do exemplo acima.

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

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

Big O notação diz o custo de resolver um problema infinitamente grande.

E além disso

Fatores constantes são insignificantes

Se você atualizar para um computador que pode executar seu algoritmo duas vezes mais rápido, o Big O notação não notará isso. As melhorias constantes de 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" do 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 o infinito, a grande notação O é aproximadamente o custo de resolver seu problema.

Se o exposto acima não faz sentido, você não terá uma noção intuitiva compatível de infinito em sua cabeça, e provavelmente deve desconsiderar todas as opções acima; A única maneira de conhecer essas idéias rigorosas ou explicá -las se elas ainda não forem intuitivamente úteis, é primeiro ensinar a você uma grande notação ou algo semelhante. (Embora, uma vez que você entenda bem o Big O notação no futuro, pode valer a pena revisitar essas idéias)

O que é uma explicação inglesa clara da notação "Big O"?

Nota muito rápida:

O O em "Big O" refere -se a "Ordem" (ou precisamente "Ordem de")
Então você pode ter sua idéia literalmente de que ela é usada para pedir algo para compará -los.

"Big O" faz duas coisas:
1. Estima quantas etapas do método seu computador se aplica para realizar uma tarefa.
2. Facilitar o processo para comparar com os outros para determinar se é bom ou não?
3. "Big O 'alcança os dois acima com padronização Notations.
Existem sete anotações mais usadas
1. O (1), significa que seu computador faz uma tarefa realizada com 1 Etapa, é excelente, pedido nº 1
2. O (logn), significa que seu computador completa uma tarefa com logN Etapas, é bom, ordenado no.2
3. O (n), termine uma tarefa com N Etapas, é justo, Ordem No.3
4. O (nLogn), encerra uma tarefa com O(NlogN) Etapas, não é bom, pedido nº 4
5. O (n^2), faça uma tarefa com N^2 Etapas, é ruim, pedido nº 5
6. O (2^n), faça uma tarefa com 2^N Passos, é horrível, Ordem No.6
7. O (n!), Faça uma tarefa com N! Etapas, é terrível, ordem nº 7

Suponha que você obtenha notação O(N^2), não apenas você está claro que o método toma n*n etapas para realizar uma tarefa, você também vê que não é bom como O(NlogN) de sua classificação.

Observe o pedido no final da linha, apenas para sua melhor compreensão. Há mais de 7 notações se todas as possibilidades consideradas.

No CS, o conjunto de etapas para realizar uma tarefa é chamado de algoritmos.
Na terminologia, a grande notação 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 da parte superior.
Você pode se referir a Big-ω (Big-Omega) para o melhor caso.

Notação Big-ω (Big-Omega) (Artigo) | Academia Khan

Resumo
"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 olhar para ele (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, é considerado um grande O de n.

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

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 em função de n

c = uma constante

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

Então, no que diz respeito ao grande 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 como n se aproxima do infinito, t de n, é menor ou igual a C vezes f de n.

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

T(n)∈O(n)

Isso é lido como t de n está em grande o de n.

De volta ao inglês

Com base na definição matemática acima, se você diz que seu algoritmo é um grande 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 grande de n, também é automaticamente o grande O do N Square.

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

Verificar isto Fora um tutorial em vídeo sobre o Big O da UC Berkley. É realmente um conceito simples. Se você ouvir o professor Shewchuck (também conhecido como professor de nível de Deus) explicando, você dirá "Oh, isso é tudo!".

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

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

Grande notação 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 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 pessoa que leia pérolas de programação ou qualquer outro livro de ciência da computação e não tenha aterramento em matemática terá atingido uma parede quando chegarem aos capítulos que mencionam O (n log n) ou outra sintaxe aparentemente louca. Espero que este artigo o ajude a entender o básico do grande O e dos logaritmos.

Como programador primeiro e um segundo matemático (ou talvez terceiro ou quarto), encontrei a melhor maneira de entender o Big O minuciosamente era produzir alguns exemplos no 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 ao mesmo tempo (ou espaço), independentemente do tamanho do conjunto de dados de entrada.
bool IsFirstElementNull(IList<string> elements) {
    return elements[0] == null; } O(N)
SOBRE)

O (n) descreve um algoritmo cujo desempenho crescerá linearmente e em proporção direta ao tamanho do conjunto de dados de entrada. O exemplo abaixo também demonstra o tamanho do Favors o pior cenário de desempenho; Uma string correspondente pode ser encontrada durante qualquer iteração do loop for e a função retornaria mais cedo, mas a grande notação 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;
} 
SOBRE²)

SOBRE²) representa um algoritmo cujo desempenho é diretamente proporcional ao quadrado do tamanho do conjunto de dados de entrada. Isso é comum com algoritmos que envolvem iterações aninhadas sobre o conjunto de dados. Iterações aninhadas mais profundas resultarão em O (n³), SOBRE⁴) 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 adição no conjunto de dados de entrada. A curva de crescimento de um O (2^N) A função é exponencial - começando muito superficial e depois subindo meteoricamente. Um exemplo de um (2^N) Função é 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 complicados de explicar, então vou usar um exemplo comum:

A pesquisa binária é uma técnica usada para pesquisar conjuntos de dados classificados. Ele funciona selecionando o elemento médio do conjunto de dados, essencialmente a mediana e o compara com um valor alvo. Se os valores corresponderem, ele retornará o sucesso. Se o valor alvo for maior que o valor do elemento da sonda, ele levará 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 da sonda, ele executará a operação contra a metade inferior. Ele continuará a reduzir pela metade o conjunto de dados com cada iteração até que o valor seja encontrado ou até que não possa mais dividir o conjunto de dados.

Esse tipo de algoritmo é descrito como O (log n). A metade iterativa da metade 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 que contém 10 itens leva um segundo para concluir, um conjunto de dados A contenção de 100 itens leva dois segundos e um conjunto de dados contendo 1000 itens levará 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á reduzido pela metade e, portanto, em pé de igualdade com um conjunto de dados de entrada metade do tamanho. Isso torna os algoritmos como pesquisa binária extremamente eficientes ao lidar com grandes conjuntos de dados.

Esta é uma explicação muito simplificada, mas espero que abranja detalhes mais importantes.

Digamos que seu algoritmo que lide com o problema depende de alguns 'fatores', por exemplo, vamos fazer n e x.

Dependendo de n e x, seu algoritmo exigirá algumas operações, por exemplo, na pior das hipóteses 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 grande do seu algoritmo é O(N^2 + log(X)). Basicamente, traduz 'a quantidade de operações que seu algoritmo precisa para as piores escalas com isso'.

Prefácio

algoritmo: procedimento/fórmula para resolver um problema

Como analisar algoritmos e como podemos comparar algoritmos um contra o outro?

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

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

3 itens principais:

Comparar A rapidez com que o tempo de execução cresce NÃO Compare os tempos de execução exatos (depende do hardware)
Apenas preocupado com o tempo de execução em relação à entrada (n)
Como n fica arbitrariamente grande, concentre -se nos termos que crescerão mais rápido à medida que N fica grande (pense no infinito), também conhecido como Análise assintótica

Complexidade espacial: 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 da memória.

Licenciado em: CC-BY-SA com atribuição

Não afiliado a StackOverflow

O que é um inglês simples explicação do "Big O" notação?

O Livro De Telefone

O Caixeiro-Viajante

Em Tempo Polinomial

O (1)

SOBRE)

SOBRE2)

O (2N)

Logaritmos

Prefácio

SOBRE²)

O (2^N)