Existem algoritmos O (1 / n)?

Existem algoritmos O (1 / n)?

Ou qualquer outra coisa que seja menor que O (1)?

Esta questão não é tão estúpida quanto parece. Pelo menos teoricamente, algo como O (1 / n ) é completamente sensato quando tomamos a definição matemática da notação Big O :

Agora você pode facilmente replace g ( x ) por 1 / x … é óbvio que a definição acima ainda vale para alguns f .

Para o propósito de estimar o crescimento de tempo de execução assintótico, isso é menos viável … um algoritmo significativo não pode ser mais rápido à medida que a input cresce. Claro, você pode construir um algoritmo arbitrário para atender isso, por exemplo, o seguinte:

def get_faster(list): how_long = (1 / len(list)) * 100000 sleep(how_long) 

Claramente, esta function gasta menos tempo à medida que o tamanho da input cresce … pelo menos até algum limite, reforçado pelo hardware (precisão dos números, tempo mínimo que o sleep pode esperar, tempo para processar argumentos etc.): este limite seria então um limite inferior constante de modo que, de fato, a function acima ainda tem tempo de execução O (1).

Mas existem algoritmos do mundo real onde o tempo de execução pode diminuir (pelo menos parcialmente) quando o tamanho da input aumenta. Observe que esses algoritmos não exibirão comportamento de tempo de execução abaixo de O (1), no entanto. Ainda assim, eles são interessantes. Por exemplo, pegue o algoritmo de busca de texto muito simples da Horspool . Aqui, o tempo de execução esperado diminuirá conforme o comprimento do padrão de pesquisa aumentar (mas o aumento do comprimento do palheiro aumentará novamente o tempo de execução).

Sim.

Há precisamente um algoritmo com tempo de execução O (1 / n), o algoritmo “vazio”.

Para um algoritmo ser O (1 / n) significa que ele executa assintoticamente em menos etapas do que o algoritmo que consiste em uma única instrução. Se ele for executado em menos etapas que um passo para todo n> n0, ele deve consistir precisamente em nenhuma instrução para aqueles n. Como a verificação de ‘se n> n0’ custa pelo menos 1 instrução, ela deve consistir em nenhuma instrução para todo n.

Resumindo: O único algoritmo que é O (1 / n) é o algoritmo vazio, consistindo de nenhuma instrução.

Isso não é possível. A definição de Big-O não é maior que a desigualdade:

 A(n) = O(B(n)) < => exists constants C and n0, C > 0, n0 > 0 such that for all n > n0, A(n) < = C * B(n) 

Portanto, o B (n) é, de fato, o valor máximo, portanto, se diminuir à medida que n aumenta, a estimativa não será alterada.

sharptooth está correto, O (1) é o melhor desempenho possível. No entanto, isso não implica uma solução rápida, apenas uma solução de tempo fixo.

Uma variante interessante, e talvez o que realmente está sendo sugerido, é quais problemas ficam mais fáceis à medida que a população cresce. Eu posso pensar em uma resposta, embora artificial e irônico:

Duas pessoas em um set têm o mesmo aniversário? Quando n excede 365, retorna verdadeiro. Embora para menos de 365, isso é O (n ln n). Talvez não seja uma ótima resposta, já que o problema não se torna mais fácil, mas apenas se torna O (1) para n> 365.

Do meu aprendizado anterior de grande notação O, mesmo se você precisar de 1 passo (como verificar uma variável, fazer uma atribuição), é O (1).

Note que O (1) é o mesmo que O (6), porque a “constante” não importa. É por isso que dizemos que O (n) é o mesmo que O (3n).

Então, se você precisa de apenas 1 passo, é O (1) … e como seu programa precisa de pelo menos 1 passo, o mínimo que um algoritmo pode ir é O (1). A menos que não façamos isso, então é O (0), eu acho? Se fizermos alguma coisa, então é O (1), e esse é o mínimo que pode ser alcançado.

(Se escolhermos não fazer isso, então pode se tornar uma questão Zen ou Tao … no campo da programação, O (1) ainda é o mínimo).

Ou que tal isso:

