b'\n_START_ARTICLE_\nGrande-O\n_START_PARAGRAPH_\nNa matem\xc3\xa1tica, a nota\xc3\xa7\xc3\xa3o O-grande descreve o comportamento limitante de uma fun\xc3\xa7\xc3\xa3o quando o argumento tende a um valor espec\xc3\xadfico ou para o infinito, normalmente, em termos de fun\xc3\xa7\xc3\xb5es mais simples. \xc3\x89 membro de uma fam\xc3\xadlia maior de nota\xc3\xa7\xc3\xb5es conhecida como nota\xc3\xa7\xc3\xa3o Landau, nota\xc3\xa7\xc3\xa3o Bachmann\xe2\x80\x93Landau (nomeada dessa forma por conta de Edmund Landau e Paul Bachmann), ou nota\xc3\xa7\xc3\xa3o assint\xc3\xb3tica.   Em ci\xc3\xaancia da computa\xc3\xa7\xc3\xa3o, o O-grande \xc3\xa9 usado para classificar algoritmos pela forma como eles respondem (ex., no tempo de processamento ou espa\xc3\xa7o de trabalho requerido) a mudan\xc3\xa7as no tamanho da entrada. Na teoria anal\xc3\xadtica dos n\xc3\xbameros, \xc3\xa9 usado para estimar o "erro cometido" quando se substitui o tamanho assint\xc3\xb3tico, ou o tamanho assint\xc3\xb3tico m\xc3\xa9dio, de uma fun\xc3\xa7\xc3\xa3o aritm\xc3\xa9tica, pelo valor, ou pelo valor m\xc3\xa9dio, que ela recebe num argumento grande e finito. Um exemplo famoso \xc3\xa9 o problema de estimar o termo restante no teorema do n\xc3\xbamero primo._NEWLINE_A nota\xc3\xa7\xc3\xa3o O-grande caracteriza fun\xc3\xa7\xc3\xb5es de acordo com suas taxas de crescimento: fun\xc3\xa7\xc3\xb5es diferentes com as mesmas taxas de crescimento t\xc3\xaam a mesma nota\xc3\xa7\xc3\xa3o O-grande. A letra O \xc3\xa9 usada porque a taxa de crescimento de uma fun\xc3\xa7\xc3\xa3o tamb\xc3\xa9m \xc3\xa9 referenciada como a ordem de uma fun\xc3\xa7\xc3\xa3o. Uma descri\xc3\xa7\xc3\xa3o de uma fun\xc3\xa7\xc3\xa3o em termos de O-grande normalmente prov\xc3\xaa um limite superior na taxa de crescimento da fun\xc3\xa7\xc3\xa3o. Associada a nota\xc3\xa7\xc3\xa3o O-grande existem v\xc3\xa1rias outras nota\xc3\xa7\xc3\xb5es, usando os s\xc3\xadmbolos o, \xce\xa9, \xcf\x89, e \xce\x98, para descrever outros tipos de relacionamento com taxas de crescimento assint\xc3\xb3ticas._NEWLINE_A nota\xc3\xa7\xc3\xa3o O-grande \xc3\xa9 tamb\xc3\xa9m usada por muitos campos para prover estimativas similares.\n_START_SECTION_\nUtiliza\xc3\xa7\xc3\xa3o\n_START_PARAGRAPH_\nA nota\xc3\xa7\xc3\xa3o O-grande possui duas grandes \xc3\xa1reas de aplica\xc3\xa7\xc3\xa3o. Em matem\xc3\xa1tica, \xc3\xa9 comumente usada para descrever o qu\xc3\xa3o perto uma s\xc3\xa9rie finita se aproxima de uma fun\xc3\xa7\xc3\xa3o, especialmente no caso de uma S\xc3\xa9rie de Taylor truncada ou uma expans\xc3\xa3o assint\xc3\xb3tica. Em ci\xc3\xaancia da computa\xc3\xa7\xc3\xa3o, \xc3\xa9 \xc3\xbatil na an\xc3\xa1lise de algoritmos. Em ambas aplica\xc3\xa7\xc3\xb5es, a fun\xc3\xa7\xc3\xa3o g(x) que aparece com o O(...) \xc3\xa9 tipicamente a mais simples poss\xc3\xadvel, omitindo fatores constantes e termos de mais  baixa ordem._NEWLINE_Existem dois usos formalmente parecidos, mas visivelmente diferentes, dessa nota\xc3\xa7\xc3\xa3o: comportamento assint\xc3\xb3tico no infinito e comportamento assint\xc3\xb3tico infinitesimal. Essa distin\xc3\xa7\xc3\xa3o \xc3\xa9 s\xc3\xb3 na aplica\xc3\xa7\xc3\xa3o, mas n\xc3\xa3o no princ\xc3\xadpio, por\xc3\xa9m, a defini\xc3\xa7\xc3\xa3o formal de O-grande \xc3\xa9 a mesma para ambas as classes, mudando somente os limites para o argumento da fun\xc3\xa7\xc3\xa3o.\n_START_SECTION_\nSinal de igualdade\n_START_PARAGRAPH_\nA afirma\xc3\xa7\xc3\xa3o "f(x) \xc3\xa9 O(g(x))" como definido acima \xc3\xa9 frequentemente escrita como f(x)\xc2\xa0=\xc2\xa0O(g(x)). Alguns consideram isso como sendo um abuso de nota\xc3\xa7\xc3\xa3o, desde que o uso de sinais de igualdade poderiam levar a poss\xc3\xadveis erros, ao passo que ela sugere uma simetria que a afirma\xc3\xa7\xc3\xa3o n\xc3\xa3o carrega. Como de Bruijn disse, O(x)\xc2\xa0=\xc2\xa0O(x\xc2\xb2) \xc3\xa9 verdade, por\xc3\xa9m O(x\xc2\xb2)\xc2\xa0=\xc2\xa0O(x) n\xc3\xa3o \xc3\xa9. Knuth descreve essas afirma\xc3\xa7\xc3\xb5es como "igualdades de caminho \xc3\xbanico", desde que os lados n\xc3\xa3o podem ser revertidos, "n\xc3\xb3s poder\xc3\xadamos deduzir coisas rid\xc3\xadculas como n\xc2\xa0=\xc2\xa0n\xc2\xb2 das identidades n\xc2\xa0=\xc2\xa0O(n\xc2\xb2) e n\xc2\xb2\xc2\xa0=\xc2\xa0O(n\xc2\xb2)."_NEWLINE_Por essas raz\xc3\xb5es, seria mais preciso usar a nota\xc3\xa7\xc3\xa3o de conjuntos e escrever f(x)\xc2\xa0\xe2\x88\x88\xc2\xa0O(g(x)), pensando em O(g(x)) como a classe de todas as fun\xc3\xa7\xc3\xb5es h(x) tais que |h(x)|\xc2\xa0\xe2\x89\xa4\xc2\xa0C|g(x)| para alguma constante C. No entanto, o uso do sinal de igual \xc3\xa9 habitual. Knuth destacou que "os matem\xc3\xa1ticos costumam usar o sinal = como eles usam a palavra \'\xc3\xa9\' em Ingl\xc3\xaas: Arist\xc3\xb3teles \xc3\xa9 um homem, mas um homem n\xc3\xa3o \xc3\xa9 necessariamente Arist\xc3\xb3teles."\n_START_SECTION_\nExemplo\n_START_PARAGRAPH_\nSuponha que um algoritmo est\xc3\xa1 sendo desenvolvido para operar num conjunto de n elementos. Seus desenvolvedores est\xc3\xa3o interessados em encontrar uma fun\xc3\xa7\xc3\xa3o T(n)  que expresse quanto tempo o algoritmo vai levar para rodar (numa medida arbitr\xc3\xa1ria de tempo)  em termos do n\xc3\xbamero de elementos no conjunto da entrada. O algoritmo funciona primeiro chamando uma sub-rotina que ordena os elementos no conjunto e ent\xc3\xa3o executa suas pr\xc3\xb3prias opera\xc3\xa7\xc3\xb5es. A ordena\xc3\xa7\xc3\xa3o tem uma complexidade de tempo conhecida de O(n\xc2\xb2), e depois da sub-rotina, o algoritmo deve executar 55n\xc2\xb3\xc2\xa0+\xc2\xa02n\xc2\xa0+\xc2\xa010 passos adicionais antes de terminar.  Assim a complexidade de tempo deram do algoritmo pode ser expressa como T(n) = 55n\xc2\xb3\xc2\xa0+\xc2\xa0O(n\xc2\xb2)._NEWLINE_Aqui os termos 2n+10 est\xc3\xa3o submissos ao crescimento mais r\xc3\xa1pido O(n\xc2\xb2). Novamente, essa utiliza\xc3\xa7\xc3\xa3o desconsidera alguns dos significados formais do s\xc3\xadmbolo "=", mas permite que se use a nota\xc3\xa7\xc3\xa3o O-grande como uma esp\xc3\xa9cie de marcador de posi\xc3\xa7\xc3\xa3o conveniente.\n_START_SECTION_\nNota\xc3\xa7\xc3\xb5es assint\xc3\xb3ticas relacionadas\n_START_PARAGRAPH_\nO-grande \xc3\xa9 a nota\xc3\xa7\xc3\xa3o assint\xc3\xb3tica mais utilizada para compara\xc3\xa7\xc3\xa3o de fun\xc3\xa7\xc3\xb5es, por\xc3\xa9m em muitos casos pode ser substitu\xc3\xadda por Theta-grande \xce\x98 para limites mais apertados. Aqui n\xc3\xb3s definiremos algumas nota\xc3\xa7\xc3\xb5es relacionadas em termos de O-grande, avan\xc3\xa7ando at\xc3\xa9 a fam\xc3\xadlia de nota\xc3\xa7\xc3\xb5es de Bachmann-Landau, da qual a nota\xc3\xa7\xc3\xa3o O-grande pertence.'