"Para pequenos valores de n, O (n) pode ser tratado como se fosse O (1)"

26

Já ouvi várias vezes que, para valores suficientemente pequenos de n, O (n) pode ser pensado / tratado como se fosse O (1).

Exemplo :

A motivação para fazer isso é baseada na idéia incorreta de que O (1) é sempre melhor que O (lg n), é sempre melhor que O (n). A ordem assintótica de uma operação só é relevante se, em condições realistas, o tamanho do problema se tornar realmente grande. Se n permanecer pequeno, todo problema será O (1)!

O que é suficientemente pequeno? 10? 100? 1.000? Em que momento você diz "não podemos mais tratar isso como uma operação gratuita"? Existe uma regra de ouro?

Parece que pode ser específico do domínio ou do caso, mas existem regras gerais gerais sobre como pensar sobre isso?

rianjs
fonte
4
A regra geral depende de qual problema você deseja resolver. Seja rápido em sistemas embarcados com ? Publicar na teoria da complexidade? n100
Raphael
3
Pensando mais nisso, parece basicamente impossível criar uma única regra de ouro, porque os requisitos de desempenho são determinados pelo seu domínio e pelos requisitos de negócios. Em ambientes sem recursos limitados, n pode ser bastante grande. Em ambientes severamente restritos, pode ser bem pequeno. Isso parece óbvio agora em retrospectiva.
Rianjs
12
@rianjs Você parece estar enganando O(1)de graça . O raciocínio por trás das primeiras frases é que O(1)é constante , que às vezes pode ser incrivelmente lento. Um cálculo que leva mil bilhões de anos, independentemente da entrada, é um O(1)cálculo.
Mooing Duck
11
Pergunta relacionada sobre por que usamos assintóticos em primeiro lugar.
Raphael
3
@rianjs: esteja ciente das piadas como "um pentágono é aproximadamente um círculo, para valores suficientemente grandes de 5". A frase sobre a qual você está perguntando faz sentido, mas, como já causou alguma confusão, pode valer a pena perguntar a Eric Lippert até que ponto essa escolha exata de fraseado teve efeito humorístico. Ele poderia ter dito: "se existe algum limite superior em , todo problema é " e ainda está matematicamente correto. "Pequeno" não faz parte da matemática. O ( 1 )nO(1)
21714 Steve Jobs (

Respostas:

21

Todas as ordens de magnitude envolvem um constante , várias delas na verdade. Quando o número de itens é grande o suficiente, essa constante é irrelevante. A questão é se o número de itens é pequeno o suficiente para que essa constante domine.C

Aqui está uma maneira visual de pensar sobre isso.

insira a descrição da imagem aqui

Todos têm uma constante de inicialização que determina seu ponto de partida no eixo Y. Cada um também possui uma constante crítica, dominando a rapidez com que eles aumentarão.C

  • Para , C determina o tempo.O(1)C
  • é realmente C × n , onde C determina o ângulo.O(n)C×nC
  • é realmente ( C × n ) 2 , onde C determina a nitidez da curva.O(n2)(C×n)2C

Para determinar qual algoritmo você deve usar, é necessário estimar o local onde os tempos de execução se cruzam. Por exemplo, uma solução com um tempo de inicialização alto ou um C alto perderá para uma solução O ( n ) com um tempo de inicialização baixo e um C baixo em um número bastante grande de itens.O(1 1)CO(n)C

Aqui está um exemplo do mundo real. Você precisa mover um monte de tijolos pelo quintal. Você pode movê-los alguns de cada vez com as mãos ou pegar uma retroescavadeira enorme e lenta para levantá-los e conduzi-los em uma única viagem. Qual é a sua resposta se houver três tijolos? Qual é a sua resposta se houver três mil?

Aqui está um exemplo de CS. Digamos que você precise de uma lista sempre classificada. Você pode usar uma árvore que se manterá em ordem para . Ou você pode usar uma lista não classificada e reorganizar após cada inserção ou exclusão em O ( n log n ) . Como as operações em árvore são complicadas (elas têm uma constante alta) e a classificação é muito simples (constante baixa), a lista provavelmente ganhará centenas ou milhares de itens.O(registron)O(nlogn)

Você pode observar esse tipo de coisa, mas no final o benchmarking é o que fará isso. Você também precisa observar quantos itens normalmente terá e reduzir o risco de receber mais. Você também deseja documentar sua suposição como "o desempenho diminuirá rapidamente em itens" ou "assumimos um tamanho máximo definido de X ".XX

Como esses requisitos estão sujeitos a alterações, é importante colocar esse tipo de decisão atrás de uma interface. No exemplo da árvore / lista acima, não exponha a árvore ou a lista. Dessa forma, se suas suposições estiverem erradas ou você encontrar um algoritmo melhor, poderá mudar de idéia. Você pode até fazer um híbrido e alternar dinamicamente os algoritmos à medida que o número de itens aumenta.

Schwern
fonte
Não faz sentido dizer . O que você realmente quer dizer é que, se o tempo de execução é T = O ( 1 ) , em seguida (em muitos casos) T C . Se T = O ( n ) , em muitos casos T C n , ou mais formalmente T = C n + o ( n ) . E assim por diante. Observe, no entanto, que em outros casos a constante C varia de acordo comO(1)=O(C)T=O(1)TCT=O(n)TCnT=Cn+o(n)C , dentro de certos limites. n
Yuval Filmus
@YuvalFilmus É por isso que eu gosto de gráficos.
21414 Schwern
Esta é a melhor resposta, de longe, o ponto é a rapidez com que a função cresce.
Ricardo
11
Gráfico bonito, mas o eixo realmente deve ser rotulado como "tempo", não "velocidade". y
Ilmari Karonen
11
A linha realmente uma parábola, não é? Parece muito plano para n pequeno e muito íngreme para n grande . O(n2)nn
David Richerby
44

Isso ajuda bastante as respostas já postadas, mas pode oferecer uma perspectiva diferente.

É revelador que a pergunta discuta "valores suficientemente pequenos de n ". O objetivo principal do Big-O é descrever como o processamento cresce em função do que está sendo processado. Se os dados que estão sendo processados ​​permanecem pequenos, é irrelevante discutir o Big-O, porque você não está interessado no crescimento (o que não está acontecendo).

Dito de outra forma, se você estiver percorrendo uma distância muito curta na rua, pode ser igualmente rápido andar, usar uma bicicleta ou dirigir. Pode até ser mais rápido andar se demorar um pouco para encontrar as chaves do carro ou se ele precisar de gasolina, etc.

Para n pequeno , use o que for conveniente.

Se você estiver fazendo uma viagem de cross-country, precisará procurar maneiras de otimizar sua direção, sua quilometragem, etc.

Eric Hughes
fonte
5
"Para n pequeno, use o que for conveniente." - se você executar a operação com frequência , escolha a mais rápida (para o seu ). Veja também aqui . n
Raphael
4
Grande metáfora!
Evorlor
11
Do ponto de vista puramente matemático, a complexidade assintótica não diz nada quando n < infinity.
Gordon Gustafson
15

A citação é bastante vaga e imprecisa. Há pelo menos três maneiras relacionadas pelas quais ele pode ser interpretado.

O ponto matemático literal por trás disso é que, se você estiver interessado apenas em instâncias de tamanho até algum limite, haverá apenas muitas instâncias possíveis. Por exemplo, existem apenas finitamente muitos gráficos em até cem vértices. Se houver apenas um número finito de instâncias, você poderá, em princípio, resolver o problema apenas construindo uma tabela de consulta de todas as respostas para todas as instâncias possíveis. Agora, você pode encontrar a resposta verificando primeiro se a entrada não é muito grande (o que leva tempo constante: se a entrada for maior que  k, é inválido) e procure a resposta na tabela (que leva tempo constante: há um número fixo de entradas na tabela). Observe, no entanto, que o tamanho real da tabela é provavelmente incomensuravelmente grande. Eu disse que há apenas um número finito de gráficos em cem vértices e é verdade. Só que o número finito é maior que o número de átomos no universo observável.

Um ponto mais prático é que, quando dizemos que o tempo de execução de um algoritmo é , isso significa apenas que é assintoticamente c n 2  passos, para um C constante  . Ou seja, existe uma constante n 0, de modo que, para todos os n n 0 , o algoritmo leva aproximadamente c n 2 etapas. Mas talvez n 0 = 100 , 000 , 000Θ(n2) cn2Cn0nn0cn2n0=100,000,000e você só está interessado em instâncias de tamanho muito menor que isso. O limite quadrático assintótico pode nem se aplicar às suas pequenas instâncias. Você pode ter sorte e pode ser mais rápido com pequenas entradas (ou pode ter azar e ser mais lento). Por exemplo, para pequeno  , n 2 < 1000 n , é melhor executar um algoritmo quadrático com boas constantes do que um algoritmo linear com constantes ruins. Um exemplo prático disto é que os algoritmos de multiplicação de matrizes assintoticamente mais eficientes (variantes de Galveston-Winograd , executando em tempo O ( n 2,3729 ) ) são raramente utilizados na prática por causa de Strassen ónn2<1000nO(n2,3729) algoritmo é mais rápido, a menos que suas matrizes sejam realmente grandes.O(n2,8074)

Um terceiro ponto é que, se  é pequeno, n 2 e até n 3  são pequenos. Por exemplo, se você precisar classificar alguns milhares de itens de dados e classificá-los apenas uma vez, qualquer algoritmo de classificação será suficiente: a Θ ( n 2 )nn2n3Θ(n2)o algoritmo ainda precisará apenas de algumas dezenas de milhões de instruções para classificar seus dados, o que não leva muito tempo em uma CPU capaz de executar bilhões de instruções por segundo. OK, também existem acessos à memória, mas mesmo um algoritmo lento levará menos de um segundo, então provavelmente é melhor usar um algoritmo simples e lento e acertar do que usar um algoritmo complexo e rápido e descobrir que é muito rápido mas com erros e, na verdade, não classifica os dados corretamente.

David Richerby
fonte
4
Embora pontos perfeitamente corretos e válidos, acho que você não entendeu. Parece que eles queriam dizer que, às vezes, o algoritmo com desempenho melhor do que um algoritmo com O ( 1 ) , para n s suficientemente pequenos . Isso acontece, por exemplo, quando o primeiro tem tempo de execução 10 n + 50 , enquanto o último é executado no tempo 100000 . Então, para n pequeno o suficiente, é realmente mais rápido usar o protocolo O ( n ) . O(n)O(1 1)n10n+50.100000nO(n)
Ran G.
@Tocou. Isso não vem para o meu segundo caso? (Especialmente se eu editá-lo para dizer algo mais como "Um linear algoritmo com bons constantes pode bater um algoritmo constante / logarítmica com constantes maus"?)
David Richerby
11
Seria bom mencionar explicitamente a importância das constantes quando n é pequeno. É algo que provavelmente não ocorreria a alguém que nunca ouviu isso antes.
Rob Watts
9

A notação Big-O realmente diz apenas algo sobre o comportamento de n arbitrário grande. Por exemplo, significa que existe uma constante c> 0 e um número inteiro n 0 tal que f ( n ) < c n 2 para cada n > n 0 .f(n)=O(n2)n0 0f(n)<cn2n>n0 0

Em muitos casos, você pode encontrar uma constante c e dizer "Para cada n> 0, f (n) é aproximadamente ". Qual é a informação útil para ter. Mas, em alguns casos, isso não é verdade. Se f (n) = n 2 + 10 18 , isso é totalmente enganador. Portanto, apenas porque algo é O (n ^ 2) não significa que você pode desligar o cérebro e ignorar a função real.cn2n2+1018

Por outro lado, se você apenas encontrar os valores n = 1, 2 e 3, na prática, não fará diferença o que f (n) faz para n ≥ 4, portanto, é melhor considerar que f ( n) = O (1), com c = max (f (1), f (2), f (3)). E é isso que significa suficientemente pequeno: se a afirmação de que f (n) = O (1) não o engana, se os únicos valores de f (n) que você encontrar são "suficientemente pequenos".

gnasher729
fonte
5

Se não cresce, é O (1)

A afirmação do autor é um pouco axiomática.

Ordens de crescimento descrevem o que acontece com a quantidade de trabalho que você deve realizar à medida que Naumenta. Se você sabe que Nisso não aumenta, seu problema é efetivamente O(1).

Lembre-se que O(1)não significa "rápido". Um algoritmo que sempre exige 1 trilhão de etapas para ser concluído é O(1). Um algoritmo que leva de 1 a 200 etapas, mas nunca mais, é O(1). [1]

Se o seu algoritmo executa exatamente N ^ 3etapas e você sabe que Nnão pode ser superior a 5, nunca pode executar mais do que 125 etapas, portanto é eficaz O(1).

Mas, novamente, O(1)não significa necessariamente "rápido o suficiente". Essa é uma pergunta separada que depende do seu contexto. Se demorar uma semana para terminar algo, você provavelmente não se importa se é tecnicamente O(1).


[1] Por exemplo, a pesquisa em um hash é O(1), mesmo que as colisões de hash signifiquem que você precise examinar vários itens em um balde, desde que haja um limite rígido de quantos itens podem estar nesse balde.

Nathan Long
fonte
11
Isso tudo parece válido, exceto por isso: "Se o seu algoritmo executa exatamente N ^ 3 etapas e você sabe que N não pode ser superior a 5, ele nunca pode executar mais de 125 etapas, portanto é O (1)". . Novamente, se um algoritmo usa um número inteiro e meu suporte para número inteiro máximo é 32767, é O (1)? Obviamente não. Big-O não muda com base nos limites dos parâmetros. É O (n) mesmo que você saiba que 0 <n <3 porque n = 2 leva o dobro do tempo que n = 1.
JSobell
3
@JSobell Mas é O (1). Se houver uma limitação que limita seu n para f (n), significa que ele não pode crescer indefinidamente. Se seu n é limitado por 2 ^ 15, sua grande função n ^ 2 é realmente g(n) = min(f(2^15), f(n))- que está em O (1). Dito isso, na prática, as constantes são muito importantes e claramente n pode se tornar grande o suficiente para que uma análise assintótica seja útil.
Voo
2
@JSobell Isso é semelhante à questão de saber se os computadores são realmente "Turing Complete", já que tecnicamente não podem ter um espaço de armazenamento infinito. Tecnicamente, matematicamente, um computador não é uma máquina de Turing "verdadeira". Na prática, não existe "fita infinita", mas os discos rígidos chegam perto o suficiente.
Kyle Strand
Eu escrevi um sistema de Risco financeiro há vários anos que envolvia n ^ 5 manipulações matriciais, então tinha um limite prático de n = 20 antes que os recursos se tornassem um problema.
precisa
Desculpe, pressione Enter muito cedo. Eu escrevi um sistema de Risco financeiro há vários anos que envolvia n ^ 5 manipulações matriciais, então tinha um limite prático de n = 20 antes que os recursos se tornassem um problema. De acordo com essa lógica falha, a função criada é O (1) porque eu tenho um limite de 20. Quando o cliente diz "Hmm, talvez devêssemos movê-lo para 40 como um limite ... Sim, o algoritmo é O (1 ), então não há problema "... É por isso que os limites de uma entrada não fazem sentido. A função era O (n ^ 5), não O (1), e este é um exemplo prático de por que Big-O é independente dos limites.
precisa
2

Agora, posso usar uma hashtable e ter O (1) pesquisas (deixando de lado a implementação específica da hashtable), mas se eu tivesse, por exemplo, uma lista, teria O (n) pesquisas. Dado esse axioma, esses dois serão iguais se as coleções forem pequenas o suficiente. Mas em algum momento eles divergem ... que ponto é esse?

Na prática, é o ponto em que a construção da tabela de hash leva mais do que o benefício que você obtém com as pesquisas aprimoradas. Isso varia muito com base na frequência com que você faz a pesquisa e na frequência com que faz outras coisas. O (1) vs O (10) não é grande coisa se você fizer isso uma vez. Se você fizer isso milhares de vezes por segundo, mesmo isso importa (embora pelo menos importe a uma taxa linearmente crescente).

Telastyn
fonte
Se você quiser ter certeza, faça algumas experiências para ver qual estrutura de dados é melhor para seus parâmetros.
Yuval Filmus
@Telastyn Yuval Filmus está certo, se você realmente quer ter certeza. Eu sei o nome de uma pessoa Jim, seus parâmetros estão ok. Mas ele não ouviu conselhos como o de Yuval. Você realmente deve ouvir Yuval para ter certeza e segurança.
InformedA
2

Embora a citação seja verdadeira (mas vaga), também há perigos para ela. Imo, você deve analisar a complexidade em qualquer estágio do seu aplicativo.

É fácil demais dizer: ei, só tenho uma lista pequena, se quiser verificar se o item A está na lista, escreverei um loop fácil para percorrer a lista e comparar os itens.

Então o seu amigo programador precisa usar a lista, vê sua função e é como: ei, eu não quero duplicatas na lista, então ele usa a função para todos os itens adicionados à lista.

(lembre-se, ainda é um pequeno cenário de lista.)

Três anos depois, eu chego e meu chefe acaba de fazer uma grande venda: nosso software será usado por um grande varejista nacional. Antes atendemos apenas pequenas lojas. E agora meu chefe vem me xingar e gritar: por que o software, que sempre "funcionou bem", agora é terrivelmente lento?

Acontece que essa lista era uma lista de clientes, e nossos clientes tinham apenas talvez 100 clientes, então ninguém percebeu. A operação de preencher a lista era basicamente uma operação O (1), porque demorou menos de um milissegundo. Bem, nem tanto quando há 10.000 clientes a serem adicionados a ele.

E anos após a má decisão O (1) original, a empresa quase perdeu um grande cliente. Tudo por causa de um pequeno erro de design / suposição anos antes.

Pieter B
fonte
Mas também ilustra uma característica importante de muitos sistemas do mundo real: os "algoritmos" que você aprende na graduação são, na verdade, peças a partir das quais "algoritmos" reais são feitos. Isso geralmente é sugerido; por exemplo, a maioria das pessoas sabe que o quicksort geralmente é escrito para retornar à classificação de inserção quando as partições ficam pequenas o suficiente e que a pesquisa binária geralmente é escrita para retornar à pesquisa linear. Mas poucas pessoas percebem que a classificação por mesclagem pode se beneficiar de alguma pesquisa binária.
Pseudônimo
1

A motivação para fazer isso é baseada na idéia incorreta de que O (1) é sempre melhor que O (lg n), é sempre melhor que O (n). A ordem assintótica de uma operação só é relevante se, em condições realistas, o tamanho do problema se tornar realmente grande.

Se eu tiver dois algoritmos com esses horários:

  • log (n) +10000
  • n + 1

Então existe algum ponto em que eles se cruzam. Por nmenor que isso, o algoritmo "linear" é mais rápido, e por nmaior que isso, o algoritmo "logarítmico" é mais rápido. Muitas pessoas cometem o erro de assumir que o algoritmo logarítmico é mais rápido, mas, para os pequenos n, não é.

Se n permanecer pequeno, todo problema será O (1)!

I especular o que quer dizer aqui é que, se né limitado, então todo problema é O (1). Por exemplo, se estivermos classificando números inteiros, podemos optar por usar o quicksort. O(n*log(n))obviamente. Mas se decidirmos que nunca pode haver mais do que 2^64=1.8446744e+19números inteiros, saberemos que n*log(n)<= 1.8446744e+19*log(1.8446744e+19)<= 1.1805916e+21. Portanto, o algoritmo sempre levará menos que 1.1805916e+21"unidades de tempo". Como esse é um tempo constante, podemos dizer que o algoritmo sempre pode ser feito nesse tempo constante -> O(1). (Observe que, mesmo que essas unidades de tempo sejam nanossegundos, isso representa um total geral de mais de 37411 anos). Mas ainda O(1).

Mooing Duck
fonte
0

Suspeito que muitas dessas respostas estejam faltando um conceito fundamental. O (1): O (n) não é o mesmo que f (1): f (n) onde f é a mesma função, porque O não representa uma única função. Mesmo o bom gráfico de Schwern não é válido porque possui o mesmo eixo Y para todas as linhas. Para todos usarem o mesmo eixo, as linhas teriam que ser fn1, fn2 e fn3, onde cada uma era uma função cujo desempenho poderia ser diretamente comparado aos demais.

Já ouvi várias vezes que, para valores suficientemente pequenos de n, O (n) pode ser pensado / tratado como se fosse O (1)

Bem, se n = 1 eles são exatamente iguais? Não. Uma função que permite um número variável de iterações não tem nada em comum com uma que não, a notação big-O não se importa, e nós também não devemos.

A notação Big-O está simplesmente lá para expressar o que acontece quando temos um processo iterativo e como o desempenho (tempo ou recursos) diminui à medida que o 'n' aumenta.

Então, para responder à pergunta real ... eu diria que aqueles que fazem essa afirmação não entendem a notação Big-O corretamente, porque é uma comparação ilógica.

Aqui está uma pergunta semelhante: se eu percorrer uma sequência de caracteres e eu sei que, em geral, minhas seqüências terão menos de 10 caracteres, posso dizer que é o equivalente a O (1), mas se minhas sequências forem mais longas, então eu diria que era O (n)?

Não, porque uma sequência de 10 caracteres leva 10 vezes mais que uma sequência de 1 caractere, mas 100 vezes menos que uma sequência de 1000 caracteres! Está ligado).

