A notação Oh grande não menciona valor constante

Sou programador e comecei a ler algoritmos. Não estou completamente convencido com as anotações, como Bog Oh, Big Omega e Big Theta. O motivo é, por definição, de Big Oh, afirma que deve haver uma função g (x) tal que seja sempre maior ou igual a f (x). Ou f (x) <= cn para todos os valores de n> n0.

Por que não mencionamos o valor constante na definição? Por exemplo, digamos que uma função 6n + 4, a denotemos como O (n). Mas não é verdade que a definição seja válida para todos os valores constantes. Isso é válido apenas quando c> = 10 en> = 1. Para valores menores de c que 6, o valor de n0 aumenta. Então, por que não mencionamos o valor constante como parte da definição?

Existem várias razões, mas provavelmente a mais importante é que as constantes são uma função da implementação do algoritmo, não o próprio algoritmo. A ordem de um algoritmo é útil para comparar algoritmos, independentemente de sua implementação.

O tempo de execução real de um quicksort geralmente muda se for implementado em C ou Python, Scala ou Postscript. O mesmo se aplica à classificação de bolhas - o tempo de execução varia amplamente com base na implementação.

No entanto, o que não muda é o fato de que, tudo o mais é igual, à medida que o conjunto de dados aumenta, o tempo necessário para executar uma classificação de bolha aumentará mais rapidamente do que o tempo necessário para executar a classificação rápida no caso típico, independentemente do idioma ou da máquina eles são implementados com, assumindo uma implementação razoavelmente correta. Esse simples fato permite que você faça inferências inteligentes sobre os próprios algoritmos quando detalhes concretos não estão disponíveis.

A ordem de um algoritmo filtra fatores que, embora importantes nas medições reais do mundo real, tendem a ser apenas ruídos ao comparar algoritmos em abstrato.

O (n) e outras notações de ordem (normalmente) não estão relacionadas ao comportamento de funções para valores pequenos. Está preocupado com o comportamento das funções para valores muito grandes, ou seja, limites à medida que n se move em direção ao infinito.

As constantes tecnicamente são importantes, mas geralmente são abstraídas quando n se torna grande o suficiente, o valor de c é totalmente irrelevante. Se o valor de c é importante, podemos incluí-lo na análise, mas, a menos que as funções que estão sendo comparadas possuam fatores constantes muito grandes ou se a eficiência é uma preocupação especialmente importante, elas normalmente não são.

A notação Big O, de acordo com a definição, afirma que: A notação Big O é construída com a intuição de que, para todos os valores n à direita de n ', o valor de f (n) é igual ou inferior a cg (n). As constantes também não importam quando você usa fatores de alto valor (variáveis) (como n-quadrado ou n-cubo), pois são apenas as constantes e não as quantidades variáveis ​​que podem se tornar tão grandes quanto esses fatores. Dado a seguir é o gráfico da notação Big-O.
For a given function g(n), we denote by O(g(n)) the set of functions:
O(g(n)) = {f(n): there exist positive constants c and n' such that 0<=f(n)<=c.g(n) for all n > n'}

A essência dessa notação está no fato " how lower is f(n) from c.g(n) and not when it starts becoming lower".

Na análise de algoritmos, Order of Growth é a principal abstração e fornece a taxa na qual o tempo de execução muda à medida que o tamanho da entrada é alterado. Digamos que um algoritmo tenha um tempo de execução f(n) = 2n + 3. Agora, conectamos algum tamanho de entrada,

n = 10: 2 * 10 + 3 = 23

n = 100: 2 * 100 + 3 = 203

n = 10000: 2 * 10000 + 3 = 20003

n = 1000000: 2 * 1000000 + 3 = 2000003

n = 100000000 : 2 * 100000000 + 3 = 200000003

Como pode ser visto, a ordem de crescimento é determinada principalmente pela variável n; As constantes 2 e 3 são menos significativas e, à medida que o tamanho da entrada aumenta, elas se tornam ainda menos significativas na determinação. É por isso que, na análise de algoritmos, as constantes são diminuídas em favor da variável que determina a ordem de crescimento de uma função.

Toda a noção da notação Big-Oh é especificamente para ignorar constantes e apresentar a parte mais importante da função que descreve o tempo de execução de um algoritmo.

Esqueça a definição formal por um momento. Qual é a pior função (crescimento mais rápido) n^2 - 5000ou 5000 n + 60000? Por nmenos de cerca de 5000, a função linear é maior (e, portanto, pior). Além disso (valor exato 5013?), A equação quadrática é maior.

Como existem mais (muito mais) números positivos maiores que 5000 que menores, consideramos o quadrático como a função 'maior' (pior) em geral. A notação de ordem (Big-Oh etc) impõe isso (você sempre pode eliminar um aditivo e uma constante multiplicativa usando essas definições).

Obviamente, as coisas nem sempre são simples. Às vezes você não quer saber essas constantes. Qual é a melhor classificação de inserção ou de bolha? Ambos são O(n^2). Mas um é realmente melhor que o outro. Com uma análise mais elaborada, é possível obter constantes como você está pensando. Geralmente, é muito mais fácil calcular a função Big-Oh do que uma função mais exata.

Big-Oh ignora essas constantes para simplificar e facilitar as comparações mais importantes. Gostamos da notação porque geralmente não queremos saber sobre as constantes (principalmente irrelevantes).

