Big O Pergunta sobre um algoritmo com (n ^ 2 + n) / 2 de taxa de crescimento

16

Estou fazendo essa pergunta porque estou confuso sobre um aspecto da grande notação O.

Estou usando o livro Data Structures and Abstractions with Java de Frank Carrano. No capítulo sobre "Eficiência de algoritmos", ele mostra o seguinte algoritmo:

int sum = 0, i = 1, j = 1
for (i = 1 to n) {
    for (j = 1 to i)
        sum = sum + 1
}

Ele inicialmente descreve esse algoritmo como tendo uma taxa de crescimento de (n 2  + n) / 2 . Que olhar parece intuitivo.

No entanto, é então afirmado que (n 2  + n) / 2 se comporta como n 2 quando n é grande. No mesmo parágrafo ele afirma (n 2  + n) / 2 também se comporta como n 2 / 2 . Ele usa isso para classificar o algoritmo acima como O (n 2 ) .

Eu entendo isso (n 2  + n) / 2 é semelhante ao n 2 / 2 porque percentualmente, n faz pouca diferença. O que eu não entendo é por que (n 2  + n) / 2 e n 2 são semelhantes, quando n é grande.

Por exemplo, se n = 1.000.000 :

(n^2 + n) / 2 =  500000500000 (5.000005e+11)
(n^2) / 2     =  500000000000 (5e+11)
(n^2)         = 1000000000000 (1e+12)

Esse último não é nada parecido. De fato, obviamente, é o dobro do meio. Então, como Frank Carrano pode dizer que são semelhantes? Além disso, como o algoritmo é classificado como O (n 2 ) . Olhando para esse loop interno, eu diria que era n 2 + n / 2

Andrew S
fonte
Se você estiver interessado eu tinha dado uma resposta para três loops aninhados com árvore de execução verificação diagrama Um quebra-cabeça relacionadas com loops aninhados
Grijesh Chauhan
1
basicamente, a idéia é que, à medida que ncresce, tanto as funções 'n ^ 2' quanto a sua função se comportam de maneira semelhante, há uma constante desconfiança em sua taxa de crescimento. Se você tem uma expressão complexa, a função que cresce mais rapidamente domina.
AK_
1
@ MichaelT: Eu não acho que seja uma duplicata dessa pergunta, pois a outra é apenas uma questão de contagem incorreta. Essa é uma pergunta mais sutil sobre por que os termos menores (especificamente, multiplicadores constantes e polinômios de menor grau) são ignorados. Aparentemente, o questionador aqui já entende o problema levantado na outra questão, e uma resposta que é suficiente para essa pergunta não responderá a essa.
sdenham

Respostas:

38

Ao calcular a complexidade Big-O de um algoritmo, o que está sendo mostrado é o fator que dá a maior contribuição ao aumento no tempo de execução se o número de elementos em que você executa o algoritmo aumenta.

Se você tiver um algoritmo com complexidade de (n^2 + n)/2e duplicar o número de elementos, a constante 2não afeta o aumento no tempo de execução, o termo ncausa uma duplicação no tempo de execução e o termo n^2causa um aumento de quatro vezes na execução Tempo.
Como o n^2termo tem a maior contribuição, a complexidade do Big-O é O(n^2).

Bart van Ingen Schenau
fonte
2
Eu gosto disso, está ficando um pouco mais claro.
Andrew S
7
Isso é muito ondulado. Pode ser verdadeiro ou falso. Se você puder fazer uma pequena quantidade de matemática, veja uma das respostas abaixo.
usr
2
Esse raciocínio é muito vago: significaria que poderíamos concluir isso O(n * log n) = O(n), o que não é verdade.
CFH
Pode não ser a resposta mais precisa ou a mais semanticamente correta, mas o importante aqui é que isso me levou a começar a entender o ponto central e acho que esse era o objetivo do autor. É deliberadamente vago, pois os detalhes costumam desviar os princípios básicos. É importante ver a madeira para as árvores.
21715 Andrew S
Bart estava realmente falando sobre termos, não fatores. Entendendo isso, não podemos concluir isso O(n * log n) = O(n). Eu acho que isso dá uma boa explicação da lógica por trás da definição.
MarkFoskey #
10

A definição é que

f(n) = O(g(n))

se existe alguma constante C> 0 tal que, para todos os n maiores que alguns n_0, temos

|f(n)| <= C * |g(n)|

Isso é claramente verdadeiro para f (n) = n ^ 2 eg (n) = 1/2 n ^ 2, onde a constante C deve ser 2. Também é fácil ver que isso é verdade para f (n) = n ^ 2 e g (n) = 1/2 (n ^ 2 + n).