JSobell
fonte
O(1 1)f(Eu)Eumax{f(0 0),...,f(10)}O(1 1)
Sim, e este é um exemplo de onde a notação Big-O é geralmente incompreendida. De acordo com seu argumento, se eu souber que o valor máximo de n é 1.000.000, então minha função é O (1). De fato, minha função poderia ser na melhor das hipóteses O (1) e na pior das hipóteses O (n). Essa notação é usada para descrever a complexidade algorítmica, não uma implementação concreta, e sempre usamos a mais cara para descrever um cenário, não a melhor. De fato, pelo seu argumento, toda função que permite n <2 é O (1)! :)
jsobell
n<2O(1 1)f(n)f(10)nO(1 1)
Desculpe, mas se você diz que conhecer os limites superiores de n cria uma função O (1), está dizendo que a representação notacional está diretamente relacionada ao valor de n, e não é. Tudo o mais que você mencionou está correto, mas sugerindo que, como n tem limites, O (1) não está correto. Na prática, existem lugares onde o que você descreve pode ser observável, mas estamos vendo a notação Big-O aqui, não a codificação funcional. Então, novamente, por que você sugeriria que n ter um máximo de 10 tornaria O (1)? Por que 10? Por que não 65535 ou 2 ^ 64?
JSobell
Dito isto, se você escreve uma função que preenche uma string com 10 caracteres, sempre faz um loop sobre a string, então é O (1) porque n é sempre 10 :) #
1825 JSobell
0