programador : chefe, eu encontrei uma maneira de fazer isso no tempo O (1)!
chefe : não há necessidade de fazê-lo, estamos falidos esta manhã.
programador : oh, então, ele se torna O (0).

Que tal não executar a function (NOOP)? ou usando um valor fixo. Isso conta?

Não, isso não é possível:

Como n tende ao infinito em 1 / n, eventualmente alcançamos 1 / (inf), que é efetivamente 0.

Assim, a class big-oh do problema seria O (0) com um n massivo, mas mais próximo do tempo constante com um n baixo. Isso não é sensato, pois a única coisa que pode ser feita em tempo mais rápido que o constante é:

void nothing() {};

E até isso é discutível!

Assim que você executar um comando, você estará em pelo menos O (1), então não, nós não podemos ter uma grande class de O (1 / n)!

Eu geralmente uso O (1 / n) para descrever as probabilidades que diminuem à medida que as inputs se tornam maiores – por exemplo, a probabilidade de uma moeda justa aparecer no log2 (n) flips é O (1 / n).

O (1) significa simplesmente “tempo constante”.

Quando você adiciona uma saída antecipada a um loop [1], você está (em uma notação big-O) transformando um algoritmo O (1) em O (n), mas tornando-o mais rápido.

O truque é, em geral, o algoritmo de tempo constante é o melhor, e linear é melhor que exponencial, mas para pequenas quantidades de n, o algoritmo exponencial pode ser realmente mais rápido.

1: Supondo um comprimento de lista estático para este exemplo

Acredito que os algoritmos quânticos podem fazer várias computações “de uma vez” via superposição …

Eu duvido que esta seja uma resposta útil.

Para qualquer pessoa cuja leitura esta pergunta e queira entender sobre o que é a conversa, isso pode ajudar:

 | |constant |logarithmic |linear| N-log-N |quadratic| cubic | exponential | | n | O(1) | O(log n) | O(n) |O(n log n)| O(n^2) | O(n^3) | O(2^n) | | 1 | 1 | 1 | 1| 1| 1| 1 | 2 | | 2 | 1 | 1 | 2| 2| 4| 8 | 4 | | 4 | 1 | 2 | 4| 8| 16| 64 | 16 | | 8 | 1 | 3 | 8| 24| 64| 512 | 256 | | 16 | 1 | 4 | 16| 64| 256| 4,096 | 65536 | | 32 | 1 | 5 | 32| 160| 1,024| 32,768 | 4,294,967,296 | | 64 | 1 | 6 | 64| 384| 4,069| 262,144 | 1.8 x 10^19 | 

Muitas pessoas tiveram a resposta correta (Não). Eis outra maneira de provar isso: Para ter uma function, você precisa chamar a function e você deve retornar uma resposta. Isso leva uma certa quantidade constante de tempo. MESMO QUE o restante do processamento tenha levado menos tempo para inputs maiores, a impressão da resposta (que supomos ser um único bit) leva pelo menos tempo constante.

Se a solução existir, ela pode ser preparada e acessada em tempo constante = imediatamente. Por exemplo, usando uma estrutura de dados LIFO, se você souber que a consulta de sorting é para ordem inversa. Então os dados já estão classificados, dado que o modelo apropriado (LIFO) foi escolhido.

Quais problemas se tornam mais fáceis à medida que a população cresce? Uma resposta é uma coisa como bittorrent, em que a velocidade de download é uma function inversa do número de nós. Ao contrário de um carro, que fica mais lento quanto mais você carrega, uma rede de compartilhamento de arquivos como o bittorrent acelera mais nós conectados.

Você não pode ir abaixo de O (1), porém O (k) onde k é menor que N é possível. Nós os chamamos de algoritmos de tempo sublinear . Em alguns problemas, o algoritmo de tempo Sublinear só pode fornecer soluções aproximadas para um problema específico. No entanto, às vezes, uma solução aproximada é boa, provavelmente porque o dataset é muito grande ou é muito computacionalmente caro para computar tudo.

