Aula 4: Big-O e análise de complexidade

Imagine uma lista telefônica enorme e você está a procurar um nome: folhear página por página leva uma eternidade, mas uma lista em ordem alfabética oferece um jeito muito mais esperto de encontrar. Esta aula dá um nome curto a esse padrão — Big-O — uma forma prática de descrever como o trabalho cre

Big-O é simplesmente perguntar: 'se você dobrar o número de itens, quanto mais trabalho isso é?'. Se você passa por cada itnuma vez, dobrar os itens = o dobro do trabalho (chamamos isso de O(n)). Se você compara cada item com todos os outros, dobrar os itens = quatro vezes mais trabalho (O(n²)). É isso — um nome curto para a velocidade com que o trabalho cresce.

análise de complexidade: Estimar o trabalho (tempo) e a memória que um algoritmo precisa em função do tamanho da entrada n.
Big-O: Notação para a taxa de crescimento de um algoritmo no pior caso, ignorando constantes e termos de ordem inferior.
tempo linear: O(n): o trabalho cresce em proporção direta ao tamanho da entrada — uma passada por cada elemento.