cfh
fonte
4
"Se existe alguma constante C> 0 tal que, forr todos n", deve ser "Se houver algumas constantes C, n_0 tal que, para todas as n> n_0"
Taemyr 20/04/2015
@ Taemyr: Desde que a função gseja diferente de zero, isso na verdade não é necessário, pois você sempre pode aumentar a constante C para tornar a declaração verdadeira para os finitos muitos primeiros valores de n_0.
CFH
Não, enquanto estivermos olhando para funções, não há um número finito de valores potenciais de n_0.
Taemyr
@ Taemyr: n_0 é um número finito. Escolha C = max {f (i) / g (i): i = 1, ..., n_0} e a instrução sempre será válida para os primeiros n_0 valores, como você pode verificar facilmente.
CFH
No CS, isso é menos preocupante, porque n geralmente é tamanho de entrada e, portanto, discreto. Nesse caso, pode-se escolher C de modo que n_0 = 1 funcione. Mas a definição formal é n maior que um limite, o que elimina um monte de detalhes na aplicação da definição.
Taemyr
6

Ao falar sobre complexidade, você está interessado apenas nas mudanças de fator de tempo com base no número de elementos ( n).

Como tal, você pode remover qualquer fator constante (como o 2aqui).

Isso deixa você com O(n^2 + n).

Agora, para um tamanho razoável, no produto, ou seja n * n, será significativamente maior do que apenas n, e é por isso que você também pode pular essa parte, o que deixa você com uma complexidade final de O(n^2).

É verdade que, para números pequenos, haverá uma diferença significativa, mas isso se torna mais marginal, quanto maior o seu número n.

Mario
fonte
Qual é o tamanho de n para que a diferença se torne marginal? Além disso, por que o / 2 é removido, sua existência reduz pela metade o valor?
Andrew S
6
@ Andrews Porque Big O Notation fala sobre crescimento. Dividir por 2 é irrelevante fora do contexto de benchmarks e timestamps porque, em última análise, não altera a taxa de crescimento. O maior componente, no entanto, faz e é isso que você mantém.
21415 Neil
2
@ Niel, brilhante, tão claro. Eu gostaria que os livros colocassem assim. Às vezes, acho que os autores sabem demais que esquecem que os meros mortais não possuem seu conhecimento funcional e, portanto, não fazem pontos importantes claros; em vez disso, enterram-no em alguma descrição matemática formal ou omitem tudo juntos, acreditando que esteja implícito.
Andrew S
Eu gostaria de poder votar esta resposta mais de uma vez! @ Neil, você deveria escrever os livros da Big O.
Tersosauros
3

Não é que "(n² + n) / 2 se comporte como n² quando n for grande", é que (n² + n) / 2 cresça como n² à medida que n aumenta .

Por exemplo, conforme n aumenta de 1.000 para 1.000.000

(n² + n) / 2  increases from  500500 to  500000500000
(n²) / 2      increases from  500000 to  500000000000
(n²)          increases from 1000000 to 1000000000000

Da mesma forma, à medida que n aumenta de 1.000.000 para 1.000.000.000

(n² + n) / 2  increases from  500000500000 to  500000000500000000
(n²) / 2      increases from  500000000000 to  500000000000000000
(n²)          increases from 1000000000000 to 1000000000000000000

Eles crescem da mesma forma, e é disso que trata o Big O Notation.

Se você plotar (n² + n) / 2 e n² / 2 no Wolfram Alpha , eles são tão semelhantes que são difíceis de distinguir por n = 100. Se você traçar todos os três no Wolfram Alpha , verá duas linhas separadas por um fator constante de 2.

ShadSterling
fonte
Isso é bom, deixa muito claro para mim. Obrigado por responder.
21815 Andrew S
2

Parece que você precisa trabalhar um pouco mais a grande notação O. Quão conveniente é essa notação, é muito enganosa por causa do uso de um sinal de igual, que não é usado aqui para denotar a igualdade de funções.

Como você sabe, essa notação expressa comparações assintóticas de funções, e escrever f = O (g) significa que f (n) cresce no máximo tão rápido quanto g (n) quanto n vai ao infinito. Uma maneira simples de traduzir isso é dizer que a função f / g é limitada. Mas é claro, temos que cuidar dos lugares onde g é zero e acabamos com a definição mais robusta que você pode ler em quase todos os lugares .

