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

13

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?

Pradeep
fonte
4
Como você propõe representar exatamente o valor constante?
Daniel B
1
Indo mais longe, qualquer função de terminação é O (1) se você ligar n.
30712 Brian

Respostas:

23

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.

tylerl
fonte
22

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.

Engenheiro Mundial
fonte
3
Por exemplo, construir as pirâmides é O (n), classificar fotos delas é O (n log n) - em algum momento você pode ter pirâmides suficientes para levar mais tempo para classificar as imagens do que construir uma nova! Mas apenas para um número muito grande de pirâmides!
Martin Beckett
Boa resposta, mas para um dado N e dois algoritmos que normalmente se enquadram na mesma "família" de complexidades, pode haver mérito em fazer exatamente o que o OP sugere e incluir pelo menos os coeficientes relativos. Um algoritmo linear com o dobro do número de instruções por elemento como outro poderia ser denominado * O * (2N) para o segundo alg's * O * (N) para mostrar a diferença relativa, porque para qualquer N, o primeiro algoritmo será sempre o dobro o tempo de execução do segundo; no entanto, ao comparar com uma função de uma família de complexidade diferente, como * O * (NlogN), os coeficientes não importam.
29412 KeithS
10

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'}




insira a descrição da imagem aqui

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

Vaibhav Agarwal
fonte
Nesse caso, para todo O (n) também é Big theta de n, pois, conforme a definição de alguma constante, será um limite inferior e, para alguma constante, é um limite superior. por exemplo 6n + 4 também é um teta grande (n), pois quando c é menor que 10, é sempre o limite inferior. e quando c é maior que 10, é um limite superior. Então, podemos dizer que, para qualquer notação Big Oh, também é um Big Theta?
Pradeep
1
Você está dizendo o contrário: "Big Theta significa Big Oh". E Big-Oh pode ser substituído por Big-Theta para limites assintoticamente apertados.
Vaibhav Agarwal
9

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.

theD
fonte
1

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

Mitch
fonte
1

(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!!!

Briguy37
fonte
Oi, boa explicação. Eu ainda tenho algumas dúvidas. 1. Não podemos transformar 6n + 4 em O (4), pois existe um valor variável 'n'. Essa é a resposta? 2. enquanto simplificação, você escolheu c = 7 e calculou correspondentemente n0 a 4. O que levou a decidir c = 7 e não menos que 7? porque com base no valor de c, o n0 será alterado.
Pradeep
@ Pradeep: Para 1, você está correto. Para uma explicação mais profunda: se tentarmos O(4), isso tornaria nossa equação de desigualdade c*4 >= 6n+4e, para qualquer uma cque escolhemos, sempre poderíamos encontrar um valor em que todos os valores nacima que tornariam a desigualdade falsa.
Briguy37
@ Pradeep: Para 2, os valores reais ce n0não são importantes. O que é importante é que n0existe para o cque escolhemos. Para que isso seja verdade, o lado esquerdo da desigualdade deve aumentar mais rápido que o lado direito para valores grandes de n. c=6não é bom para isso ( 6n >= 6n+4nunca é verdade), então eu escolhi c=7. Eu poderia ter apenas como facilmente escolhido c=10, c=734ou c=6.0000001e ainda teria sido capaz de ver que havia alguns n0que existia para fazer a desigualdade verdadeiro para n >= n0, o que significa que o Big Oh estamos testando é válido.
Briguy37
Obrigado pela explicação clara. Era exatamente isso que eu estava procurando. Obrigado mais uma vez.
Pradeep
@Pradeep: Ainda bem que pude ajudar :)
Briguy37
1

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

tempestade
fonte