(como essa é uma resposta mais longa, leia os negritos para obter um resumo )

Vamos dar o seu exemplo e seguir passo a passo, entendendo o propósito por trás do que estamos fazendo. Começamos com sua função e o objetivo de encontrar sua notação Big Oh:

f(n) = 6n+4

Primeiro, vamos O(g(n))ser o Big Oh notação estamos tentando encontrar para f(n). A partir da definição de Big Oh, precisamos encontrar um simplificado g(n) onde existam algumas constantes ce n0onde c*g(n) >= f(n)seja verdade para todos nmaiores que n0.

Primeiro, vamos escolher g(n) = 6n + 4(o que renderia O(6n+4)em Big Oh). Nesse caso, vemos que c = 1e qualquer valor de n0atenderá aos requisitos matemáticos de nossa definição de Big Oh, pois g(n)sempre é igual a f(n):

c*g(n)      >=  f(n)    
1*(6n + 4)  >=  6n + 4    //True for all n's, so we don't need to pick an n0

Neste ponto, atendemos aos requisitos matemáticos. Se parássemosO(6n+4) , fica claro que isso não é mais útil do que escrever f(n), portanto , perderia o verdadeiro objetivo da notação Big Oh: entender a complexidade geral de tempo de um algoritmo! Assim, vamos para o próximo passo: simplificação.

Primeiro, podemos simplificar o 6nque o Big Oh é O(4)? Não! (Exercite para o leitor se ele não entender o porquê)

Segundo, podemos simplificar o 4que é o Big Oh O(6n)? Sim! Nesse caso g(n) = 6n, então:

c*g(n)    >=  f(n)
c*6n      >=  6n + 4     

Neste ponto, vamos escolher c = 2desde então o lado esquerdo aumentará mais rápido (em 12) do que o lado direito (em 6) para cada incremento de n.

2*6n      >=  6n + 4

Agora precisamos encontrar um positivo em n0que a equação acima seja verdadeira para todos que nsão maiores que esse valor. Como já sabemos que o lado esquerdo está aumentando mais rapidamente que o direito, tudo o que precisamos fazer é encontrar uma solução positiva. Assim, uma vez que n0 = 2torna o exposto acima verdade, sabemos que g(n)=6n, ou O(6n)é uma notação potencial do Big Oh para f(n).

Agora, podemos simplificar o 6que é o Big Oh O(n)? Sim! Nesse caso g(n) = n, então:

c*g(n)      >=  f(n)    
c*n         >=  6n + 4    

Vamos escolher, c = 7pois a esquerda aumentaria mais rápido que a direita.

7*n         >=  6n + 4

Vemos que o acima exposto será verdadeiro para todos nmaiores ou iguais a n0 = 4. Assim, O(n)é uma notação potencial do Big Oh para f(n). Podemos simplificar g(n)mais? Não!

Finalmente, descobrimos que a notação Big Oh mais simples f(n)é O(n). Por que passamos por tudo isso? Porque agora sabemos que f(n)é linear , pois a notação Big Oh é de complexidade linear O(n). O bom é que agora podemos comparar a complexidade de tempo f(n)com outros algoritmos! Por exemplo, sabemos agora que f(n)é de comparável tempo a complexidade das funções h(n) = 123n + 72, i(n) = n, j(n) = .0002n + 1234, etc; porque, usando o mesmo processo de simplificação descrito acima, todos eles têm uma complexidade de tempo linear de O(n).

Doce!!!

Se você tem uma função de desempenho 6n + 4, a pergunta relevante é "6 o quê?". Como um comentário perguntou: o que sua constante representa? Em termos de física, quais são as unidades do seu fator constante?

A razão pela qual a notação O () é tão amplamente usada para descrever o desempenho do algoritmo é que não há uma maneira portátil de responder a essa pergunta. Processadores diferentes levam um número diferente de ciclos de clock e quantidades diferentes de tempo para executar o mesmo cálculo elementar, ou podem agrupar os cálculos elementares relevantes de maneira diferente. Diferentes linguagens de computador ou diferentes descrições formais e informais, como o pseudocódigo, representarão algoritmos de maneiras difíceis de comparar diretamente. Mesmo implementações na mesma linguagem podem representar o mesmo algoritmo de maneiras diferentes - detalhes triviais de formatação, como o número de linhas à parte, geralmente você terá uma grande variedade de opções estruturais arbitrárias para implementar qualquer algoritmo.

Veja de outra maneira: usamos "algoritmo" não para descrever uma implementação específica, mas para descrever toda uma classe de possíveis implementações do mesmo procedimento geral. Essa abstração ignora os detalhes da implementação em favor da documentação de algo de valor geral, e o fator de desempenho constante é um desses detalhes.

Dito isso, as descrições de algoritmos geralmente são acompanhadas de folclore, anotações ou até referências reais que descrevem o desempenho de implementações reais em hardware real. Isso dá uma idéia aproximada de que tipo de fator constante esperar, mas também deve ser tomado com um pouco de sal, porque o desempenho real depende de coisas como quanto trabalho foi feito na otimização de uma determinada implementação. Além disso, a longo prazo, o desempenho relativo de algoritmos comparáveis ​​tende a mudar à medida que a arquitetura dos melhores e mais recentes processadores muda ...