Justificação para negligenciar fatores constantes no Big O

Muitas vezes, se as complexidades estão tendo constantes como 3n, negligenciamos essa constante e dizemos O (n) e não O (3n). Não consigo entender como podemos negligenciar essa mudança tríplice? Alguma coisa está variando 3 vezes mais rapidamente que outra! Por que negligenciamos esse fato?

Para racionalizar como as notações assintóticas ignoram fatores constantes, geralmente penso assim: a complexidade assintótica não é para comparar o desempenho de algoritmos diferentes, é para entender como o desempenho de algoritmos individuais é escalado em relação ao tamanho da entrada.

Por exemplo, dizemos que uma função que etapas é , porque, grosso modo, para entradas grandes o suficiente, dobrar o tamanho da entrada não passará do dobro do número de etapas executadas. Da mesma forma, significa que dobrar o tamanho da entrada quadruplicará o número de etapas e significa que dobrar o tamanho da entrada aumentará o número de etapas no máximo em alguma constante.O ( n ) O ( n 2 ) O ( log n $3n$$O(n)$$O(n^2)$$O(\log n)$

É uma ferramenta para dizer quais algoritmos escalam melhor, não quais são absolutamente mais rápidos.

Primeiro, como outras respostas já explicaram, , ou, para colocar em palavras, uma função é O ( 3 n ) se e somente se for O ( n ) . f = O ( 3 n ) significa que existe um ponto N e um fator C 3 tal que para todos n ≥ N , f ( n ) ≤ C 3 ⋅ $O(3n) = O(n)$$O(3n)$$O(n)$$f = O(3n)$$N$$C_3$$n \ge N$ . Agora escolha C 1 = 3 C 3 : para todos n ≥ N , f ( n ) ≤ C 1 ⋅ n , então f = O ( n ) . A prova do inverso é semelhante.$f(n) \le C_3 \cdot 3n$$C_1 = 3 C_3$$n \ge N$$f(n) \le C_1 \cdot n$$f = O(n)$

Agora vamos à razão pela qual essa é a ferramenta certa. Observe que, quando medimos a complexidade de um algoritmo, não fornecemos uma unidade. Não contamos segundos ou instruções da máquina: contamos algumas etapas elementares não especificadas que levam um tempo limitado. Fazemos isso porque a execução do mesmo algoritmo em uma máquina diferente alteraria o tempo necessário por instrução - multiplique a frequência do relógio por e o tempo de execução passará de f ( n ) para f ( n ) /$3$$f(n)$$f(n)/3$. Se implementarmos o mesmo algoritmo em uma linguagem diferente, ou em um sistema diferente, o tempo gasto por cada etapa elementar poderá ser diferente, mas, novamente, há muitos detalhes: dificilmente nos importamos com essas diferenças.

Quando você se importa com horários precisos, a complexidade assintótica não é relevante: a complexidade assintótica informa o que acontece com tamanhos de entrada muito grandes, que podem ou não ser os tamanhos de entrada reais com os quais você está lidando.

Lembre-se da definição de Big-O:

se existir c > 0 tal que f ( n ) ≤ c g ( n ) para todos os n .$f(n)\in O(g(n))$$c>0$$f(n)\le cg(n)$$n$

Sob essa definição, temos esse para cada constante d . O objetivo da notação O é exatamente para simplificar expressões dessa maneira. De fato, 3 n cresce três vezes mais rápido que n , mas ambos são lineares. Se isso é justificado ou não - isso depende do contexto. Mas se você concorda em usar a notação O , por definição isso é válido.$dn\in O(n)$$d$$O$$3n$$n$$O$

A notação Big O é uma média sem unidade de medição da variação de desempenho, portanto impenetrável aos custos relativos das primitivas computacionais.

Em poucas palavras: a notação Big O é um tipo de medição relativo, sem unidade (em oposição à medição absoluta). Ele só pode medir a variação de desempenho, não o desempenho absoluto, para o qual as constantes são muito importantes. A vantagem é que isso a torna amplamente independente da implementação, permitindo análises mais simples que podem ignorar os custos relativos das operações elementares, desde que esses custos tenham limites superiores e inferiores fixos positivos. Mas a consequência é que fatores constantes não têm sentido . Mesmo assim, mesmo para a finalidade pretendida, a análise de complexidade assintótica pode ser questionada por outros motivos e deve ser considerada com cuidado. Por exemplo, o tamanho da entrada bruta pode não ser o parâmetro correto a ser considerado.

Uma primeira observação é que sua pergunta não está exatamente precisa. Quando você negligencia a constante em 3 n , há de fato uma "alteração de três vezes", mas ambas variam na mesma taxa e você não pode afirmar que "[uma] coisa está variando 3 vezes mais rapidamente que a outra".$3$$3n$

Uma boa razão para ignorar a constante na notação Landau é que não temos nenhuma unidade em que possamos confiar. Quando alguém afirma que A vive duas vezes mais longe de você do que B, isso tem significado independentemente de qualquer unidade. Podemos concordar com isso, mesmo que você meça distâncias em polegadas enquanto eu faço isso em anos-luz. Porém, a medição da distância absoluta requer a especificação de unidades, e sua formulação numérica depende da unidade escolhida.

O tempo real gasto por um algoritmo depende do tempo de execução das operações elementares, que depende muito da máquina. Você pode contar o número de operações elementares, mas não há razão para acreditar que todas elas levam o mesmo tempo, e sempre é possível compor várias operações em uma única ou decompor uma operação em operações menores, de modo que o número operações não é realmente significativo, a menos que você concorde com uma máquina virtual de referência. Ser independente de referência é uma vantagem.

Outra visão da vantagem da abordagem é que tudo o que você importa na análise é contar o número de operações elementares, desde que o custo tenha um limite superior e um limite inferior positivo. Você não precisa se preocupar com o custo individual.

No entanto, o preço a pagar por essa vantagem é que a avaliação dos custos de computação é fornecida com unidade não especificada, e o tempo de computação, por exemplo, pode ser nanossegundos ou milênios - nem tentamos saber. Em outras palavras, os fatores constantes não têm sentido, uma vez que a mudança de unidades é inseparável da mudança do fator constante e nenhuma unidade de referência é usada.

Conforme observado por Patrick87 , isso é suficiente para entender como um algoritmo é escalonado em relação ao tamanho da entrada, mas não fornece uma medida absoluta de desempenho, além de depender de uma unidade de referência. A desinstalação de uma máquina abstrata de referência comum pode ser feita quando se deseja comparar o desempenho de algoritmos distintos, mas é mais difícil garantir que a comparação não seja influenciada pelos detalhes da realização. Na complexidade assintótica, esse risco é evitado porque você compara o algoritmo consigo mesmo.

De qualquer forma, apenas um programador ingênuo confiaria exclusivamente na complexidade assintótica para escolher um algoritmo. Existem muitos outros critérios, incluindo a constante não contada e o custo real das operações elementares. Além disso, a complexidade do pior caso pode ser um indicador ruim, porque a fonte da complexidade do pior caso pode ocorrer raramente e em fragmentos da entrada pequenos o suficiente para ter um impacto limitado. Por exemplo, analisadores gerais para gramáticas adjacentes a árvores têm uma complexidade teórica e são bastante úteis na prática. O pior caso que conheço é a inferência do tipo polimórfico de Damas-Hindley-Milner$O(n^6)$algoritmo usado para ML, que tem complexidade exponencial de pior caso. Mas isso não parece incomodar os usuários de ML, nem impedir a gravação de programas muito grandes no ML. Há mais do que a constante que importa. Na verdade, a análise assintótica relaciona uma medida do custo de uma computação a alguma medida da complexidade da entrada. Mas o tamanho bruto pode não ser a medida certa.

Complexidade é como decisão, pode ser teoricamente ruim, mas isso pode ser irrelevante para a maior parte do espaço de dados ... às vezes. A análise de complexidade assintótica é uma ferramenta boa e bem projetada, com suas vantagens e limitações, como todas as ferramentas. Com ou sem explicitar a constante, que pode não ter sentido, é necessário usar o julgamento.

As outras respostas fornecem excelentes explicações do porquê, de acordo com a definição de Big-O, .$O(n)=O(3n)$

Quanto ao motivo pelo qual realmente fazemos isso no CS, é para termos uma descrição compacta da eficiência de um algoritmo. Por exemplo, pode haver um algoritmo que possui uma instrução if, em que um ramo executa instruções e o outro executa 3 n instruções. Isso significa que o número exato muda para cada entrada, mesmo para entradas do mesmo comprimento. Poderíamos encontrar um número para cada entrada, mas usar a notação big-O nos fornece uma medida da complexidade do tempo que vale para TODAS as entradas.$n$$3n$

Isso é muito mais útil para adivinhar a rapidez com que um algoritmo será. Caso contrário, teríamos que analisar uma função maciça por partes, que seria muito difícil de entender.

A outra principal razão é que essas medidas são independentes de hardware. Diferentes compiladores e arquiteturas alteram o mesmo código em conjuntos de instruções muito diferentes. No entanto, se soubermos que o número de instruções é linear, exponencial etc., teremos uma idéia da velocidade dos algoritmos que mantém, independentemente do computador em que o compilamos ou executamos.

$f(n)=O(g(n))$$\limsup\limits_{n\to\infty} \frac{f(n)}{g(n)}<+\infty$

$g(n)=n$$g(n)=3n$

$O(n^2)=O(.00005321n^2+1000000000n+10^{46803})$$f$$=$

Deixe-me explicar-lhe simplesmente. Vamos tomar n = 100000. Agora, o que é 3n? É 300000 ( Sim, são 3 dobras de n ) Mas o que é n ^ 2 ? 10000000000 . ( são 1 lakh dobras de n ). Compare n ^ 2 com n. 3 é insignificante quando comparamos com 1 lakh. então, podemos removê-lo.

Pense se n é alguns bilhões ou trilhões. Nesse caso, novamente vamos comparar 3 com alguns bilhões ou trilhões. Agora, você sabe por que podemos negligenciar 3.