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?

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.

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 \times n$$C$
• é realmente ( C × n ) 2 , onde C determina a nitidez da curva.$O(n^2)$$(C \times n)^2$$C$

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)$$C$$O(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(\log{n})$$O(n \log{n})$

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 ".$X$$X$

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.

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.

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 , $\Theta(n^2)$ $cn^2$$C$$n_0$$n\geq n_0$$cn^2$$n_0=100,000,000$e 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 $n$$n^2 < 1000n$$O(n^{2.3729})$ algoritmo é mais rápido, a menos que suas matrizes sejam realmente grandes.$O(n^{2.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$n$$n^2$$n^3$$\Theta(n^2)$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.

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 (n^2)$$n_0$$f (n) < c n^2$$n > n_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.$c n^2$$n^2 + 10^{18}$

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

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.

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

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.

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

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

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)$$O(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)$
2. $O(n)$
3. $O(nlog(n))$
4. $O(n^2)$

$O(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. $4nlog(n)$ etapas (log com base 2)
4. $1n^2$ 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 \times 10 = 110$ passos
3. $4 \times 10 \times 3.32 \approx 134$ passos
4. $1 \times 100 = 100$ passos

Como você vê, neste caso, o aparentemente pior algoritmo com complexidade assintótica $O(n^2)$ é o mais rápido, batendo algoritmos com $O(1), O(n)$ e $O(nlog(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 tratar$O(n^2)$ tão melhor que $O(1)$ (o que isso significaria, afinal?) Isso significa que, para entradas suficientemente pequenas (como você viu no exemplo), o $O(n^2)$ ainda pode ser mais rápido do que $O(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.