Problemas de Implementação
Ao lidarmos com algoritmos e estruturas de dados, muitas vezes as pessoas ficam com a impressão de que são assuntos extremamente complexos. Contudo, na maior parte das situações, estas técnicas são simples e intuitivas. Para as dominar, basta praticar e ganhar experiência prática, de modo a adquirir a intuição de como os algoritmos funcionam na realidade.
Quando enfrentamos exercícios e problemas específicos, rapidamente se torna evidente que certos grupos e categorias de problemas podem ser encarados em conjunto. Partilham determinadas características que nos permitem aplicar algumas técnicas a todo esse grupo de problemas.
Um desses grupos é o dos problemas de implementação. Normalmente, essas questões trazem no enunciado os passos necessários para chegar à solução. Ou seja, as ações que o programa deve executar estão detalhadas no próprio problema. Assim, o trabalho do engenheiro de software consiste em implementar esses passos de forma eficiente para alcançar o resultado desejado. É importante salientar que, apesar de os passos estarem descritos no enunciado, pode não ser imediato transformá-los em código logo de início.
Desafio - Find the missing number
Dado todos os números de 1 a
n exceto um, pretende-se encontrar o número que está em falta.Input
A primeira linha do input contém um único inteiro
n (2 ≤ n ≤ 100 000).A segunda linha do input contém
n-1 inteiros separados por espaço (1 ≤ ≤ n).Output
O programa deve imprimir o número em falta.
Exemplos
Entrada | Saída |
4
3 4 1 | 2 |
3
2 1 | 3 |
Tutorial sobre Complexidade e Notação Big
Apesar de o problema descrito acima parecer simples, a solução ingênua não será suficientemente rápida para passar em todos os testes.
Uma abordagem inicial (naive) poderia ser ler todos os elementos do input para uma lista e, em seguida, percorrer todos os números de 1 até
n para verificar se cada um deles está presente na lista. Sempre que um número não for encontrado, este será a resposta:n = int(input())
a = [int(ai) for ai in input().split()]
for i in range(1, n + 1): # n operações
if i not in a: # n operações (percorre todos os elementos)
print(i) # Encontrámos a solução!Este algoritmo acaba por ser muito lento. Ele percorre todos os números de
1...n e, para cada um, verifica se está na lista. Verificar a pertença de um número numa lista é uma operação linear, pois o programa precisa de percorrer todos os elementos em a para saber se i está lá ou não. Por isso, para cada i, são necessárias n operações, uma vez que a lista tem um tamanho próximo de n (na verdade n-1, mas isso não altera muito a análise).Consequentemente, o algoritmo realiza cerca de operações no total. O ciclo externo faz
n iterações, enquanto a verificação de pertença na lista também requer n passos, resultando em aproximadamente operações (no caso mais desfavorável).💻
Os nossos computadores conseguem realizar aproximadamente 10 a 100 milhões de operações num único segundo. Então, se o limite de tempo do problema for de 1 segundo (o que é comum em problemas de algoritmos), devemos procurar não exceder os 100 milhões de operações no total.
No problema descrito acima,
n pode ir até 100 000, o que implica que o algoritmo executaria operações, ou seja, 10 mil milhões de operações. Numa máquina comum, isso demoraria perto de 100 segundos, muito acima do limite de 1 segundo normalmente imposto. Logo, é necessário encontrar uma solução mais eficiente.Notação Big
A notação Big O (Big ) descreve o limite superior do ritmo de crescimento do tempo de execução de um algoritmo à medida que o tamanho da entrada aumenta. Ela fornece uma estimativa aproximada da quantidade de operações que o algoritmo realiza em função do tamanho da sua entrada.
No nosso exemplo, estimámos que o algoritmo realizaria unidades da ordem de operações no total. Assim, dizemos que a complexidade do algoritmo é .
Iremos explorar este assunto mais detalhadamente, apresentando mais intuição e formalidade ao longo do curso.
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB