Análise de Complexidade - Desafios Flashcards
Defina e explique, de maneira formal, o que significa dizer que uma função possui complexidade O(n).
De maneira formal, dizer que uma função f(x) é O(n) quer dizer que ∃ k > 0 ∃ n0 ∀n>n0 f(n) <= k * n. Em outras palavras, isso quer dizer que, para uma entrada suficientemente grande, o tempo de execução será sempre de uma ordem menor ou igual a n
A expressão x = O(n) pode ser escrita como O(n) = x. Verdadeiro ou falso? Justifique.
Falso. x = O(n) não significa que x é igual a O(n), mas sim que x pertence ao conjunto das funções para o qual a definição de O(n) se aplica. Em outras palavras, x = O(n) deve ser entendido como “x é/pertence a O(n)” ao invés de “x é igual a O(n)”.
Explique, de forma sucinta, o significado das notações O, Ω, Θ, o e ω. Quai operador aritmético melhor resume o significado dessas notações?
- f(x) = o(g(x)) : f(x) será sempre inferior a g(x). <
- f(x) = O(g(x)): f(x) nunca será maior que g(x). <=
- f(x) = Θ(g(x)): f(x) nunca será nem muito maior nem muito menor que g(x). ≈
- f(x) = Ω(g(x)): f(x) nunca será menor que g(x). >=
- f(x) = ω(g(x)): f(x) será sempre maior que g(x). >
Como demonstrar de maneira formal que um loop dentro de um algoritmo é correto?
Usando indução:
- Primeiro, mostra-se o caso base (ou seja, que o algoritmo é correto antes de entrar no loop).
- Então, mostra-se o caso indutivo (ou seja, se ele era correto antes de entrar no loop, ele permanece correto antes da próxima iteração).
- Por último, demonstra-se que o loop é finito (junto com suas implicações baseadas na condição de término).
Como obter a relação de recorrência da quantidade de operações necessárias para resolver um problema recursivo com a técnica dividir para conquistar?
Primeiro, calcule a quantidade de operações envolvidas no passo base, T(0).
A seguir, calcule D(n), a quantidade de operações necessárias para dividir o problema de tamanho n em a problemas de tamanho n/b. Então, calcule C(n), a quantidade de operações necessárias para transformar as a soluções de problemas de tamanho n/b em uma solução para o problema de tamanho n. Por último, para obter a relação de recorrência, some D(n) com C(n) e a * T(n/b).
Um algoritmo O(n²) é mais lento para entradas suficientemente grandes que um algoritmo O(n). Verdadeiro ou falso? Justifique.
Falso. Pela definição da notação O, um algoritmo que sempre executa em tempo constante também é O(n²) e por consequência pode ser mais rápido que um algoritmo que executa em velocidade linear.
Um algoritmo Θ(n²) é sempre mais lento que um algoritmo Θ(n). Verdadeiro ou falso? Justifique.
Falso. Análise assintótica calcula a velocidade para valores grandes o suficiente para tornarem irrelevantes as constantes dos valores menores. Para entradas pequenas, um algoritmo que precisa de n² operações para ser executado é mais rápido que um algoritmo que precisa de 1000 * n operações.
O que a função Θ(n) representa na seguinte equação?
2n² + 3n + 1 = 2n² + Θ(n). Qual a vantagem desse tipo de representação?
Nesse caso, Θ(n) representa uma função qualquer que pertence ao conjunto das funções Θ(n).
A vantagem desse tipo de representação é que permite o estudo da complexidade de algoritmos sem ter necessariamente que especificar todas as operações de menor ordem envolvidas.
O que a função Θ representa na seguinte equação?
2n² + Θ(n) = Θ(n²). Como interpretar essa equação?
Nesse caso, Θ representa uma função qualquer que pertence ao conjunto das funções especificadas como parâmetro.
A expressão indica que, não importa qual função você escolha para Θ(n), existe uma forma de escolher uma função pertencente a Θ(n²) que satisfaz a equação.
Como deve-se interpretar convencionalmente a expressão T(n) = O(1) para n < 3. Por que essa convenção é considerada um abuso da notação?
Pela convenção, deve-se entender a expressão como “existe uma constante c tal que T(n) <= c quando n < 3”.
Essa convenção é considerada um abuso porque a notação big O nesse caso diz que existem constantes c e n0 tais que para qualquer n > n0, T(n) <= c. Se a constante n0 for maior ou igual a 3, não é possível inferir nada, tornando a expressão sem sentido.
Enumere quais notações (entre O, Ω, Θ, o e ω) possuem as seguintes propriedades:
- Transitividade
- Reflexividade
- Simetria
- Todas elas são transitivas (ou seja, f(n) = O(g(n)) e g(n) = O(h(n)) implica em f(n) = O(h(n)).
- O, Ω e Θ são reflexivas (ou seja, f(n) = O(f(n))
- Somente Θ é simétrica (ou seja, f(n) = Θ(g(n)) se e somente se g(n) = Θ(f(n)) ).
Quais propriedades uma recorrência T(n) tem que possuir para ser considerada algorítmica? Quando isso é convencionalmente usado?
Ela deve, para algum valor constante pré-defindo n0 > 0, seguir duas propriedades:
1 - Para todo n < n0, T(n) = Θ(1)
2 - Para todo n >= n0, todo caminho de recursão alcança um dos casos base em um número finito de invocações recursivas.
Convencionalmente, quando uma recorrência é definida sem um caso base explícito, assumimos que ela seja algorítmica.
Cite e explique de forma sucinta quatro formas diferentes de definir o comportamento assintótico de algoritmos cujo comportamento pode ser descrito por uma relação de recorrência.
- Método da substituição: Dê um palpite para o comportamento assintótico e verifique se ele está correto usando indução matemática.
- Método da árvore recursiva: Modele a recorrência como uma árvore onde cada nó representa o custo de uma etapa e então some o valor desses nós.
- Teorema mestre: Se a recorrência é da forma T(n) = a T(n/b) + f(n) (a > 0 e b > 1 constantes, custo de dividir e combinar f(n)), ela pode ser resolvida usando um dos três casos do Teorema Mestre.
- Método Akra-Bazzi: Método geral para resolver recorrência usando cálculo. Capaz de lidar com recorrências mais complicadas que as abordadas pelo Teorema Mestre.
Onde está o erro na seguinte prova que T(n) = 2T(n/2) + Θ(n) possui complexidade O(n)?
T(n) = 2T(n/2) + Θ(n)
<= 2 * O(n/2) + Θ(n)
<= 2 * O(n) + Θ(n)
= O(n)
O erro está no fato de que a constante c implícita na notação O(n) não é necessariamente a mesma em cada linha. Para construir uma prova usando indução estrutural, é necessário demonstrar que a constante c da primeira e da última linha trata-se da mesma constante.
No contexto de comportamento assintótico de funções de recorrência, por que recomenda-se evitar o uso de notações assintóticas no método da substituição?
Para que a demonstração por indução matemática seja válida, é necessário que a mesma constante satisfaça a a recorrência para todo n > n0. Por outro lado, notações assintóticas incluem uma ou mais constantes que não necessariamente permanecem as mesmas durante o desenvolvimento da prova. Por isso, recomenda-se nomear as constantes de forma explícita.
Onde está o erro na seguinte prova que T(n) = 2T(n/2) + Θ(n) possui complexidade O(n)?
T(n) = 2T(n/2) + Θ(n)
<= 2(c*n/2) + Θ(n)
<= cn + Θ(n)
= O(n)
O erro está no fato de que a prova por indução tem por objetivo mostrar que T(n) <= cn para todo n > n0. Ao provarmos isso, demonstramos por consequência que T(n) pertence ao conjunto O(n), algo que não foi demonstrado nesta prova.
Quais são as condições para a aplicação do Teorema Mestre para a resolução de recorrências?
T(n) deve ser uma recorrência da forma a * T(n/b) + f(n) com a > 0, b > 1 e f(n) definida para reais grandes o suficiente. a * T(n/b) também pode ser escrita como a’ * T(⌈n/b⌉) + a ‘’ * T(⌊n/b⌋), com a’ + a’’ = a.
Quais são os três casos do Teorema Mestre para resolução de recorrências?
1 - Se existir uma constante ε > 0 tal que f(n) = O(n ^ (log b a - ε) ), então T(n) = Θ(n^logb a)
2 - Se existir uma constante k >= 0 tal que f(n) = Θ(n ^log(b a) * lg ^ k n), então T(n) = Θ (n^logb a * lg^(k+1) n)
3 - Se existir uma constante ε > 0 tal que f(n) = Ω(n^(log b a + ε)) e se f(n) satisfaz a condição de regularidade a * f(n/b) <= c f(n) para alguma constante c < 1 para todo n grande o suficiente, então T(n) = Θ(f(n)).
De maneira simplificada, como identificar qual caso do Teorema mestre deve ser utilizada em um determinado problema?
De maneira simplificada, basta comparar a função f(n) com a função n ^ (log b a).
Se a segunda função cresce (polinomialmente) mais rápido que a primeira, devemos aplicar o primeiro caso. Se ambas crescem aproximadamente na mesma taxa, devemos aplicar o segundo caso. Se a primeira cresce (polinomialmente) mais rápido que a segunda, aplicamos o terceiro caso.
Dê três exemplos de circunstâncias que podem levar o Teorema Mestre a não ser aplicável.
1 - A função de recorrência não ser da forma a * T(n/b) + f(n).
2 - A função n^(log b a) não crescer polinomialmente mais rápido que f(n). Por exemplo, na função T(n) = 2T(n/2) + n/lg n, f(n) cresce logaritmicamente mais rápido que n^(log 2 2) = n.
3 - A função f(n) não crescer polinomialmente mais rápido que n^(log b a). Acontece, nesse caso, o caso reverso doanterior.
4 - As função f(n) e n ^ (log b a) não puderem ser comparadas assintoticamente. Por exemplo, f(n) pode ser uma função definida por partes em que cada parte se compara de forma diferente a n ^ (log b a).
5 - O caso ser similar ao apresentado no caso 3 do Teorema Mestre, porém a função f(n) não satisfazer a condição de regularidade a*f(n/b) <= c f(n) para alguma constante c < 1
Qual a forma geral da recorrência de Akra-Bazzi? Qual a vantagem de usá-la sobre o Teorema Mestre?
A forma geral da recorrência de Akra-Bazzi é T(n) = f(n) + Σ ai T(n/bi).
A maior vantagem da recorrência de Akra-Bazzi é que ela pode ser usada para lidar com situações onde a recorrência divide o problema principal em sub problemas de tamanhos diferentes.
Como usar o método de Akra-Bazzi para resolver recorrências?
Primeiro, deve-se encontrar o número p tal que Σ ai/bi^p = 1. Com isso, o método de Akra-Bazzi diz que a solução da recorrência T(n) será Θ(n^p(1 + integral de 1 até n de f(x)/x^(p+1))).
Qual a diferença entre máximo e maximal?
Máximo se refere ao maior valor possível (ou seja, o maior valor global). Maximal se refere ao maior valor alcançável a partir do caminho escolhido (ou seja, o maior valor local).