Essa notação acaba sendo muito conveniente para a computação - é por isso que é tão difundida - mas deve ser tratada com cuidado, pois o sinal de igual que vemos ali não denota uma igualdade de funções . É como dizer que 2 = 5 mod 3 não implica que 2 = 5 e se você gosta de álgebra, pode realmente entender a grande notação O como um módulo de igualdade.

Agora, voltando à sua pergunta específica, é totalmente inútil calcular alguns valores numéricos e compará-los: por maior que seja um milhão, ele não explica o comportamento assintótico. Seria mais útil a proporção trama das funções f (n) = n (n-1) / 2 e g (n) = N² - mas, neste caso especial, podemos ver imediatamente que f (n) / g (n) é menor que 1/2 se n> 0, o que implica que f = O (g) .

Para melhorar sua compreensão da notação, você deve

  • Trabalhe com uma definição limpa, não com uma impressão confusa, com base em coisas semelhantes - como você a experimentou, essa impressão confusa não funciona bem.

  • Tire algum tempo para elaborar exemplos em detalhes. Se você elaborar apenas cinco exemplos em uma semana, será suficiente para melhorar sua confiança. Este é um esforço que definitivamente vale a pena.


Nota lateral algébrica Se A é a álgebra de todas as funções Ν → Ν e C a subalgebra de funções delimitadas, dada uma função f, o conjunto de funções pertencentes a O (f) é um módulo C de A e as regras de computação no grande A notação descreve apenas como A opera nesses submódulos. Assim, a igualdade que vemos é uma igualdade dos módulos C de A , este é apenas outro tipo de módulo.

Michael Le Barbier Grünewald
fonte
1
É difícil seguir esse artigo da Wikipedia após o primeiro pequeno pedaço. Foi escrito para matemáticos talentosos por matemáticos talentosos e não é o tipo de texto introdutório que eu esperaria de um artigo enciclopédico. Obrigado pela sua compreensão, embora seja tudo de bom.
Andrew S
Você superestima o nível no texto da Wikipedia! :) Não é tão bem escrito, com certeza. Graham, Knuth e Patashnik escreveram um livro adorável "Concrete Mathematics" para estudantes do ensino médio. Você também pode tentar "a arte da programação de computadores" ou um livro de teoria dos números escrito nos anos 50 (Hardy & Wright, Rose), pois eles geralmente têm como alvo o nível de estudante do ensino médio. Você não precisa ler o livro completo. Se você escolher um, apenas a parte sobre assintótica! Mas antes você precisa decidir o quanto precisa entender. :)
Michael Le Barbier Grünewald
1

Eu acho que você entende mal o que significa a grande notação O.

Quando você vê O (N ^ 2), significa basicamente: quando o problema fica 10 vezes maior, o tempo para resolvê-lo será: 10 ^ 2 = 100 vezes maior.

Vamos perfurar 1000 e 10000 na sua equação: 1000: (1000 ^ 2 + 1000) / 2 = 500500 10000: (10000 ^ 2 + 10000) / 2 = 50005000

50005000/500500 = 99,91

Assim, enquanto o N ficou 10 vezes maior, as soluções ficaram 100 vezes maiores. Portanto, ele se comporta: O (N ^ 2)

Pieter B
fonte
1

se n fosse um 1,000,000então

(n^2 + n) / 2  =  500000500000  (5.00001E+11)
(n^2) / 2      =  500000000000  (5E+11)
(n^2)          = 1000000000000  (1E+12)

1000000000000.00 o que?

Embora a complexidade nos forneça uma maneira de prever um custo do mundo real (segundos ou bytes, dependendo de estarmos falando sobre complexidade de tempo ou complexidade de espaço), ela não nos dá um número de segundos ou qualquer outra unidade específica.

Isso nos dá um grau de proporção.

Se um algoritmo precisar fazer algo n² vezes, será necessário n² × c para algum valor de c, que é quanto tempo leva cada iteração.

Se um algoritmo tiver que fazer algo n² ÷ 2 vezes, será necessário n² × c para algum valor de c que seja duas vezes maior que cada iteração.

De qualquer forma, o tempo gasto ainda é proporcional a n².

Agora, esses fatores constantes não são algo que podemos simplesmente ignorar; de fato, você pode ter um caso em que um algoritmo com complexidade O (n²) se sai melhor que um com complexidade O (n), porque se estamos trabalhando em um pequeno número de itens, o impacto dos fatores de consentimento é maior e pode superar outras preocupações . (De fato, mesmo O (n!) É o mesmo que O (1) para valores suficientemente baixos de n).

Mas não é disso que a complexidade nos fala.

