Pergunta

Se eu tiver um algoritmo que leva 4n^2 + 7n move-se para realizar, qual é O seu?O(4n^2)?O(n^2)?

Eu sei que 7n é cortado, mas eu não sei se eu deveria manter a n^2 coeficiente ou não.

Obrigado

Foi útil?

Solução

Você deve abandonar qualquer coeficiente, porque a pergunta está realmente perguntando "na ordem de", que tenta caracterizá -la como linear, exponencial, logarítmica, etc ... isto é, quando n é muito grande, o coeficiente é de pouca importância.

Isso também explica por que você solta o +7n, porque quando n é muito grande, esse termo tem relativamente pouco significado para a resposta final. Se você estiver familiarizado com o cálculo, pode dizer limpo n-> inf (4*n^2+7n) ~ = lim n-> inf (4*n^2) ~ = lim n-> inf (n^2)

Você também pode pensar sobre isso em um sentido gráfico ... isto é, se você representar graficamente a função 4n^2 + 7n para valores cada vez maiores de n, um matemático pode dizer "parece n^2". É verdade que teria que ser um matemático bastante liberal, pois essa não é uma afirmação rigorosa, mas é basicamente o que O (...) está tentando transmitir.

Outras dicas

Os coeficientes não são relevantes na grande notação O, então é apenas O (n2). Como explica a Wikipedia:

...] Os coeficientes se tornam irrelevantes se compararmos a qualquer outra ordem de expressão, como uma expressão contendo um termo n3 ou n2.

Todos que estiverem lendo ou escrevendo sobre complexidade de algoritmos deve saber exatamente o que o Landau Símbolos e assimptótico notações são, caso contrário, eles não entendem o que está acontecendo, ou simplesmente ter uma aproximado (e muitas vezes enganosa) ideia.

Para simplificar (e muito), vamos f e g ser duas funções f : N -> N e g : N -> N.Dizemos que f is O(g) se, e somente se, existe uma constante M > 0 de tal forma que |f(n)| < M|g(n)|, para todos os n > M.Que é, de um modo mais informal, a partir de um grande valor de n, todos os valores f(n) são menores do que um múltiplo de g(n) (ou seja, g cresce mais rápido de f).

Essa definição é equivalente a

f is O(g) <==> There is K >= 0 such that lim{n -> +oo} |f(n)|/|g(n)| = K

Então, vamos dar f(n) = 4n^2 + 7n e g(n) = n^2, e tentar provar f is O(g) (Vou omitir {n -> +oo}):

lim |f(n)|/|g(n)| = lim f(n)/g(n) = lim (4n^2 + 7n) / n^2 = 4 + lim 7n/n^2 =
                  = 4 + lim 7/n = 4 + 0 = 4

Isso implica que há uma M de tal forma que n > M ==> |f(n)| < M|g(n)|, e , assim, f is O(g).

Então, tecnicamente, é correto afirmar 4n^2 + 7n is O(4n^2), como é correto dizer que 4n^2 + 7n is O(n^3), 4n^2 + 7n is O(e^n), e assim por diante.Mas, para ser significativa, estamos interessados no limite inferior.Por isso, se f is O(e^n) e f is O(n^2), estamos mais interessados em saber o que f is O(n^2), uma vez que este é muito mais restritivo.

Nota MUITO IMPORTANTE

O que é extremamente importante na escolha de um algoritmo é entender que grande-O notações refere-se a assimptótico casos, isto é, quando você considere extremamente, inimaginável enorme entradas, que podem ir bem além do poder computacional disponível no universo conhecido (ou seja, infinito conjuntos de entrada, expressa matematicamente por {n -> +oo}).

Para usos práticos (ou seja, não então, enormes entradas), quando a escolha de um algoritmo, com certeza, você vai observar candidato algoritmos grande-O notações, mas você deve ter certeza de que o escolhido algoritmo é bem adaptado e melhor desempenho) para o (esperado) de entrada.

Finalmente, geralmente melhor desempenho de algoritmos são mais difíceis de entender e implementar corretamente.Você deve considerar este fato, bem como quando a escolha de um algoritmo (ou seja, é a hora eu vou passar a depuração e a fixação de meu implementação este algoritmo consideravelmente superior ao tempo eu teria de esperar com outro algoritmo, com a pior big-O a notação?.Se assim for, você deve considerar o mais simples, menos eficiente do algoritmo, como a solução geral seria mais eficiente).

É O (n^2). Fatores constantes "mudam para o O". Você mantém apenas o maior expoente, pois esse é o que está dominando. E você pode deixar os coeficientes de fora, pois, ao comparar algoritmos diferentes, mesmo coeficientes muito grandes resultam em números totais menores do que ter um expoente maior (com n grande o suficiente).

Uma declaração como

4n² + 7n = O(n²)

significa que para algum multiplicador constante c, a expressão cn² acabará por ultrapassar 4n² + 7n. Tecnicamente não é incorreto deixar o coeficiente lá - O(n²) e O(4n²) significa exatamente a mesma coisa, porque qualquer constante c pois o primeiro pode ser substituído por c/4 para o último. No entanto, isso é menos claro, possivelmente enganador e definitivamente fora do padrão.

Matematicamente falando, você escreveria O (4n²). Isso significa que a função de complexidade de seus algoritmos se comporta como n-> 4n² em direção a infinito positivo.

Mas na ciência da computação/algoritmo, você apenas escreveria O (N²), o que é suficiente para categorizar seu algoritmo.

Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top