diff options
Diffstat (limited to 'pt-br/asymptoticnotation-pt.html.markdown')
| -rw-r--r-- | pt-br/asymptoticnotation-pt.html.markdown | 161 |
1 files changed, 0 insertions, 161 deletions
diff --git a/pt-br/asymptoticnotation-pt.html.markdown b/pt-br/asymptoticnotation-pt.html.markdown deleted file mode 100644 index c5299a11..00000000 --- a/pt-br/asymptoticnotation-pt.html.markdown +++ /dev/null @@ -1,161 +0,0 @@ ---- -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) |