1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
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)
|
