Exercícios sobre complexidade de algoritmos

Prévia do material em texto

Exercícios sobre complexidade de algoritmos
1. Dada uma função em um algoritmo, como f(n) = 3n^2 + 2n + 1, determine sua complexidade
assintótica em termos de Big O.
2. Suponha que temos um algoritmo que possui um loop que executa n/2 iterações. Qual é a
complexidade assintótica desse algoritmo?
3. Considere um algoritmo que tem um loop aninhado dentro de outro loop, onde ambos os loops
executam n iterações. Qual é a complexidade assintótica desse algoritmo?
4. Se um algoritmo possui uma complexidade de tempo de O(n log n) e outro possui uma
complexidade de O(n^2), qual algoritmo seria mais eficiente para grandes conjuntos de dados?
Explique.
5. Dada uma função de complexidade T(n) = 2T(n/2) + n, determine sua complexidade assintótica
utilizando o Teorema Mestre.
6. Suponha que um algoritmo tem uma complexidade de tempo de O(n^3) e seu tamanho de
entrada seja aumentado em 10 vezes. Qual será o impacto no tempo de execução do algoritmo?
7. Explique a diferença entre complexidade de tempo e complexidade de espaço de um algoritmo.
Dê exemplos.
8. Se um algoritmo tem uma complexidade de tempo de O(n^2) e uma complexidade de espaço de
O(1), o que isso significa em termos de desempenho e uso de memória?
9. Considere um algoritmo que primeiro ordena uma lista de números e, em seguida, realiza uma
busca binária nessa lista ordenada. Qual é a complexidade assintótica total deste algoritmo?
10. Suponha que temos um algoritmo que realiza uma busca linear em uma lista de tamanho n, em
seguida, executa uma operação de ordenação em outra lista de tamanho m. Qual seria a
complexidade assintótica total desse algoritmo, considerando que m pode ser diferente de n?
1. Resolução: A função f(n) = 3n^2 + 2n + 1 tem uma complexidade assintótica de O(n^2), pois o
termo dominante é n^2.
2. Resolução: Um loop que executa n/2 iterações tem uma complexidade assintótica de O(n), pois o
número de iterações é linearmente proporcional a n.
3. Resolução: Se um algoritmo possui dois loops aninhados que executam n iterações cada, a
complexidade total é O(n^2), pois a quantidade total de iterações é o produto dos tamanhos dos
loops.
4. Resolução: Um algoritmo com complexidade de tempo O(n log n) é mais eficiente do que um
algoritmo com complexidade O(n^2) para grandes conjuntos de dados. Isso ocorre porque n log n
cresce muito mais lentamente do que n^2 à medida que n aumenta.
5. Resolução: Utilizando o Teorema Mestre, podemos ver que T(n) = aT(n/b) + f(n), onde a = 2, b = 2
e f(n) = n. Como f(n) = n = O(n^1), então a complexidade de T(n) é O(n^log_b(a)), ou seja,
O(n^log_2(2)), que é O(n).
6. Resolução: Se a complexidade de tempo é O(n^3), e o tamanho de entrada é aumentado em 10
vezes, o tempo de execução será aumentado em 10^3 = 1000 vezes.
7. Resolução: A complexidade de tempo de um algoritmo refere-se ao número de operações que ele
realiza em relação ao tamanho da entrada, enquanto a complexidade de espaço refere-se à
quantidade de memória que o algoritmo utiliza durante sua execução. Por exemplo, um algoritmo de
ordenação por inserção tem uma complexidade de tempo de O(n^2) e uma complexidade de espaço
de O(1).
8. Resolução: Isso significa que, à medida que o tamanho da entrada aumenta, o tempo de execução
do algoritmo aumenta quadraticamente, enquanto a quantidade de memória que ele usa permanece
constante, independente do tamanho da entrada.
9. Resolução: A ordenação da lista tem uma complexidade de tempo de O(n log n), e a busca binária
tem uma complexidade de tempo de O(log n). Portanto, a complexidade assintótica total é O(n log n)
+ O(log n), que simplifica para O(n log n).
10. Resolução: A busca linear tem uma complexidade de tempo de O(n), e a operação de ordenação
tem uma complexidade de tempo que depende do tamanho da lista, portanto, é O(m log m).
Portanto, a complexidade total seria O(n) + O(m log m).