-
Notifications
You must be signed in to change notification settings - Fork 0
/
anotações.txt
56 lines (37 loc) · 2.58 KB
/
anotações.txt
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
(ANOTAÇÕES QUE ACHEI IMPORTANTE DECORAR)
-- Capítulo 1 --
[Pesquisa Binária]
Pesquisa Binária:
Você chuta um número intermediário e elimina a metade dos números restantes a cada vez.
Se ele encontrar o valor, ele o retorna, se não, ele retorna nulo.
OBS1: Elimina metade dos números a cada tentativa.
OBS2: A pesquisa binária só funciona se sua lista está ordenada.
[Tempo de Execução]
Tempo de execução linear é quando o número de tentativas é igual ao tamanho da lista.
A pesquisa binária é executada com tempo logarítmico.
[Notação Big O]
Notação Big O é uma notação especial que diz o quão rápido é um algoritmo.
Permite que você compare o número de operações.
Exemplos comuns de tempo de execução Big O:
O(n): O tempo de execução simples ou tempo linear na notação Big O é O(n). [N é o tamanho da lista, ou seja, o número de operações]
O(log n): O tempo de execução logáritmica da notação big O é O(log n).
O(n* log n): Algoritmo rápido de ordenação, como a ordenação quicksort.
O(n^2): Algoritmo lento de ordenação, como a ordenação por seleção.
O(n!): Algoritmo bastante lento, como o do caixeiro viajante. É conhecido como tempo fatorial, pois n! é o fatorial de n.
A notação Big O é escita da seguinte forma:
"BIG O" -> O(n) <= Número de operações
Isso fornece o número de operações que um algoritmo realiza.
É chamado de notação big O pq coloca-se um "grande O" na frente do número de operações.
A Notação Big O leva em conta a pior das hipóteses.
* A rapidez de um algoritmo não é medida em segundos, mas pelo crescimento do número de operações.
* Em vez disso, discutimos sobre o quão rapidamente o tempo de execução de um algortimo aumenta confome
o número de elementos aumenta.
* O tempo de execução em algoritmos é expresso na notação big O.
* O(log n) é mais rápido que O(n), e O(log n) fica ainda mais rápido conforme a lista aumenta.
FINAL: Se quiser, leia sobre árvores binárias de busca.
RECAPITULANDO:
A pesquisa binária é m uito mais rápida do que a pesquisa simples.
O(log n) é mais rápido que O(n), e O(log n) fica ainda mais rápido conforme o elementos da lista aumentam.
A rapidez de um algoritmo não é medida em segundos, e sim em quantidade de operações, em outras palavras, por meio do seu crescimento.
O tempo de execução dos algoritmos é expresso na notação Big O.
-- Capítulo 2 --