Métodos de Resolução de Recorrências - AULA 04 - PDF

Definição Métodos de Resolução Projeto e Análise de Algoritmos Métodos de Resolução de Recorrências Prof. Giovani Bernardes Vitor...

Definição Métodos de Resolução Projeto e Análise de Algoritmos Métodos de Resolução de Recorrências Prof. Giovani Bernardes Vitor [email protected] ECOI11 : PAA Universidade Federal de Itajubá - UNIFEI Campus de Itabira-MG 26 Agosto 2024 Giovani Bernardes Vitor Aula 04: Métodos de Recorrências 26 Agosto 2024 1 / 49  Definição Algoritmos Recursivos e suas Recorrências Métodos de Resolução Recorrências Quando um algoritmo contém uma chamada recursiva a si próprio, seu tempo de execução frequentemente pode ser descrito por uma equação de recorrência ou recorrência, que descreve o tempo de execução glo- bal sobre um problema de tamanho n em termos do tempo de execução sobre entradas menores. Pode-se usar ferramentas matemáticas para resolver a recorrência e es- tabelecer limites sobre o desempenho do algoritmo. Giovani Bernardes Vitor Aula 04: Métodos de Recorrências 26 Agosto 2024 2 / 49  Definição Algoritmos Recursivos e suas Recorrências Métodos de Resolução Recorrências Métodos para resolver Recorrências: Expansão Substituição Árvores de Recursão Teorema Mestre Giovani Bernardes Vitor Aula 04: Métodos de Recorrências 26 Agosto 2024 3 / 49  Definição Algoritmos Recursivos e suas Recorrências Métodos de Resolução Fatorial Seja a seguinte função para calcular o fatorial de n: double fatorial(unsigned int n) { if (n 1, o custo para executar a função é c mais o custo para executar T (n − 1). Como resolver essa recorrência? Giovani Bernardes Vitor Aula 04: Métodos de Recorrências 26 Agosto 2024 5 / 49  Definição Algoritmos Recursivos e suas Recorrências Métodos de Resolução Ordenação com o Mergesort Também conhecido como ordenação por intercalação. Obedece ao para- digma de dividir e conquistar. Dividir: Divide a sequência de n elementos a serem ordenados em duas subsequências de n/2 elementos cada uma. Conquistar: Ordena as duas subsequências recursivamente, utilizando a ordenação por intercalação. Combinar: Intercala (merge) as duas sequências ordenadas, de modo a produzir a resposta ordenada. Giovani Bernardes Vitor Aula 04: Métodos de Recorrências 26 Agosto 2024 6 / 49  Definição Algoritmos Recursivos e suas Recorrências Métodos de Resolução Ordenação com o Mergesort A operação chave do Mergesort é a intercalação de duas sequências ordenadas, no passo de Combinação. O Mergesort utiliza o procedimento Intercala(A, p, q, r) que possui: Entrada: um vetor A[p..r ] e um índice q tais que A[p..q] e A[q + 1..r ] estão em ordem crescente. Saída: o vetor A[p..r ] em ordem crescente. Giovani Bernardes Vitor Aula 04: Métodos de Recorrências 26 Agosto 2024 7 / 49  Definição Algoritmos Recursivos e suas Recorrências Métodos de Resolução Ordenação com o Mergesort Giovani Bernardes Vitor Aula 04: Métodos de Recorrências 26 Agosto 2024 8 / 49  Definição Algoritmos Recursivos e suas Recorrências Métodos de Resolução Ordenação com o Mergesort Algoritmo 1 INTERCALA(A, p, q, r) 1: n1 = q − p + 1 2: n2 = r − q 3: Criar vetores L[1...n1 + 1] e R[1..n2 + 1] 4: para i = 1 até n1 faça 5: L[i] = A[p + i − 1] 6: fim para 7: para j = 1 até n2 faça 8: R[j] = A[q + j] 9: fim para 10: L[n1 + 1] = ∞, R[n2 + 1] = ∞, i = 1, j = 1 11: para k = p até r faça 12: se L[i] 1 Como resolver essa recorrência? Giovani Bernardes Vitor Aula 04: Métodos de Recorrências 26 Agosto 2024 19 / 49  Método da Expansão Definição Método da árvore de recursão Métodos de Resolução Método da Substituição Método do Teorema Mestre Método da Expansão Também conhecido por Método de Iteração. Em cada passo, o valor do termo T é substituído pela sua definição. Giovani Bernardes Vitor Aula 04: Métodos de Recorrências 26 Agosto 2024 20 / 49  Método da Expansão Definição Método da árvore de recursão Métodos de Resolução Método da Substituição Método do Teorema Mestre Método da Expansão Exemplo 1: Voltando à recorrência do algoritmo de fatorial recursivo... T (n) =c + T (n − 1) =c + (c + T (n − 2)) =c + c + (c + T (n − 3)). =.. =c + c +... + (c + T (1)) = c + c +... + c +d | {z } n−1 Desta forma, a recorrência pode ser expressa como: T (n) = c(n − 1) + d = O(n) Giovani Bernardes Vitor Aula 04: Métodos de Recorrências 26 Agosto 2024 21 / 49  Método da Expansão Definição Método da árvore de recursão Métodos de Resolução Método da Substituição Método do Teorema Mestre Método da Expansão Exemplo 2: Seja a seguinte recorrência: ( 0 n=1 T (n) = T ( n2 ) + 1 n >= 2 Resolvendo a recorrência... n T (n) =T ( ) + 1 2 n =(T ( 2 ) + 1) + 1 2 n =(T ( 3 ) + 1) + 1 + 1 2 (1). =.. =(T (1) + 1) + 1 +... + 1 n =T ( k ) + 1 + 1 +... + 1 2 | {z } k Giovani Bernardes Vitor Aula 04: Métodos de Recorrências 26 Agosto 2024 22 / 49  Método da Expansão Definição Método da árvore de recursão Métodos de Resolução Método da Substituição Método do Teorema Mestre Método da Expansão Exemplo 2: Seja a seguinte recorrência: ( 0 n=1 T (n) = T ( n2 ) + 1 n >= 2 Resolvendo a recorrência... n T (n) =T ( ) + 1 2 n =(T ( 2 ) + 1) + 1 2 n =(T ( 3 ) + 1) + 1 + 1 2 (1). =.. =(T (1) + 1) + 1 +... + 1 n =T ( k ) + 1 + 1 +... + 1 2 | {z } k Giovani Bernardes Vitor Aula 04: Métodos de Recorrências 26 Agosto 2024 22 / 49  Método da Expansão Definição Método da árvore de recursão Métodos de Resolução Método da Substituição Método do Teorema Mestre Método da Expansão cont. Exemplo 2: Para resolver T (n), considere que 2nk = 1, ou seja, n = 2k. Aplicando o log2 nos dois lados fica igual a log2 n = log2 2k , resultando em k = log2 n. Aplicando em T (n): n T (n) =T ( )+k 2k =T (1) + log2 n = 0 + log2 n = log2 n = O(log2 n) Giovani Bernardes Vitor Aula 04: Métodos de Recorrências 26 Agosto 2024 23 / 49  Método da Expansão Definição Método da árvore de recursão Métodos de Resolução Método da Substituição Método do Teorema Mestre Método da Expansão Exemplo 3: Seja a seguinte recorrência: ( 0 n=1 T (n) = 2T ( n2 ) + n n >= 2 Resolvendo a recorrência... n T (n) =2T ( ) + n 2 n n =2(2T ( 2 ) + ) + n 2 2 n n n =2(2(2T ( 3 ) + 2 ) + ) + n 2 2 2.. =. =2(2(2(...(2T (1) + 2) + 22 )...) + 2k −1 ) + 2k =k 2k Giovani Bernardes Vitor Aula 04: Métodos de Recorrências 26 Agosto 2024 24 / 49  Método da Expansão Definição Método da árvore de recursão Métodos de Resolução Método da Substituição Método do Teorema Mestre Método da Expansão Exemplo 3: Seja a seguinte recorrência: ( 0 n=1 T (n) = 2T ( n2 ) + n n >= 2 Resolvendo a recorrência... n T (n) =2T ( ) + n 2 n n =2(2T ( 2 ) + ) + n 2 2 n n n =2(2(2T ( 3 ) + 2 ) + ) + n 2 2 2.. =. =2(2(2(...(2T (1) + 2) + 22 )...) + 2k −1 ) + 2k =k 2k Giovani Bernardes Vitor Aula 04: Métodos de Recorrências 26 Agosto 2024 24 / 49  Método da Expansão Definição Método da árvore de recursão Métodos de Resolução Método da Substituição Método do Teorema Mestre Método da Expansão cont. Exemplo 3: Para resolver T (n), considere que 2nk = 1, ou seja, n = 2k. Conforme o exemplo anterior, k = log2 n. Aplicando em T (n): T (n) =k 2k =log2 n2log2 n =log2 nn =O(nlog2 n) Giovani Bernardes Vitor Aula 04: Métodos de Recorrências 26 Agosto 2024 25 / 49  Método da Expansão Definição Método da árvore de recursão Métodos de Resolução Método da Substituição Método do Teorema Mestre Método da Expansão Exemplo 4: Às vezes, um pouco de manipulação algébrica pode tornar uma recorrência desconhecida semelhante a uma que você já viu antes. Seja a seguinte recorrência: √ T (n) = 2T ( n) + lgn Parece difícil, mas podemos simplicá-la com uma troca de variáveis. Reno- mear m = lgn, produz: m T (2m ) = 2T (2 2 ) + m Giovani Bernardes Vitor Aula 04: Métodos de Recorrências 26 Agosto 2024 26 / 49  Método da Expansão Definição Método da árvore de recursão Métodos de Resolução Método da Substituição Método do Teorema Mestre Método da Expansão cont. Exemplo 4: Agora podemos renomear S(m) = T (2m ) para produzir a nova recorrência: m S(m) = 2S( ) + m 2 que é muito semelhante à recorrência do Exemplo 3. Essa nova recorrência possui a mesma solução: S(m) = O(mlgm). Trocando de volta de S(m) para T (n), obtemos: T (n) = T (2m ) = S(m) = O(mlgm) = O(lgnlglgn) Giovani Bernardes Vitor Aula 04: Métodos de Recorrências 26 Agosto 2024 27 / 49  Método da Expansão Definição Método da árvore de recursão Métodos de Resolução Método da Substituição Método do Teorema Mestre Método da Expansão Exemplo 5: Resolva a recorrência: ( 1 n=1 T (n) = n + T ( n3 ) n > 1 Giovani Bernardes Vitor Aula 04: Métodos de Recorrências 26 Agosto 2024 28 / 49  Método da Expansão Definição Método da árvore de recursão Métodos de Resolução Método da Substituição Método do Teorema Mestre Método da Expansão n T (n) =n + T ( ) 3 n n =n + ( + T ( 2 )) 3 3 n n n =n + ( + 2 + T ( 3 )) 3 3 3. =.. n n =n + + 2 +... + T (n/3k ) 3 3 1 Esta equação representa uma soma de uma série geométrica de razão 3 multiplicada por n e adicionada de T ( 3nk ), que é menor ou igual à 1. Giovani Bernardes Vitor Aula 04: Métodos de Recorrências 26 Agosto 2024 29 / 49  Método da Expansão Definição Método da árvore de recursão Métodos de Resolução Método da Substituição Método do Teorema Mestre Método da Expansão (cont.) Se desprezarmos o termo T ( 3nk ), quando n tende para o infinito, então ∞ X 1 1 3n T (n) = n ( )i = n( )= i=0 3 1 − 13 2 Se considerarmos o termo T ( 3nk ) e denominarmos k o número de subdivisões de 3 do tamanho do problema, então 3nk = 1 e n = 3k. Logo k = log3 n. k −1 k −1 X n n X 1 T (n) = i + T( k ) = n ( )i + 1 3 3 3 i=0 i=0 n(1 − ( 31 )k ) 3n = +1= = O(n) (1 − 13 ) 2 Giovani Bernardes Vitor Aula 04: Métodos de Recorrências 26 Agosto 2024 30 / 49  Método da Expansão Definição Método da árvore de recursão Métodos de Resolução Método da Substituição Método do Teorema Mestre Método da Expansão (cont.) Se desprezarmos o termo T ( 3nk ), quando n tende para o infinito, então ∞ X 1 1 3n T (n) = n ( )i = n( )= i=0 3 1 − 13 2 Se considerarmos o termo T ( 3nk ) e denominarmos k o número de subdivisões de 3 do tamanho do problema, então 3nk = 1 e n = 3k. Logo k = log3 n. k −1 k −1 X n n X 1 T (n) = i + T( k ) = n ( )i + 1 3 3 3 i=0 i=0 n(1 − ( 31 )k ) 3n = +1= = O(n) (1 − 13 ) 2 Giovani Bernardes Vitor Aula 04: Métodos de Recorrências 26 Agosto 2024 30 / 49  Método da Expansão Definição Método da árvore de recursão Métodos de Resolução Método da Substituição Método do Teorema Mestre Método da árvore de recursão Permite visualizar melhor o que acontece quando a recorrência é iterada. Útil para recorrências de algoritmos de divisão e conquista. Considere a recorrência do algoritmo MERGESORT: ( c n=1 T (n) = 2T ( n2 ) + cn n > 1 Giovani Bernardes Vitor Aula 04: Métodos de Recorrências 26 Agosto 2024 31 / 49  Método da Expansão Definição Método da árvore de recursão Métodos de Resolução Método da Substituição Método do Teorema Mestre Método da árvore de recursão Giovani Bernardes Vitor Aula 04: Métodos de Recorrências 26 Agosto 2024 32 / 49  Método da Expansão Definição Método da árvore de recursão Métodos de Resolução Método da Substituição Método do Teorema Mestre Método da árvore de recursão Giovani Bernardes Vitor Aula 04: Métodos de Recorrências 26 Agosto 2024 33 / 49  Método da Expansão Definição Método da árvore de recursão Métodos de Resolução Método da Substituição Método do Teorema Mestre Método da árvore de recursão O número de níveis é lgn + 1. No nível i o tempo gasto é cn. No último nível há cn folhas. Logo, T (n) = cnlgn + cn = O(nlgn). Giovani Bernardes Vitor Aula 04: Métodos de Recorrências 26 Agosto 2024 34 / 49  Método da Expansão Definição Método da árvore de recursão Métodos de Resolução Método da Substituição Método do Teorema Mestre Método da árvore de recursão Resumo: O número de nós em cada nível da árvore é o número de chamadas recursivas. Em cada nó indicamos o tempo gasto naquele nó que não corresponde a chamadas recursivas. Na coluna mais à direita indicamos o tempo total naquele nível que não corresponde a chamadas recursivas. Somando ao longo da coluna determina-se a solução de recorrência. Giovani Bernardes Vitor Aula 04: Métodos de Recorrências 26 Agosto 2024 35 / 49  Método da Expansão Definição Método da árvore de recursão Métodos de Resolução Método da Substituição Método do Teorema Mestre Método da Substituição O método de substituição para resolver recorrências envolve duas etapas: 1 Pressupor a forma da solução. 2 Usar a indução matemática para encontrar as constantes e mostrar que a solução funciona. O nome vem da substituição da resposta pressuposta para a função quando a hipótese indutiva é aplicada a valores menores. Método eficiente, mas só pode ser aplicado em casos nos quais é fácil pressupor a forma da resposta. Pode ser usado para estabelecer limites inferiores ou superiores sobre uma recorrência. Giovani Bernardes Vitor Aula 04: Métodos de Recorrências 26 Agosto 2024 36 / 49  Método da Expansão Definição Método da árvore de recursão Métodos de Resolução Método da Substituição Método do Teorema Mestre Método da Substituição Exemplo 1: Seja a seguinte recorrência, muito semelhante à do MERGESORT: n T (n) = 2T (b c) + n 2 Supomos que a solução é T (n) = O(nlgn). Devemos provar que T (n) ≤ cnlgn para c > 0. Começamos supondo que esse limite se mantém válido para bn/2c, ou seja, que T (bn/2c) ≤ c bn/2c lg(bn/2c). Giovani Bernardes Vitor Aula 04: Métodos de Recorrências 26 Agosto 2024 37 / 49  Método da Expansão Definição Método da árvore de recursão Métodos de Resolução Método da Substituição Método do Teorema Mestre Método da Substituição cont. A substituição na recorrência produz: n n T (n) 1 constantes, seja f(n) uma função e seja T(n) definida sobre os inteiros não negativos pela recorrência n T (n) = aT ( ) + f (n) b n como bn ou bn.     onde interpretamos b logb a− 1 Se f (n) = O(n ) para alguma constante  > 0, então T (n) = Θ(nlogb a ). 2 Se f (n) = Θ(nlogb a ), então T (n) = Θ(nlogb a log n). 3 Se f (n) = Ω(nlogb a+ ) para alguma constante  > 0, e se af (n/b) ≤ cf (n) para alguma constante c < 1 e para todo n suficientemente grande, então T (n) = Θ(f (n)). Giovani Bernardes Vitor Aula 04: Métodos de Recorrências 26 Agosto 2024 44 / 49  Método da Expansão Definição Método da árvore de recursão Métodos de Resolução Método da Substituição Método do Teorema Mestre Teorema Mestre Exemplo 1: T (n) = 9T (n/3) + n Temos a = 9, b = 3, f (n) = n. Portanto, nlogb a = nlog3 9 = n2. Como f (n) = O(nlog3 9− ), onde  = 1, podemos aplicar o Caso 1 e concluir que a solução é T (n) = Θ(n2 ). Giovani Bernardes Vitor Aula 04: Métodos de Recorrências 26 Agosto 2024 45 / 49  Método da Expansão Definição Método da árvore de recursão Métodos de Resolução Método da Substituição Método do Teorema Mestre Teorema Mestre Exemplo 2: T (n) = T (2n/3) + 1 Temos a = 1, b = 3/2, f (n) = 1. Portanto, nlogb a = nlog3/2 1 = n0 = 1. Aplica-se o Caso 2, pois f (n) = Θ(nlogb a ) = Θ(1), e portanto a solução da recorrência é T (n) = Θ(log n). Giovani Bernardes Vitor Aula 04: Métodos de Recorrências 26 Agosto 2024 46 / 49  Método da Expansão Definição Método da árvore de recursão Métodos de Resolução Método da Substituição Método do Teorema Mestre Teorema Mestre Exemplo 3: T (n) = 3T (n/4) + nlog n Temos a = 3, b = 4, f (n) = nlog n. Portanto, nlogb a = nlog4 3 = n0,793. Como f (n) = Ω(nlog4 3+ ), onde  ≈ 0, 2, aplica-se o Caso 3 se podemos mostrar que a condição de regularidade é válida para f (n). Para n suficientemente grande, af (n/b) = 3f (n/4) = 3(n/4)log n/4 ≤ (3/4)nlog n = cf (n) para c = 3/4. Assim, de acordo com o Caso 3, a solução para a recorrência é T (n) = Θ(nlog n). Giovani Bernardes Vitor Aula 04: Métodos de Recorrências 26 Agosto 2024 47 / 49  Método da Expansão Definição Método da árvore de recursão Métodos de Resolução Método da Substituição Método do Teorema Mestre Teorema Mestre Exemplo 4: T (n) = 2T (n/2) + nlog n Temos a = 2, b = 2, f (n) = nlog n. Portanto, nlogb a = nlog2 2 = n1 = n. Parece que o Caso 3 deve se aplicar, pois f (n) = nlog n é assintoticamente maior que nlogb a = nlog2 2 = n1 = n. Não existe  > 0 tal que f (n) ∈ Ω(nlogb a+ ). Giovani Bernardes Vitor Aula 04: Métodos de Recorrências 26 Agosto 2024 48 / 49  Método da Expansão Definição Método da árvore de recursão Métodos de Resolução Método da Substituição Método do Teorema Mestre Referências Notas de aula: Prof. Walter Aoiama Nagai e Profa. Claudia A. Izeki - Disciplina ECO027 - UNIFEI - 2015 Livro: Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Clifford Stein, Introduction to Algorithms, volume , Editora Prentice-Hall, Segunda edição, (2006) Giovani Bernardes Vitor Aula 04: Métodos de Recorrências 26 Agosto 2024 49 / 49  Tópicos Introdução Análise assintótica Projeto e Análise de Algoritmos Complexidade Assintótica Prof. Giovani Bernardes Vitor [email protected] ECOI2207 : PAA Universidade Federal de Itajubá - UNIFEI Campus de Itabira-MG 19 Agosto 2024 Giovani Bernardes Vitor Aula 03: Complexidade Assintótica 19 Agosto 2024 1 / 34  Tópicos Introdução Análise assintótica Complexidade Assintótica Comparação Assintótica Análise Assintótica Ordens O, ω , θ Recursividade Giovani Bernardes Vitor Aula 03: Complexidade Assintótica 19 Agosto 2024 2 / 34  Tópicos Consumo de tempo assintótico Introdução Comparação assintótica de funções Análise assintótica Consumo de tempo assintótico Seja A um algoritmo para um problema P. A quantidade de tempo que A con- some para processar uma dada instância de P depende da máquina usada para executar A. Mas o efeito da máquina se resume a uma constante multi- plicativa: Se A consome tempo t numa determinada máquina, consumirá tempo 2t numa máquina duas vezes mais lenta e t/2 numa máquina duas vezes mais rápida. Para eliminar o efeito da máquina, basta discutir o consumo de tempo de A sem as constantes multiplicativas. A notação assintótica(O-ómicron, Ω-ómega, Θ-theta) é ideal para fazer isso. Giovani Bernardes Vitor Aula 03: Complexidade Assintótica 19 Agosto 2024 3 / 34  Tópicos Consumo de tempo assintótico Introdução Comparação assintótica de funções Análise assintótica Comparação assintótica de funções É desejável exprimir o consumo de tempo de um algoritmo de uma maneira que não dependa da linguagem de programação, nem dos detalhes de implementação, nem do computador empregado. Para tornar isto possível, é preciso introduzir um modo grosseiro de comparar funções. (dependência entre o consumo de tempo de um algoritmo e o tamanho de sua “entrada”) Giovani Bernardes Vitor Aula 03: Complexidade Assintótica 19 Agosto 2024 4 / 34  Tópicos Consumo de tempo assintótico Introdução Comparação assintótica de funções Análise assintótica Comparação assintótica de funções Essa comparação só leva em conta a “velocidade de crescimento” das funções. Assim, ela despreza fatores multiplicativos (pois a função 2n2 , por exemplo, cresce tão rápido quanto 10n2 ) e despreza valores peque- nos do argumento (a função n2 cresce mais rápido que 100n, embora n2 seja menor que 100n quando n é pequeno). Dizemos que esta maneira de comparar funções é assintótica. Há três tipos de comparação assintótica: uma com sabor de “>”, outra com sabor de “6”, e uma terceira com sabor de “=”. Giovani Bernardes Vitor Aula 03: Complexidade Assintótica 19 Agosto 2024 5 / 34  Tópicos Consumo de tempo assintótico Introdução Comparação assintótica de funções Análise assintótica Comparação assintótica de funções Essa comparação só leva em conta a “velocidade de crescimento” das funções. Assim, ela despreza fatores multiplicativos (pois a função 2n2 , por exemplo, cresce tão rápido quanto 10n2 ) e despreza valores peque- nos do argumento (a função n2 cresce mais rápido que 100n, embora n2 seja menor que 100n quando n é pequeno). Dizemos que esta maneira de comparar funções é assintótica. Há três tipos de comparação assintótica: uma com sabor de “>”, outra com sabor de “6”, e uma terceira com sabor de “=”. Giovani Bernardes Vitor Aula 03: Complexidade Assintótica 19 Agosto 2024 5 / 34  Tópicos Consumo de tempo assintótico Introdução Comparação assintótica de funções Análise assintótica Comparação assintótica de funções Essa comparação só leva em conta a “velocidade de crescimento” das funções. Assim, ela despreza fatores multiplicativos (pois a função 2n2 , por exemplo, cresce tão rápido quanto 10n2 ) e despreza valores peque- nos do argumento (a função n2 cresce mais rápido que 100n, embora n2 seja menor que 100n quando n é pequeno). Dizemos que esta maneira de comparar funções é assintótica. Há três tipos de comparação assintótica: uma com sabor de “>”, outra com sabor de “6”, e uma terceira com sabor de “=”. Giovani Bernardes Vitor Aula 03: Complexidade Assintótica 19 Agosto 2024 5 / 34  Análise assintótica Tópicos Notação O Introdução Notação Ω Análise assintótica Notação Θ Notações o, ω Análise assintótica Ao ver uma expressão como n+10 ou n2 +1,a maioria das pessoas pensa au- tomaticamente em valores pequenos de n, próximos de zero. A análise de al- goritmos faz exatamente o contrário: ignora os valores pequenos e concentra- se nos valores enormes de n. Para esses valores, as funções: 2 2 n2 N 2, 3n , 9999n2 , 1000 , n2 + 100n, etc. Crescem todas com a mesma velocidade e portanto são todas “equivalentes” Esse tipo de matemática, interessado somente em valores enormes de n, é chamado assintótica. Nessa matemática, as funções são classificadas em ´´ordens”; todas as funções de uma mesma ordem são “equivalentes”. As cinco funções acima, por exemplo, pertencem à mesma ordem. Giovani Bernardes Vitor Aula 03: Complexidade Assintótica 19 Agosto 2024 6 / 34  Análise assintótica Tópicos Notação O Introdução Notação Ω Análise assintótica Notação Θ Notações o, ω Notação O (ômicron grego Maiúsculo) (Big O) Convém restringir a atenção a funções assintoticamente não negativas, ou seja, funções f tais que f (n) > 0 para todo n suficientemente grande. Mais explicitamente: f é assintoticamente não negativa se existe n0 tal que f (n) > 0 para todo n maior que n0. DEFINIÇÃO: Dadas funções assintoticamente não negativas f e g, dizemos que f está na ordem O de g e escrevemos f = O(g) se f (n) 6 c.g(n) para algum c positivo e para todo n suficientemente grande. Em outras palavras, existe um número positivo c e um número n0 tais que f (n) 6 c.g(n) para todo n maior que n0. Giovani Bernardes Vitor Aula 03: Complexidade Assintótica 19 Agosto 2024 7 / 34  Análise assintótica Tópicos Notação O Introdução Notação Ω Análise assintótica Notação Θ Notações o, ω Notação O : Diagrama “F está em O(G)” tem sabor de “F 6 G00 tem sabor de “F não cresce mais que G” conceito sob medida para tratar de consumo de tempo de algoritmos Giovani Bernardes Vitor Aula 03: Complexidade Assintótica 19 Agosto 2024 8 / 34  Análise assintótica Tópicos Notação O Introdução Notação Ω Análise assintótica Notação Θ Notações o, ω Notação O : Exemplo 01 n2 + 10n = O(n2 ) (f 6 O(g)) → f (n) 6 c.g(n) PROVA: se n > 10 então n2 + 10n 6 2 ∗ n2 resumo: n2 + 10n 6 2∗n2 para todo n > 10 Como sabemos que 2 e 10 são bons valores para c e n0 ? queremos: n2 + 10n 6 c.n2 dividindo por n2 , temos: 1 + 10/n 6 c se n > 10 então 1 + 10/n 6 2 Parece que basta tomar c > 2 e n > 10 Giovani Bernardes Vitor Aula 03: Complexidade Assintótica 19 Agosto 2024 9 / 34  Análise assintótica Tópicos Notação O Introdução Notação Ω Análise assintótica Notação Θ Notações o, ω Notação O : Exemplo 01 n2 + 10n = O(n2 ) (f 6 O(g)) → f (n) 6 c.g(n) PROVA: se n > 10 então n2 + 10n 6 2 ∗ n2 resumo: n2 + 10n 6 2∗n2 para todo n > 10 Como sabemos que 2 e 10 são bons valores para c e n0 ? queremos: n2 + 10n 6 c.n2 dividindo por n2 , temos: 1 + 10/n 6 c se n > 10 então 1 + 10/n 6 2 Parece que basta tomar c > 2 e n > 10 Giovani Bernardes Vitor Aula 03: Complexidade Assintótica 19 Agosto 2024 9 / 34  Análise assintótica Tópicos Notação O Introdução Notação Ω Análise assintótica Notação Θ Notações o, ω Notação O : Exemplo 02 9n + 9 = O(n2 ) PROVA: para todo n > 1 então 9n + 9 6 18 ∗ n2 Giovani Bernardes Vitor Aula 03: Complexidade Assintótica 19 Agosto 2024 10 / 34  Análise assintótica Tópicos Notação O Introdução Notação Ω Análise assintótica Notação Θ Notações o, ω Notação O : Exemplo 02 9n + 9 = O(n2 ) PROVA: para todo n > 1 então 9n + 9 6 18 ∗ n2 Giovani Bernardes Vitor Aula 03: Complexidade Assintótica 19 Agosto 2024 10 / 34  Análise assintótica Tópicos Notação O Introdução Notação Ω Análise assintótica Notação Θ Notações o, ω Notação O : Exemplo 03 100n está em O(n2 ) PROVA: para todo n > 100 então Giovani Bernardes Vitor Aula 03: Complexidade Assintótica 19 Agosto 2024 11 / 34  Análise assintótica Tópicos Notação O Introdução Notação Ω Análise assintótica Notação Θ Notações o, ω Notação O : Exemplo 03 100n está em O(n2 ) PROVA: para todo n > 100 então 100n 6 n * n = n*n = 1 * n2 Giovani Bernardes Vitor Aula 03: Complexidade Assintótica 19 Agosto 2024 11 / 34  Análise assintótica Tópicos Notação O Introdução Notação Ω Análise assintótica Notação Θ Notações o, ω Notação O : Exemplo 04 2n3 + 100n está em O(n3 ) PROVA: para todo n > 1 então OUTRA PROVA: para todo n > 100 então Giovani Bernardes Vitor Aula 03: Complexidade Assintótica 19 Agosto 2024 12 / 34  Análise assintótica Tópicos Notação O Introdução Notação Ω Análise assintótica Notação Θ Notações o, ω Notação O : Exemplo 04 2n3 + 100n está em O(n3 ) PROVA: para todo n > 1 então 2n3 + 100n 6 2n3 + 100n3 6 102n3 OUTRA PROVA: para todo n > 100 então Giovani Bernardes Vitor Aula 03: Complexidade Assintótica 19 Agosto 2024 12 / 34  Análise assintótica Tópicos Notação O Introdução Notação Ω Análise assintótica Notação Θ Notações o, ω Notação O : Exemplo 04 2n3 + 100n está em O(n3 ) PROVA: para todo n > 1 então 2n3 + 100n 6 2n3 + 100n3 6 102n3 OUTRA PROVA: para todo n > 100 então 2n3 + 100n 6 2n3 + n * n * n 6 3n3 Giovani Bernardes Vitor Aula 03: Complexidade Assintótica 19 Agosto 2024 12 / 34  Análise assintótica Tópicos Notação O Introdução Notação Ω Análise assintótica Notação Θ Notações o, ω Notação O : Exemplo 05 log n está em O(n) PROVA: para todo n > 1 então Giovani Bernardes Vitor Aula 03: Complexidade Assintótica 19 Agosto 2024 13 / 34  Análise assintótica Tópicos Notação O Introdução Notação Ω Análise assintótica Notação Θ Notações o, ω Notação O : Exemplo 05 log n está em O(n) PROVA: para todo n > 1 então n 6 2n log n 6 log 2n log n 6 n Giovani Bernardes Vitor Aula 03: Complexidade Assintótica 19 Agosto 2024 13 / 34  Análise assintótica Tópicos Notação O Introdução Notação Ω Análise assintótica Notação Θ Notações o, ω Notação O : Exemplo 06 n1.5 está em O(n2 ) PROVA: para todo n > 1 então Giovani Bernardes Vitor Aula 03: Complexidade Assintótica 19 Agosto 2024 14 / 34  Análise assintótica Tópicos Notação O Introdução Notação Ω Análise assintótica Notação Θ Notações o, ω Notação O : Exemplo 06 n1.5 está em O(n2 ) PROVA: para todo n > 1 então n1.5 6 n0.5 ∗ n1.5 6 n2 Giovani Bernardes Vitor Aula 03: Complexidade Assintótica 19 Agosto 2024 14 / 34  Análise assintótica Tópicos Notação O Introdução Notação Ω Análise assintótica Notação Θ Notações o, ω Notação O : Exemplo 07 Suponha que f (n) = 2n2 + 3n + 4 e g(n) = n2. Observe que: 2n2 + 3n + 4 6 2n2 + 3n2 + 4n2 = 9n2. Desde que n0 6 1. Resumindo: f (n) 6 9g(n) para todo n > 1 Portanto, f (n) = O(g(n)). (f 6 O(g)) → f (n) 6 c.g(n) Giovani Bernardes Vitor Aula 03: Complexidade Assintótica 19 Agosto 2024 15 / 34  Análise assintótica Tópicos Notação O Introdução Notação Ω Análise assintótica Notação Θ Notações o, ω Notação O : Exemplo 08 Suponha que f (n) = 3 + 2/n e que g(n) = n0 , ou seja,g(n) = 1. Então, para n > 2: 3 + 2/n 6 3 + 1 = 4 = 4n0. Resumindo: f (n) 6 4g(n) para todo n > 2 Portanto, f (n) = O(g(n)). Giovani Bernardes Vitor Aula 03: Complexidade Assintótica 19 Agosto 2024 16 / 34  Análise assintótica Tópicos Notação O Introdução Notação Ω Análise assintótica Notação Θ Notações o, ω Algumas Operações com a Notação O Giovani Bernardes Vitor Aula 03: Complexidade Assintótica 19 Agosto 2024 17 / 34  Análise assintótica Tópicos Notação O Introdução Notação Ω Análise assintótica Notação Θ Notações o, ω Notação O: Exemplo 9 f (N) = O(7 ∗ O(1) + 2 ∗ O(N)) = O(O(1) + O(N)) = O(N) Giovani Bernardes Vitor Aula 03: Complexidade Assintótica 19 Agosto 2024 18 / 34  Análise assintótica Tópicos Notação O Introdução Notação Ω Análise assintótica Notação Θ Notações o, ω Notação Assintótica Terminologia de classes mais comuns de funções: Logarítmica - O(logn) Linear - O(n) Quadrática - O(n2 ) Polinomial - O(nk ) com k > 1 Exponencial - O(an ), com a > 1 Giovani Bernardes Vitor Aula 03: Complexidade Assintótica 19 Agosto 2024 19 / 34  Análise assintótica Tópicos Notação O Introdução Notação Ω Análise assintótica Notação Θ Notações o, ω Ordens mais comuns Giovani Bernardes Vitor Aula 03: Complexidade Assintótica 19 Agosto 2024 20 / 34  Análise assintótica Tópicos Notação O Introdução Notação Ω Análise assintótica Notação Θ Notações o, ω Notação Ω Giovani Bernardes Vitor Aula 03: Complexidade Assintótica 19 Agosto 2024 21 / 34  Análise assintótica Tópicos Notação O Introdução Notação Ω Análise assintótica Notação Θ Notações o, ω Notação Ω A notação Ω define um limite inferior para a função, por um fator cons- tante. Escreve-se f (n) = Ω(g(n)), se existirem constantes positivas c e n0 tais que para n > n0 , o valor de f (n) é maior ou igual a c.g(n). Pode-se dizer que g(n) é um limite assintótico inferior (em inglês, asymptoti- cally lower bound) para f (n). f (n) = Ω(g(n)), ∃ c > 0 e n0 |0 6 c.g(n) 6 f (n), ∀n > n0 Giovani Bernardes Vitor Aula 03: Complexidade Assintótica 19 Agosto 2024 22 / 34  Análise assintótica Tópicos Notação O Introdução Notação Ω Análise assintótica Notação Θ Notações o, ω Notação Ω Quando a notação Ω é usada para expressar o tempo de execução de um algoritmo no melhor caso, está se definindo também o limite (inferior) do tempo de execução desse algoritmo para todas as entradas. Por exemplo, o algoritmo de ordenação por inserção é Ω(n) no melhor caso. O tempo de execução do algoritmo de ordenação por inserção é Ω(n).. O que significa dizer que “o tempo de execução” (i.e., sem especificar se é para o pior caso, melhor caso, ou caso médio) é Ω(g(n))? O tempo de execução desse algoritmo é pelo menos uma constante vezes g(n) para valores suficientemente grandes de n. Giovani Bernardes Vitor Aula 03: Complexidade Assintótica 19 Agosto 2024 23 / 34  Análise assintótica Tópicos Notação O Introdução Notação Ω Análise assintótica Notação Θ Notações o, ω Notação Ω Quando a notação Ω é usada para expressar o tempo de execução de um algoritmo no melhor caso, está se definindo também o limite (inferior) do tempo de execução desse algoritmo para todas as entradas. Por exemplo, o algoritmo de ordenação por inserção é Ω(n) no melhor caso. O tempo de execução do algoritmo de ordenação por inserção é Ω(n).. O que significa dizer que “o tempo de execução” (i.e., sem especificar se é para o pior caso, melhor caso, ou caso médio) é Ω(g(n))? O tempo de execução desse algoritmo é pelo menos uma constante vezes g(n) para valores suficientemente grandes de n. Giovani Bernardes Vitor Aula 03: Complexidade Assintótica 19 Agosto 2024 23 / 34  Análise assintótica Tópicos Notação O Introdução Notação Ω Análise assintótica Notação Θ Notações o, ω Notação Ω: Exemplos Para mostrar que f (n) = 3n3 + 2n2 é Ω(n3 ) basta fazer c = 1, e então 3n3 + 2n2 > n3 para n > 0. Seja f (n) = n para n ímpar (n > 1) e f (n) = n2 /10 para n par (n > 0). Neste caso f (n) é Ω(n2 ), bastando considerar c = 1/10 e n = 0, 2, 4, 6,... Giovani Bernardes Vitor Aula 03: Complexidade Assintótica 19 Agosto 2024 24 / 34  Análise assintótica Tópicos Notação O Introdução Notação Ω Análise assintótica Notação Θ Notações o, ω Notação Ω: Exemplos Para mostrar que f (n) = 3n3 + 2n2 é Ω(n3 ) basta fazer c = 1, e então 3n3 + 2n2 > n3 para n > 0. Seja f (n) = n para n ímpar (n > 1) e f (n) = n2 /10 para n par (n > 0). Neste caso f (n) é Ω(n2 ), bastando considerar c = 1/10 e n = 0, 2, 4, 6,... Giovani Bernardes Vitor Aula 03: Complexidade Assintótica 19 Agosto 2024 24 / 34  Análise assintótica Tópicos Notação O Introdução Notação Ω Análise assintótica Notação Θ Notações o, ω Notação Θ Giovani Bernardes Vitor Aula 03: Complexidade Assintótica 19 Agosto 2024 25 / 34  Análise assintótica Tópicos Notação O Introdução Notação Ω Análise assintótica Notação Θ Notações o, ω Notação Θ A notação Θ limita a função por fatores constantes. Escreve-se f (n) = Θ(g(n)), se existirem constantes positivas c1 , c2 e n0 tais que para n > n0 , o valor de f (n) está sempre entre c1.g(n) e c2.g(n). Neste caso, pode-se dizer que g(n) é um limite assintótico firme (em inglês, asymptotically tight bound) para f (n). f (n) = Θ(g(n)), ∃ c1 > 0, c2 > 0 e n0 | 0 6 c1.g(n) 6 f (n) 6 c2.g(n), ∀n > n0 Giovani Bernardes Vitor Aula 03: Complexidade Assintótica 19 Agosto 2024 26 / 34  Análise assintótica Tópicos Notação O Introdução Notação Ω Análise assintótica Notação Θ Notações o, ω Notação Ω: Exemplos Mostre que 12 n2 − 3n = Θ(n2 ) Para provar esta afirmação, devemos achar as constantes c1 > 0, c2 > 0, n > 0, tais que: c1 n2 6 12 n2 − 3n 6 c2 n2 para todo n > n0 Se dividirmos a expressão acima por n2 temos: c1 6 1 2 − 3/n 6 c2 Giovani Bernardes Vitor Aula 03: Complexidade Assintótica 19 Agosto 2024 27 / 34  Análise assintótica Tópicos Notação O Introdução Notação Ω Análise assintótica Notação Θ Notações o, ω Notação Ω: Exemplos A inequação mais a direita será sempre válida para qualquer valor de n > 1 ao escolhermos c2 > 12. Da mesma forma, a inequação mais a esquerda será sempre válida para qualquer valor de n > 7 ao escolhermos c1 > 14 1. Assim, ao escolhermos c1 = 1/14, c2 = 1/2 e n0 = 7, podemos verificar que 1/2n2 − 3n = Θ(n2 ). Note que existem outras escolhas para as constantes c1 e c2 , mas o fato importante é que a escolha existe. Note também que a escolha destas constantes depende da função 12 n2 − 3n. Uma função diferente pertencente a Θ(n2 ) irá provavelmente requerer outras constantes. Giovani Bernardes Vitor Aula 03: Complexidade Assintótica 19 Agosto 2024 28 / 34  Análise assintótica Tópicos Notação O Introdução Notação Ω Análise assintótica Notação Θ Notações o, ω Notação Ω: Exemplos A inequação mais a direita será sempre válida para qualquer valor de n > 1 ao escolhermos c2 > 12. Da mesma forma, a inequação mais a esquerda será sempre válida para qualquer valor de n > 7 ao escolhermos c1 > 14 1. Assim, ao escolhermos c1 = 1/14, c2 = 1/2 e n0 = 7, podemos verificar que 1/2n2 − 3n = Θ(n2 ). Note que existem outras escolhas para as constantes c1 e c2 , mas o fato importante é que a escolha existe. Note também que a escolha destas constantes depende da função 12 n2 − 3n. Uma função diferente pertencente a Θ(n2 ) irá provavelmente requerer outras constantes. Giovani Bernardes Vitor Aula 03: Complexidade Assintótica 19 Agosto 2024 28 / 34  Análise assintótica Tópicos Notação O Introdução Notação Ω Análise assintótica Notação Θ Notações o, ω Notação Ω: Exemplos A inequação mais a direita será sempre válida para qualquer valor de n > 1 ao escolhermos c2 > 12. Da mesma forma, a inequação mais a esquerda será sempre válida para qualquer valor de n > 7 ao escolhermos c1 > 14 1. Assim, ao escolhermos c1 = 1/14, c2 = 1/2 e n0 = 7, podemos verificar que 1/2n2 − 3n = Θ(n2 ). Note que existem outras escolhas para as constantes c1 e c2 , mas o fato importante é que a escolha existe. Note também que a escolha destas constantes depende da função 12 n2 − 3n. Uma função diferente pertencente a Θ(n2 ) irá provavelmente requerer outras constantes. Giovani Bernardes Vitor Aula 03: Complexidade Assintótica 19 Agosto 2024 28 / 34  Análise assintótica Tópicos Notação O Introdução Notação Ω Análise assintótica Notação Θ Notações o, ω Notação Ω: Exemplos A inequação mais a direita será sempre válida para qualquer valor de n > 1 ao escolhermos c2 > 12. Da mesma forma, a inequação mais a esquerda será sempre válida para qualquer valor de n > 7 ao escolhermos c1 > 14 1. Assim, ao escolhermos c1 = 1/14, c2 = 1/2 e n0 = 7, podemos verificar que 1/2n2 − 3n = Θ(n2 ). Note que existem outras escolhas para as constantes c1 e c2 , mas o fato importante é que a escolha existe. Note também que a escolha destas constantes depende da função 12 n2 − 3n. Uma função diferente pertencente a Θ(n2 ) irá provavelmente requerer outras constantes. Giovani Bernardes Vitor Aula 03: Complexidade Assintótica 19 Agosto 2024 28 / 34  Análise assintótica Tópicos Notação O Introdução Notação Ω Análise assintótica Notação Θ Notações o, ω Notação Ω: Exemplos A inequação mais a direita será sempre válida para qualquer valor de n > 1 ao escolhermos c2 > 12. Da mesma forma, a inequação mais a esquerda será sempre válida para qualquer valor de n > 7 ao escolhermos c1 > 14 1. Assim, ao escolhermos c1 = 1/14, c2 = 1/2 e n0 = 7, podemos verificar que 1/2n2 − 3n = Θ(n2 ). Note que existem outras escolhas para as constantes c1 e c2 , mas o fato importante é que a escolha existe. Note também que a escolha destas constantes depende da função 12 n2 − 3n. Uma função diferente pertencente a Θ(n2 ) irá provavelmente requerer outras constantes. Giovani Bernardes Vitor Aula 03: Complexidade Assintótica 19 Agosto 2024 28 / 34  Análise assintótica Tópicos Notação O Introdução Notação Ω Análise assintótica Notação Θ Notações o, ω Notação Ω: Exemplos A inequação mais a direita será sempre válida para qualquer valor de n > 1 ao escolhermos c2 > 12. Da mesma forma, a inequação mais a esquerda será sempre válida para qualquer valor de n > 7 ao escolhermos c1 > 14 1. Assim, ao escolhermos c1 = 1/14, c2 = 1/2 e n0 = 7, podemos verificar que 1/2n2 − 3n = Θ(n2 ). Note que existem outras escolhas para as constantes c1 e c2 , mas o fato importante é que a escolha existe. Note também que a escolha destas constantes depende da função 12 n2 − 3n. Uma função diferente pertencente a Θ(n2 ) irá provavelmente requerer outras constantes. Giovani Bernardes Vitor Aula 03: Complexidade Assintótica 19 Agosto 2024 28 / 34  Análise assintótica Tópicos Notação O Introdução Notação Ω Análise assintótica Notação Θ Notações o, ω TEOREMA Para quaisquer funções f (n) e g(n), f (n) = Θ(g(n)) se e somente se, f (n) = O(g(n)), e f (n) = Ω(g(n)) Giovani Bernardes Vitor Aula 03: Complexidade Assintótica 19 Agosto 2024 29 / 34  Análise assintótica Tópicos Notação O Introdução Notação Ω Análise assintótica Notação Θ Notações o, ω Notação Assintótica Mais sobre notação assintótica de funções Existem duas outras notações na análise assintótica de funções: Notação o (“O” pequeno) Notação ω Estas duas notações não são usadas normalmente, mas é importante saber seus conceitos e diferenças em relação às notações O e Ω, res- pectivamente. Giovani Bernardes Vitor Aula 03: Complexidade Assintótica 19 Agosto 2024 30 / 34  Análise assintótica Tópicos Notação O Introdução Notação Ω Análise assintótica Notação Θ Notações o, ω Notação o O limite assintótico superior definido pela notação O pode ser assintoti- camente firme ou não. Por exemplo, o limite 2n2 = O(n2 ) é assintóticamente firme, mas o limite 2n = O(n2 ) não é. A notação o é usada para definir um limite superior que não é assintoti- camente firme. Formalmente a notação o é definida como: f (n) = o(g(n)), para qq c > 0 e n0 | 0 6 f (n) < c.g(n), ∀n > n0. Exemplo, 2n = o(n2 ) mas 2n2 6= o(n2 ) Giovani Bernardes Vitor Aula 03: Complexidade Assintótica 19 Agosto 2024 31 / 34  Análise assintótica Tópicos Notação O Introdução Notação Ω Análise assintótica Notação Θ Notações o, ω Notação o O limite assintótico superior definido pela notação O pode ser assintoti- camente firme ou não. Por exemplo, o limite 2n2 = O(n2 ) é assintóticamente firme, mas o limite 2n = O(n2 ) não é. A notação o é usada para definir um limite superior que não é assintoti- camente firme. Formalmente a notação o é definida como: f (n) = o(g(n)), para qq c > 0 e n0 | 0 6 f (n) < c.g(n), ∀n > n0. Exemplo, 2n = o(n2 ) mas 2n2 6= o(n2 ) Giovani Bernardes Vitor Aula 03: Complexidade Assintótica 19 Agosto 2024 31 / 34  Análise assintótica Tópicos Notação O Introdução Notação Ω Análise assintótica Notação Θ Notações o, ω Notação o O limite assintótico superior definido pela notação O pode ser assintoti- camente firme ou não. Por exemplo, o limite 2n2 = O(n2 ) é assintóticamente firme, mas o limite 2n = O(n2 ) não é. A notação o é usada para definir um limite superior que não é assintoti- camente firme. Formalmente a notação o é definida como: f (n) = o(g(n)), para qq c > 0 e n0 | 0 6 f (n) < c.g(n), ∀n > n0. Exemplo, 2n = o(n2 ) mas 2n2 6= o(n2 ) Giovani Bernardes Vitor Aula 03: Complexidade Assintótica 19 Agosto 2024 31 / 34  Análise assintótica Tópicos Notação O Introdução Notação Ω Análise assintótica Notação Θ Notações o, ω Notação o O limite assintótico superior definido pela notação O pode ser assintoti- camente firme ou não. Por exemplo, o limite 2n2 = O(n2 ) é assintóticamente firme, mas o limite 2n = O(n2 ) não é. A notação o é usada para definir um limite superior que não é assintoti- camente firme. Formalmente a notação o é definida como: f (n) = o(g(n)), para qq c > 0 e n0 | 0 6 f (n) < c.g(n), ∀n > n0. Exemplo, 2n = o(n2 ) mas 2n2 6= o(n2 ) Giovani Bernardes Vitor Aula 03: Complexidade Assintótica 19 Agosto 2024 31 / 34  Análise assintótica Tópicos Notação O Introdução Notação Ω Análise assintótica Notação Θ Notações o, ω Notação o As definições das notações O (o grande) e o (o pequeno) são similares. A diferença principal é que em f (n) = O(g(n)), a expressão 0 6 f (n) 6 c.g(n) é válida para todas constantes c > 0. Intuitivamente, a função f (n) tem um crescimento muito menor que g(n) quando n tende para infinito. Isto pode ser expresso da seguinte forma: f (n) limn→∞ g(n) =0 Alguns autores usam este limite como a definição de o. Giovani Bernardes Vitor Aula 03: Complexidade Assintótica 19 Agosto 2024 32 / 34  Análise assintótica Tópicos Notação O Introdução Notação Ω Análise assintótica Notação Θ Notações o, ω Notação ω Por analogia, a notação ω está relacionada com a notação Ω da mesma forma que a notação o está relacionada com a notação O. Formalmente a notação ω é definida como: f (n) = ω(g(n)), para qq c > 0 e n0 | 0 6 c.g(n) < f (n), ∀n > n0. n2 2 Por exemplo, 2 = ω(n), mas n2 6= ω(n2 ). A relação f (n) = ω(g(n)) implica em f (n) limn→∞ g(n) =∞ se o limite existir. Giovani Bernardes Vitor Aula 03: Complexidade Assintótica 19 Agosto 2024 33 / 34  Análise assintótica Tópicos Notação O Introdução Notação Ω Análise assintótica Notação Θ Notações o, ω Referências Notas de aula: Prof. Walter Aoiama Nagai. Disciplina ECO027 - UNIFEI - 2015 Notas de aula: Prof. Eduardo Barrére - UFJF - 2013 Notas de aula: Prof. Antonio Alfredo Ferreira Loureiro - UFMG - 2010 Livro: Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Clifford Stein, Introduction to Algorithms, volume , Editora Prentice-Hall, Segunda edição, (2006) Giovani Bernardes Vitor Aula 03: Complexidade Assintótica 19 Agosto 2024 34 / 34  Ministério da Educação Engenharia da Computação Universidade Federal de Itajubá ECOI11 – PAA Criada pela Lei nº 10.435, 24/04/2002 Prof. Giovani Bernardes Vitor Lista de Exercı́cios #2 1. Conforme apresentado pelos dois algoritmos, faça: —————————————————————————- 1 void Algoritmo1 ( int n ) 2 { 3 int i , j , x , y ; 4 x = y = 0; 5 f o r ( i = 1 ; i