O (1 / n) não é menor que O (1), basicamente significa que quanto mais dados você tem, mais rápido o algoritmo vai. Digamos que você tenha um array e sempre preencha até 10 100 elementos se tiver menos do que isso e não fizer nada se houver mais. Este não é O (1 / n), é claro, mas algo como O (-n) 🙂 Pena que a notação O-big não permite valores negativos.

Como foi apontado, além da possível exceção da function nula, não pode haver funções O(1/n) , já que o tempo gasto terá que se aproximar de 0.

Claro, existem alguns algoritmos, como o definido por Konrad, que parecem ser menores que O(1) pelo menos em algum sentido.

 def get_faster(list): how_long = 1/len(list) sleep(how_long) 

Se você quiser investigar esses algoritmos, você deve definir sua própria medida assintótica ou sua própria noção de tempo. Por exemplo, no algoritmo acima, eu poderia permitir o uso de um número de operações “livres” uma quantidade definida de vezes. No algoritmo acima, se eu definir t ‘excluindo o tempo para tudo exceto o sono, então t’ = 1 / n, que é O (1 / n). Existem provavelmente exemplos melhores, pois o comportamento assintótico é trivial. Na verdade, tenho certeza de que alguém pode descobrir os sentidos que dão resultados não triviais.

A maioria do resto das respostas interpreta big-O como sendo exclusivamente sobre o tempo de execução de um algoritmo. Mas como a pergunta não mencionou, achei que vale a pena mencionar a outra aplicação do big-O na análise numérica, que é sobre erro.

Muitos algoritmos podem ser O (h ^ p) ou O (n ^ {- p}) dependendo se você está falando sobre o tamanho do passo (h) ou o número de divisões (n). Por exemplo, no método de Euler , você procura uma estimativa de y (h), dado que você conhece y (0) e dy / dx (a derivada de y). Sua estimativa de y (h) é mais precisa quanto mais próximo de 0. Então, para encontrar y (x) para algum x arbitrário, o intervalo é de 0 a x, divide-se até n partes e executa o método de Euler em cada ponto, para ir de y (0) para y (x / n) para y (2x / n) e assim por diante.

Então, o método de Euler é então um algoritmo O (h) ou O (1 / n), onde h é tipicamente interpretado como um tamanho de passo e n é interpretado como o número de vezes que você divide um intervalo.

Você também pode ter O (1 / h) em aplicativos de análise numérica real, devido a erros de arredondamento de ponto flutuante . Quanto menor o seu intervalo, mais o cancelamento ocorre para a implementação de certos algoritmos, mais perda de dígitos significativos e, portanto, mais erros, que são propagados pelo algoritmo.

Para o método de Euler, se você estiver usando pontos flutuantes, use um passo e um cancelamento pequenos o suficiente e você estará adicionando um número pequeno a um grande número, deixando o número grande inalterado. Para algoritmos que calculam a derivada subtraindo um ao outro dois números de uma function avaliada em duas posições muito próximas, aproximando y ‘(x) com (y (x + h) – y (x) / h), em funções suaves y (x + h) se aproxima de y (x) resultando em grande cancelamento e uma estimativa para o derivativo com menos números significativos. Isso, por sua vez, será propagado para qualquer algoritmo para o qual você precise derivar (por exemplo, um problema de valor limite).

OK, eu pensei um pouco sobre isso, e talvez exista um algoritmo que possa seguir esta forma geral:

Você precisa calcular o problema do vendedor ambulante para um gráfico de 1.000 nós, no entanto, você também recebe uma lista de nós que você não pode visitar. À medida que a lista de nós não visíveis aumenta, o problema fica mais fácil de resolver.

O que sobre isso:

 void FindRandomInList(list l) { while(1) { int rand = Random.next(); if (l.contains(rand)) return; } } 

À medida que o tamanho da lista cresce, o tempo de execução esperado do programa diminui.

Eu vejo um algoritmo que é O (1 / n) reconhecidamente para um limite superior:

Você tem uma grande série de inputs que estão mudando devido a algo externo à rotina (talvez elas reflitam o hardware ou pode até haver algum outro núcleo no processador fazendo isso) e você deve selecionar um random, mas válido.