Eu acredito que o texto que você citou é bastante impreciso (usar a palavra "melhor" geralmente não faz sentido, a menos que você forneça o contexto: em termos de tempo, espaço etc.) De qualquer forma, acredito que a explicação mais simples seria:

O(1 1)O(1 1) .

Agora, vamos pegar um conjunto relativamente pequeno de 10 elementos e ter alguns algoritmos para classificá-lo (apenas um exemplo). Vamos supor que mantemos os elementos em uma estrutura que também nos fornece um algoritmo capaz de classificar os elementos em tempo constante. Digamos que nossos algoritmos de classificação possam ter as seguintes complexidades (com notação big-O):

  1. O(1 1)
  2. O(n)
  3. O(neuog(n))
  4. O(n2)

O(1 1)

Agora vamos "revelar" as verdadeiras complexidades dos algoritmos de classificação mencionados acima (onde "verdadeiro" significa não ocultar a constante), representado pelo número de etapas necessárias para concluir (e supor que todas as etapas demoram a mesma quantidade de tempo):

  1. 200
  2. 11n
  3. 4neuog(n) etapas (log com base 2)
  4. 1 1n2 passos

Se nossa entrada for do tamanho 10, essas são as quantidades exatas de etapas para cada algoritmo mencionado acima:

  1. 200 passos
  2. 11×10=110 passos
  3. 4×10×3,32134 passos
  4. 1 1×100=100 passos

Como você vê, neste caso, o aparentemente pior algoritmo com complexidade assintótica O(n2) é o mais rápido, batendo algoritmos com O(1 1),O(n) e O(neuog(n))complexidades assintóticas. O fator constante oculto pela notação big-O é importante aqui. Na minha opinião, isso não significa que possamos tratarO(n2) tão melhor que O(1 1) (o que isso significaria, afinal?) Isso significa que, para entradas suficientemente pequenas (como você viu no exemplo), o O(n2) ainda pode ser mais rápido do que O(1 1)por causa da constante oculta. E se a constante for relativamente grande em comparação com o tamanho da entrada, isso poderá importar mais do que a complexidade assintótica.

3yakuya
fonte