Na prática, existem algumas maneiras diferentes de melhorar o desempenho de um algoritmo:

  1. Melhore a eficiência de cada iteração: O (n²) ainda é executado em n² × c segundos, mas c é menor.
  2. Reduza o número de casos vistos: O (n²) ainda é executado em n² × c segundos, mas n é menor.
  3. Substitua o algoritmo por um que tenha os mesmos resultados, mas menor complexidade: por exemplo, se pudéssemos repetir algo O (n²) para algo O (n log n) e, portanto, alteramos de n² × c₀ segundos para (n log n) × c₁ segundos .

Ou, de outra forma, temos f(n)×calguns segundos sendo usados ​​e você pode melhorar o desempenho reduzindo c, reduzindo nou reduzindo o fretorno de um determinado produto n.

O primeiro podemos fazer por algumas micro-opções dentro de um loop ou usando um hardware melhor. Sempre dará uma melhoria.

O segundo que podemos fazer talvez seja identificar um caso em que possamos interromper o algoritmo antes que tudo seja examinado ou filtrar alguns dados que não serão significativos. Não proporcionará uma melhoria se o custo de fazer isso exceder o ganho, mas geralmente será uma melhoria maior que o primeiro caso, especialmente com um n grande.

O terceiro que podemos fazer usando um algoritmo completamente diferente. Um exemplo clássico seria substituir uma classificação de bolha por uma classificação rápida. Com baixo número de elementos, podemos ter piorado as coisas (se c₁ for maior que c₀), mas geralmente permite os maiores ganhos, especialmente com n muito grande.

No uso prático, as medidas de complexidade permitem-nos raciocinar sobre as diferenças entre algoritmos precisamente porque ignoram a questão de como reduzir n ou c ajudará, a se concentrar em examinar f()

Jon Hanna
fonte
"O (n!) É o mesmo que O (1) para valores suficientemente baixos de n" está errado. Tem que haver uma maneira melhor de explicar que "quando né mantido suficientemente baixo, o Big-O não importa".
Ben Voigt
@BenVoigt Eu ainda não encontrei um com o mesmo impacto retórico que isso teve quando o li pela primeira vez; não é originalmente minha, roubei de Eric Lippert, que pode ter se originado ou tirado de outra pessoa. Obviamente, ele faz referência a piadas como "π é igual a 3 para valores pequenos de π e valores grandes de 3", que ainda são mais antigos.
Jon Hanna
0

Fator constante

O ponto da grande notação O é que você pode escolher um fator constante arbitrariamente grande para que O (função (n)) seja sempre maior que a função C * (n). Se o algoritmo A for um bilhão de vezes mais lento que o algoritmo B, eles terão a mesma complexidade O, desde que essa diferença não cresça quando n crescer arbitrariamente grande.

Vamos assumir um fator constante de 1000000 para ilustrar o conceito - é um milhão de vezes maior que o necessário, mas isso ilustra o ponto em que eles são considerados irrelevantes.

(n ^ 2 + n) / 2 "cabe dentro" O (n ^ 2) porque para qualquer n, não importa o tamanho, (n ^ 2 + n) / 2 <1000000 * n ^ 2.

(n ^ 2 + n) / 2 "não se encaixa" em um conjunto menor, por exemplo, O (n) porque para alguns valores (n ^ 2 + n) / 2> 1000000 * n.

Os fatores constantes podem ser arbitrariamente grandes - um algoritmo com tempo de execução de n anos tem O (n) complexidade que é "melhor" que um algoritmo com tempo de execução de n * log (n) microssegundos.

Peter é
fonte
0

Big-O é sobre "quão complicado" é um algoritmo. Se você tiver dois algoritmos, e um leva n^2*ksegundos para ser executado e o outro leva n^2*jsegundos para ser executado, você pode argumentar sobre qual é o melhor e poderá fazer algumas otimizações interessantes para tentar afetar kou j, mas ambos esses algoritmos são muito lentos comparados a um algoritmo que leva n*mpara ser executado. Não importa quão pequeno você faça as constantes kou j, para uma entrada grande o suficiente, o n*malgoritmo sempre vencerá, mesmo que mseja bastante grande.

Então, chamamos os dois primeiros algoritmos O(n^2)e o segundo O(n). Divide bem o mundo em classes de algoritmos. É disso que se trata o big-O. É como dividir veículos em carros, caminhões e ônibus, etc. Há muita variação entre carros, e você pode passar o dia todo discutindo se um Prius é melhor que um Chevy Volt, mas no final do dia, se você precisa colocar 12 pessoas em uma, então esse é um argumento bastante sem sentido. :)

Jason Walton
fonte