Agora, se não estivesse mudando, você simplesmente faria uma lista de itens, escolheria um aleatoriamente e teria O (1) tempo. No entanto, a natureza dinâmica dos dados impede a criação de uma lista, você simplesmente tem que sondar aleatoriamente e testar a validade da sonda. (E note que, inerentemente, não há garantia de que a resposta ainda seja válida quando for devolvida. Isso ainda poderia ter sido usado – digamos, a IA para uma unidade em um jogo. Ela poderia atirar em um alvo que desaparecia enquanto puxando o gatilho.)

Isso tem um pior desempenho de infinito, mas um desempenho médio do caso que diminui à medida que o espaço de dados é preenchido.

Na análise numérica, os algoritmos de aproximação devem ter uma complexidade assintótica sub-constante na tolerância de aproximação.

 class Function { public double[] ApproximateSolution(double tolerance) { // if this isn't sub-constant on the parameter, it's rather useless } } 

Eu tive uma dúvida assim em 2007, bom ver esse tópico, eu cheguei a este tópico do meu tópico do reddit -> http://www.reddit.com/r/programming/comments/d4i8t/trying_to_find_an_algorithm_with_its_complexity/

Pode ser possível construir um algoritmo que seja O (1 / n). Um exemplo seria um loop que itera algum múltiplo de f (n) -n vezes onde f (n) é alguma function cujo valor é garantido para ser maior que n e o limite de f (n) -n como n se aproxima do infinito é zero. O cálculo de f (n) também precisaria ser constante para todo n. Eu não sei de improviso como seria o f (n) ou qual aplicativo esse algoritmo teria, na minha opinião, tal function poderia existir, mas o algoritmo resultante não teria outro propósito além de provar a possibilidade de um algoritmo com O (1 / n).

Eu não sei sobre algoritmos, mas complexidades menores que O (1) aparecem em algoritmos randoms. Na verdade, o (1) (little o) é menor que O (1). Esse tipo de complexidade geralmente aparece em algoritmos randoms. Por exemplo, como você disse, quando a probabilidade de algum evento é de ordem 1 / n, ele denota isso com o (1). Ou quando eles querem dizer que algo acontece com alta probabilidade (por exemplo, 1 – 1 / n) eles denotam com 1 – o (1).

Se a resposta for a mesma, independentemente dos dados de input, você terá um algoritmo O (0).

ou em outras palavras – a resposta é conhecida antes dos dados de input serem enviados – a function pode ser otimizada – então O (0)

A notação Big-O representa o pior cenário para um algoritmo que não é a mesma coisa que seu tempo de execução típico. É simples provar que um algoritmo O (1 / n) é um algoritmo O (1). Por definição,
O (1 / n) -> T (n) < = 1 / n, para todos n> = C> 0
O (1 / n) -> T (n) < = 1 / C, desde 1 / n <= 1 / C para todos n> = C
O (1 / n) -> O (1), pois a notação Big-O ignora as constantes (ou seja, o valor de C não importa)

Nada é menor que O (1) A notação Big-O implica a maior ordem de complexidade para um algoritmo

Se um algoritmo tem um tempo de execução de n ^ 3 + n ^ 2 + n + 5 então é O (n ^ 3). Os poderes inferiores não importam aqui porque n -> Inf, n ^ 2 será irrelevante comparado a n ^ 3

Likewise as n -> Inf, O(1/n) will be irrelevant compared to O(1) hence 3 + O(1/n) will be the same as O(1) thus making O(1) the smallest possible computational complexity

 inline void O0Algorithm() {} 

Here’s a simple O(1/n) algorithm. And it even does something interesting!

 function foo(list input) { int m; double output; m = (1/ input.size) * max_value; output = 0; for (int i = 0; i < m; i++) output+= random(0,1); return output; } 

O(1/n) is possible as it describes how the output of a function changes given increasing size of input. If we are using the function 1/n to describe the number of instructions a function executes then there is no requirement that the function take zero instructions for any input size. Rather, it is that for every input size, n above some threshold, the number of instructions required is bounded above by a positive constant multiplied by 1/n. As there is no actual number for which 1/n is 0, and the constant is positive, then there is no reason why the function would constrained to take 0 or fewer instructions.