diff options
Diffstat (limited to 'pt-br')
| -rw-r--r-- | pt-br/asymptoticnotation-pt.html.markdown | 161 |
1 files changed, 161 insertions, 0 deletions
diff --git a/pt-br/asymptoticnotation-pt.html.markdown b/pt-br/asymptoticnotation-pt.html.markdown new file mode 100644 index 00000000..c5299a11 --- /dev/null +++ b/pt-br/asymptoticnotation-pt.html.markdown @@ -0,0 +1,161 @@ +--- +category: Algorithms & Data Structures +name: Asymptotic Notation +contributors: + - ["Jake Prather", "http://github.com/JakeHP"] +translators: + - ["Carolina Knoll", "http://github.com/carolinaknoll"] +lang: pt-br +--- + +# Aprenda X em Y minutos +## Onde X=Notação Assintótica + +# Notações Assintóticas +## O que são? + +Notações assintóticas são notações matemáticas que nos permitem analisar tempo de execução +de um algoritmo, identificando o seu comportamento de acordo como o tamanho de entrada para +o algoritmo aumenta. Também é conhecido como taxa de "crescimento" de um algoritmo. O algoritmo +simplesmente se torna incrivelmente lento conforme o seu tamanho aumenta? Será que pode-se na +maior parte manter o seu tempo de execução rápido mesmo quando o tamanho de entrada aumenta? +A notação assintótica nos dá a capacidade de responder a essas perguntas. + +## Além desta, existem outras alternativas para responder a essas perguntas? + +Uma forma seria a de contar o número de operações primitivas em diferentes tamanhos de entrada. +Embora esta seja uma solução válida, a quantidade de trabalho necessário, mesmo para algoritmos +simples, não justifica a sua utilização. + +Outra maneira é a de medir fisicamente a quantidade de tempo que leva para se executar um algoritmo +de diferentes tamanhos. No entanto, a precisão e a relatividade (já que tempos obtidos só teriam +relação à máquina em que eles foram testados) deste método estão ligadas a variáveis ambientais, +tais como especificações de hardware, poder de processamento, etc. + +## Tipos de Notação Assintótica + +Na primeira seção deste documento nós descrevemos como uma notação assintótica identifica o comportamento +de um algoritmo como as alterações de tamanho de entrada (input). Imaginemos um algoritmo como uma função +f, n como o tamanho da entrada, e f (n) sendo o tempo de execução. Assim, para um determinado algoritmo f, +com tamanho de entrada n você obtenha algum tempo de execução resultante f (n). Isto resulta num gráfico, +em que o eixo Y representa o tempo de execução, o eixo X é o tamanho da entrada, e os pontos marcados são +os resultantes da quantidade de tempo para um dado tamanho de entrada. + +Pode-se rotular uma função ou algoritmo com uma notação assintótica de diversas maneiras diferentes. +Dentre seus exemplos, está descrever um algoritmo pelo seu melhor caso, pior caso, ou caso equivalente. +O mais comum é o de analisar um algoritmo pelo seu pior caso. Isso porque você normalmente não avaliaria +pelo melhor caso, já que essas condições não são as que você está planejando. Um bom exemplo disto é o de +algoritmos de ordenação; especificamente, a adição de elementos a uma estrutura de tipo árvore. O melhor +caso para a maioria dos algoritmos pode ser tão simples como uma única operação. No entanto, na maioria +dos casos, o elemento que você está adicionando terá de ser ordenado de forma adequada através da árvore, +o que poderia significar a análise de um ramo inteiro. Este é o pior caso, e é por ele que precisamos seguir. + +### Tipos de funções, limites, e simplificação + +``` +Função Logaritmica - log n +Função Linear - an + b +Função Quadrática - an^2 + bn + c +Função Polinomial - an^z + . . . + an^2 + a*n^1 + a*n^0, onde z é uma constante +Função Exponencial - a^n, onde a é uma constante +``` + +Estas são algumas classificações básicas de crescimento de função usados em várias notações. A lista +começa com a função crescimento mais lento (logarítmica, com tempo de execução mais rápido) e vai até +a mais rápida (exponencial, com tempo de execução mais lento). Observe que 'n', ou nossa entrada, +cresce em cada uma dessas funções, e o resultado claramente aumenta muito mais rapidamente em função +quadrática, polinomial e exponencial, em comparação com a logarítmica e a linear. + +Uma observação de boa importância é que, para as notações a serem discutidas, deve-se fazer o melhor +para utilizar termos mais simples. Isto significa desrespeitar constantes, e simplificar termos de +ordem, porque, como o tamanho da entrada (ou n no nosso f (n) exemplo) aumenta infinitamente (limites +matemáticos), os termos em ordens mais baixas e constantes são de pouca ou nenhuma importância. Dito +isto, se você possui constantes com valor 2^9001, ou alguma outra quantidade ridícula, inimaginável, +perceberá que a simplificação distorcerá a precisão de sua notação. + +Já que nós queremos a forma mais simples, vamos modificar nossas funções um pouco. + +``` +Logaritmica - log n +Linear - n +Quadrática - n^2 +Polinomial - n^z, onde z é uma constante +Exponencial - a^n, onde a é uma constante +``` + +### O Grande-O + +Grande-O, geralmente escrita como O, é uma Notação Assintótica para o pior caso para uma dada função. Digamos +que `f(n)` é o tempo de execução de seu algoritmo, e `g(n)` é uma complexidade de tempo arbitrário que você está +tentando se relacionar com o seu algoritmo. `f(n)` será O(g(n)), se, por qualquer constante real c (c > 0), +`f(n)` <= `c g(n)` para cada tamanho de entrada n (n > 0). + +*Exemplo 1* + +``` +f(n) = 3log n + 100 +g(n) = log n +``` + +É `f(n)` um O(g(n))? +É 3 `log n + 100` igual a O(log n)? +Vamos checar na definição de Grande-O. + +``` +3log n + 100 <= c * log n +``` + +Existe alguma constante c que satisfaça isso para todo n? + +``` +3log n + 100 <= 150 * log n, n > 2 (indefinido em n = 1) +``` + +Sim! A definição de Grande-O foi satisfeita. Sendo assim, `f(n)` é O(g(n)). + +*Exemplo 2* + +``` +f(n) = 3 * n^2 +g(n) = n +``` + +É `f(n)` um O(g(n))? +É `3 * n^2` um O(n)? +Vamos ver na definição de Grande-O. + +``` +3 * n^2 <= c * n +``` + +Existe alguma constante que satisfaça isso para todo n? +Não, não existe. `f(n)` NÃO É O(g(n)). + +### Grande-Omega + +Grande-Omega, comumente escrito como Ω, é uma Notação Assintótica para o melhor caso, ou +uma taxa de crescimento padrão para uma determinada função. + +`f(n)` é Ω(g(n)), se, por qualquer constante c real (c > 0), `f(n)` é >= `c g(n)` para cada +tamanho de entrada n (n > 0). + +Sinta-se livre para pesquisar recursos adicionais e obter mais exemplos sobre este assunto! +Grande-O é a notação primária utilizada para tempo de execução de algoritmos, de modo geral. + +### Notas de Finalização + +É complicado exibir este tipo de assunto de forma tão curta, então é definitivamente recomendado +pesquisar além dos livros e recursos on-line listados. Eles serão capazes de analisar o assunto com +uma profundidade muito maior, além de ter definições e exemplos. Mais sobre onde X="Algoritmos e +Estruturas de Dados" está a caminho: Haverá conteúdo focado na análise de exemplos de códigos reais +em breve. + +## Livros + +* [Algorithms] (http://www.amazon.com/Algorithms-4th-Robert-Sedgewick/dp/032157351X) +* [Algorithm Design] (http://www.amazon.com/Algorithm-Design-Foundations-Analysis-Internet/dp/0471383651) + +## Recursos Online + +* [MIT] (http://web.mit.edu/16.070/www/lecture/big_o.pdf) +* [KhanAcademy] (https://www.khanacademy.org/computing/computer-science/algorithms/asymptotic-notation/a/asymptotic-notation) |