Slide - Comportamento Assintótico - 2022-1

Comportament assintótico Jeroen van de Graaf DCC/UFMG Tópicos ▶ Notação Grande O (3.2) ▶ Algoritmos (3.1) ▶ Complexidade de algoritmos (3.3) Funções dos reais e naturais? ▶ Cálculo: funcões de R para R: x → f (x) ▶ Computação: funcões de N para N+ (# passos de um algoritmo ) ou R+: n → f (n) ▶ Usaremos x → f (x) e n → f (n) interchangeably ▶ Repare que sequências também são funcões de N para R: n → an ▶ Somas são simplesmente sequências especias: s1 = a1; s2 = a1 + a2; s3 = a1 + a2 + a3; ... Funções dos reais e naturais? ▶ Cálculo: funcões de R para R: x → f (x) ▶ Computação: funcões de N para N+ (# passos de um algoritmo ) ou R+: n → f (n) ▶ Usaremos x → f (x) e n → f (n) interchangeably ▶ Repare que sequências também são funcões de N para R: n → an ▶ Somas são simplesmente sequências especias: s1 = a1; s2 = a1 + a2; s3 = a1 + a2 + a3; ... Funções dos reais e naturais? ▶ Cálculo: funcões de R para R: x → f (x) ▶ Computação: funcões de N para N+ (# passos de um algoritmo ) ou R+: n → f (n) ▶ Usaremos x → f (x) e n → f (n) interchangeably ▶ Repare que sequências também são funcões de N para R: n → an ▶ Somas são simplesmente sequências especias: s1 = a1; s2 = a1 + a2; s3 = a1 + a2 + a3; ... Funções dos reais e naturais? ▶ Cálculo: funcões de R para R: x → f (x) ▶ Computação: funcões de N para N+ (# passos de um algoritmo ) ou R+: n → f (n) ▶ Usaremos x → f (x) e n → f (n) interchangeably ▶ Repare que sequências também são funcões de N para R: n → an ▶ Somas são simplesmente sequências especias: s1 = a1; s2 = a1 + a2; s3 = a1 + a2 + a3; ... Como a matemática lida com ‘infinito’? ▶ Brincadeira de criança: Um, dois, três, . . . infinito. Então, infinito é maior que qualquer número (natural ou real) concreto. ▶ Queremos definir um propriedade P(x) quando x → ∞: ▶ informal: existe x0 tal que, para tudo x > x0 : P(x) ▶ o que acontece no intervalo inicial finito [0, x0] é irrelevante ▶ formal: ∃x0∀x > x0 : P(x) ▶ Para números naturais: ▶ existe n0 tal que, para tudo n > n0 : P(n) ▶ > ou ≥ ; tanto faz Como a matemática lida com ‘infinito’? ▶ Brincadeira de criança: Um, dois, três, . . . infinito. Então, infinito é maior que qualquer número (natural ou real) concreto. ▶ Queremos definir um propriedade P(x) quando x → ∞: ▶ informal: existe x0 tal que, para tudo x > x0 : P(x) ▶ o que acontece no intervalo inicial finito [0, x0] é irrelevante ▶ formal: ∃x0∀x > x0 : P(x) ▶ Para números naturais: ▶ existe n0 tal que, para tudo n > n0 : P(n) ▶ > ou ≥ ; tanto faz Como a matemática lida com ‘infinito’? ▶ Brincadeira de criança: Um, dois, três, . . . infinito. Então, infinito é maior que qualquer número (natural ou real) concreto. ▶ Queremos definir um propriedade P(x) quando x → ∞: ▶ informal: existe x0 tal que, para tudo x > x0 : P(x) ▶ o que acontece no intervalo inicial finito [0, x0] é irrelevante ▶ formal: ∃x0∀x > x0 : P(x) ▶ Para números naturais: ▶ existe n0 tal que, para tudo n > n0 : P(n) ▶ > ou ≥ ; tanto faz Comportamento asintótico Gostaríamos de entender o comportamento asintótico de sequências, somas e funções quando n → ∞: Exemplo Sabemos que b_n = 1 + 2 + 3 + ⋯ + n não converge. Comportamento asintótico Gostaríamos de entender o comportamento asintótico de sequências, somas e funções quando n → ∞: Exemplo Sabemos que b_n = 1 + 2 + 3 + ⋯ + n não converge. Exemplo Sabemos que n! não converge Comportamento asintótico Gostaríamos de entender o comportamento asintótico de sequências, somas e funções quando n → ∞: Exemplo Sabemos que b_n = 1 + 2 + 3 + ⋯ + n não converge. Exemplo Sabemos que n! não converge Exemplo Sabemos que c_n = 1 + 1/2 + 1/3 + 1/4 + ⋯ + 1/n não converge, porque 1 + \(1/2\) + \(1/3 + 1/4\) + \(1/5 + 1/6 + 1/7 + 1/8\) + ⋯ > 1 + 1/2 + 1/2 + 1/2 + ⋯ 1 termo 2 termos 4 termos Comportamento assintótico Gostaríamos de entender o comportamento assintótico de sequências, somas e funções quando n → ∞: Exemplo Sabemos que b_n = 1 + 2 + 3 + ... + n não converge. Exemplo Sabemos que n! não converge Exemplo Sabemos que c_n = 1 + 1/2 + 1/3 + 1/4 + ... + 1/n não converge, porque 1 + (1/2)︸1 termo + (1/3 + 1/4)︸2 termos + (1/5 + 1/6 + 1/7 + 1/8)︸4 termos+ ... > 1 + 1/2 + 1/2 + 1/2 + ... Queremos modelar a taxa de crescimento (a não convergência) destas funções, comparando-as com outras Notação grande O – Definição Definição Sejam f , g funções de N para R+. Definimos a classe (= conjunto de funções) O(g) de seguinte maneira: f ∈ O(g) se existir duas constantes C e n0 tal que ∀n > n0 : f (n) ≤ C · g(n) Ou equivalente, ∀n > n0 : f (n) g(n) ≤ C Falamos que, asintoticamente, g é cota (limitante) superior de f a partir de n0. Notação alternativa: [f ] ⪯ [g] ▶ Fala-se ‘f (x) pertence a grande O de g(x)’, ou ‘f é limitada asinoticamente por g.’ ▶ Aviso: Existem livros escrevendo ’‘f = O(g)’‘, falando-se’f é grande O de g’. Mas esta forma de falar pode levar a confusão porque a igualdade não é simétrica nesse caso: O(g) = f não faz sentido. Notação grande O – Definição Definição Sejam f , g funções de N para R+. Definimos a classe (= conjunto de funções) O(g) de seguinte maneira: f ∈ O(g) se existir duas constantes C e n0 tal que ∀n > n0 : f (n) ≤ C · g(n) Ou equivalente, ∀n > n0 : f (n) g(n) ≤ C Falamos que, asintoticamente, g é cota (limitante) superior de f a partir de n0. Notação alternativa: [f ] ⪯ [g] ▶ Fala-se ‘f (x) pertence a grande O de g(x)’, ou ‘f é limitada asinoticamente por g.’ ▶ Aviso: Existem livros escrevendo ’‘f = O(g)’‘, falando-se’f é grande O de g’. Mas esta forma de falar pode levar a confusão porque a igualdade não é simétrica nesse caso: O(g) = f não faz sentido. Notação grande O – Definição Definição Sejam f , g funções de N para R+. Definimos a classe (= conjunto de funções) O(g) de seguinte maneira: f ∈ O(g) se existir duas constantes C e n0 tal que ∀n > n0 : f (n) ≤ C · g(n) Ou equivalente, ∀n > n0 : f (n) g(n) ≤ C Falamos que, asintoticamente, g é cota (limitante) superior de f a partir de n0. Notação alternativa: [f ] ⪯ [g] ▶ Fala-se ‘f (x) pertence a grande O de g(x)’, ou ‘f é limitada asinoticamente por g.’ ▶ Aviso: Existem livros escrevendo ’‘f = O(g)’‘, falando-se’f é grande O de g’. Mas esta forma de falar pode levar a confusão porque a igualdade não é simétrica nesse caso: O(g) = f não faz sentido. Notação grande O – Exemplo Exemplo [3.2.5] b_n = 1 + 2 + 3 + ... + n? Notação grande O – Exemplo Exemplo [3.2.5] b_n = 1 + 2 + 3 + ... + n? Sabemos que b_n < n + n + n + ... + n︸n termos = n^2, então b_n ∈ O(n^2) Notação grande O – Exemplo Exemplo [3.2.1] Mostre que f (x) = x 2 + 2x + 1 ∈ O(x 2). ▶ Para x > 1 temos que 2x < 2x 2 e que 1 < x 2, então 0 ≤ x 2 + 2x + 1 ≤ x 2 + 2x 2 + x 2 = 4x 2 ▶ Então podemos aplicar a definição com C = 4 e x0 = 1. Alternativamente ▶ Para x > 2 temos que 2x < x 2 e que 1 < x 2, então 0 ≤ x 2 + 2x + 1 ≤ x 2 + x 2 + x 2 = 3x 2 ▶ Então podemos aplicar a definição também com C = 3 e x0 = 2. Notação grande O – Exemplo Exemplo [3.2.1] Mostre que f (x) = x 2 + 2x + 1 ∈ O(x 2). ▶ Para x > 1 temos que 2x < 2x 2 e que 1 < x 2, então 0 ≤ x 2 + 2x + 1 ≤ x 2 + 2x 2 + x 2 = 4x 2 ▶ Então podemos aplicar a definição com C = 4 e x0 = 1. Alternativamente ▶ Para x > 2 temos que 2x < x 2 e que 1 < x 2, então 0 ≤ x 2 + 2x + 1 ≤ x 2 + x 2 + x 2 = 3x 2 ▶ Então podemos aplicar a definição também com C = 3 e x0 = 2. Notação grande O – Exemplo Exemplo [3.2.1] Mostre que f (x) = x 2 + 2x + 1 ∈ O(x 2). ▶ Para x > 1 temos que 2x < 2x 2 e que 1 < x 2, então 0 ≤ x 2 + 2x + 1 ≤ x 2 + 2x 2 + x 2 = 4x 2 ▶ Então podemos aplicar a definição com C = 4 e x0 = 1. Alternativamente ▶ Para x > 2 temos que 2x < x 2 e que 1 < x 2, então 0 ≤ x 2 + 2x + 1 ≤ x 2 + x 2 + x 2 = 3x 2 ▶ Então podemos aplicar a definição também com C = 3 e x0 = 2. Notação grande O – diagrama The part of the graph of f(x) = x^2 + 2x + 1 that satisfies f(x) < 4x^2 is shown in color. x^2 + 2x + 1 < 4x^2 for x > 1 Notação grande O – Duvida Dúvida Mostramos que f (x) = x 2 + 2x + 1 ∈ O(x 2) com C = 4, x0 = 1 e com C = 3, x0 = 2. Como escolher as constantes? Faz diferença? Você pode escolher o que é o mais fácil para sua prova; não faz diferença. Vamos provar que a escolha das constantes não faz diferença. Se quiser, você poderia escolher x0 = 1 sempre (mas talvez encontrar C te dará mais trabalho). Notação grande O – Duvida Dúvida Mostramos que f (x) = x 2 + 2x + 1 ∈ O(x 2) com C = 4, x0 = 1 e com C = 3, x0 = 2. Como escolher as constantes? Faz diferença? Você pode escolher o que é o mais fácil para sua prova; não faz diferença. Vamos provar que a escolha das constantes não faz diferença. Se quiser, você poderia escolher x0 = 1 sempre (mas talvez encontrar C te dará mais trabalho). Notação grande O – Observações Observações ▶ Trivialmente f (x) ∈ O(f (x)) sempre ▶ f ∈ O(g) sse O(f ) ⊆ O(g). ▶ Se f (x) ∈ O(g(x)) e g(x) < h(x), então f (x) ∈ O(h(x)). Ou seja, sempre podemos trocar g(x) para qualquer função maior. Por exemplo, se f (x) = x 2 + 2x + 1 ∈ O(x 2), então f (x) ∈ O(x 2 + x + 7); f (x) ∈ O(x 3). Na prática, preferimos usar a função mais simples possível como g, tirando constantes é termos de ordem menor. No exemplo anterior, podemos também mostrar que x 2 ∈ O(x 2 + 2x + 1), então f e g são da mesma ordem. Notação grande O – Observações Observações ▶ Trivialmente f (x) ∈ O(f (x)) sempre ▶ f ∈ O(g) sse O(f ) ⊆ O(g). ▶ Se f (x) ∈ O(g(x)) e g(x) < h(x), então f (x) ∈ O(h(x)). Ou seja, sempre podemos trocar g(x) para qualquer função maior. Por exemplo, se f (x) = x 2 + 2x + 1 ∈ O(x 2), então f (x) ∈ O(x 2 + x + 7); f (x) ∈ O(x 3). Na prática, preferimos usar a função mais simples possível como g, tirando constantes é termos de ordem menor. No exemplo anterior, podemos também mostrar que x 2 ∈ O(x 2 + 2x + 1), então f e g são da mesma ordem. Notação grande O – Observações Observações ▶ Trivialmente f (x) ∈ O(f (x)) sempre ▶ f ∈ O(g) sse O(f ) ⊆ O(g). ▶ Se f (x) ∈ O(g(x)) e g(x) < h(x), então f (x) ∈ O(h(x)). Ou seja, sempre podemos trocar g(x) para qualquer função maior. Por exemplo, se f (x) = x 2 + 2x + 1 ∈ O(x 2), então f (x) ∈ O(x 2 + x + 7); f (x) ∈ O(x 3). Na prática, preferimos usar a função mais simples possível como g, tirando constantes é termos de ordem menor. No exemplo anterior, podemos também mostrar que x 2 ∈ O(x 2 + 2x + 1), então f e g são da mesma ordem. Notação grande O – Observações Observações ▶ Trivialmente f (x) ∈ O(f (x)) sempre ▶ f ∈ O(g) sse O(f ) ⊆ O(g). ▶ Se f (x) ∈ O(g(x)) e g(x) < h(x), então f (x) ∈ O(h(x)). Ou seja, sempre podemos trocar g(x) para qualquer função maior. Por exemplo, se f (x) = x 2 + 2x + 1 ∈ O(x 2), então f (x) ∈ O(x 2 + x + 7); f (x) ∈ O(x 3). Na prática, preferimos usar a função mais simples possível como g, tirando constantes é termos de ordem menor. No exemplo anterior, podemos também mostrar que x 2 ∈ O(x 2 + 2x + 1), então f e g são da mesma ordem. Notação grande O – Exemplo Exemplo [3.2.2] Mostre que 7x 2 ∈ O(x 3). Solução Para x > 7 temos que 7 · x 2 < x · x 2 = x 3, então obtemos que C = 1; x0 = 7. Ou: Para x > 1 temos que 7 · x 2 < 7 · x 2 · x = 7x 3, então obtemos que C = 7; x0 = 1. Notação grande O – Exemplo Exemplo [3.2.2] Mostre que 7x 2 ∈ O(x 3). Solução Para x > 7 temos que 7 · x 2 < x · x 2 = x 3, então obtemos que C = 1; x0 = 7. Ou: Para x > 1 temos que 7 · x 2 < 7 · x 2 · x = 7x 3, então obtemos que C = 7; x0 = 1. ∗ A escolha n0 e C importa? ▶ Para provar que f ∈ O(g), a escolha dos constantes faz diferença? NÃO! ▶ Posso escolher n0 = 1 sempre? SIM! ∗ A escolha n0 e C importa? ▶ Para provar que f ∈ O(g), a escolha dos constantes faz diferença? NÃO! ▶ Posso escolher n0 = 1 sempre? SIM! ∗ A escolha n0 e C importa? Definição alternativa (com n0 = 1 sempre) Sejam f , g funções de N para R+. Definimos a classe (o conjunto) de funções O(g) de seguinte maneira: f ∈ O(g) se houver um constante C tal que ∀n > 0 : f (n) g(n) ≤ C Teorema A definição alternativa é equivalente à definição original. Prova [=⇒] O constante C de n0 = 1 serve para qualquer n0, já que f (n) g(n) ≤ C para todo n > 0 implica que f (n) g(n) ≤ C para todo n > n0 * A escolha n_0 e C importa? Definição alternativa Sejam f, g funções de ℕ para ℝ⁺. Definimos a classe (o conjunto) de funções O(g) de seguinte maneira: f ∈ O(g) se houver um constante C tal que ∀ n > 0 : f(n)/g(n) ≤ C Teorema A definição alternativa é equivalente à definição original. [⇐] Sejam C e n_0 os constantes da definição original. Defina os conjuntos dos quocientes de f e g nos intervalos [1, n_0] e [n_0 + 1, ∞) Q_1 = { f(n)/g(n) | 1 ≤ n ≤ n_0 } Q_2 = { f(n)/g(n) | n_0 < n } Sabemos que Q_1 tem um máximo, digamos M, enquanto o C da definição original é uma cota superior de Q_2. Então f(n)/g(n) < C' = max(M, C) para todo n > 0, então C' é o constante que corresponde para n_0 = 1, na definição alternativa. Notação grande O – Exemplo Exemplo [3.2.3] Mostre que n2 /∈ O(n). Solução Precisamos mostrar que não existe C e n0 tal que f (n) ≤ C · g(n). Substituindo e dividindo, obtemos n2 n = n ≤ C. Fica evidente que, não importa o valor de n0 e C, a desigualdade nunca é válida para todo n > n0. Notação grande O – Exemplo Exemplo [3.2.3] Mostre que n2 /∈ O(n). Solução Precisamos mostrar que não existe C e n0 tal que f (n) ≤ C · g(n). Substituindo e dividindo, obtemos n2 n = n ≤ C. Fica evidente que, não importa o valor de n0 e C, a desigualdade nunca é válida para todo n > n0. Notação grande O – Exemplo Exemplo [3.2.4] Mostre que x 3 /∈ O(7x 2). Solução Precisamos mostrar que não existe C e n0 tal que f (x) ≤ C · g(x). Substituindo e dividindo, obtemos x 3 7x 2 ≤ C =⇒ x ≤ 7 · C Fica evidente que, para x → ∞, não existe um C para que a desigualdade continua válida. Notação grande O – Exemplo Exemplo [3.2.4] Mostre que x 3 /∈ O(7x 2). Solução Precisamos mostrar que não existe C e n0 tal que f (x) ≤ C · g(x). Substituindo e dividindo, obtemos x 3 7x 2 ≤ C =⇒ x ≤ 7 · C Fica evidente que, para x → ∞, não existe um C para que a desigualdade continua válida. Notação grande O – Teorema do polinômio Teorema [3.2.1] Suponha an ∈ R>0 e f (x) = anx n + an−1x n−1 + . . . a1x + a0. Então f (x) ∈ O(x n). Prova Suponha x > x0 = 1 e C = |an| + |an−1| + . . . + |a0|. Então |f (x)| = |anx n + an−1x n−1 + . . . a1x + a0| ≤ |an|x n + |an−1|x n−1 + . . . |a1|x + |a0| = x n(|an| + |an−1|/x + . . . |a1|/x n−1 + |a0|/x n) ≤ x n(|an| + |an−1| + . . . |a1| + |a0|) = C · x n Notação grande O – Teorema do polinômio Teorema [3.2.1] Suponha an ∈ R>0 e f (x) = anx n + an−1x n−1 + . . . a1x + a0. Então f (x) ∈ O(x n). Prova Suponha x > x0 = 1 e C = |an| + |an−1| + . . . + |a0|. Então |f (x)| = |anx n + an−1x n−1 + . . . a1x + a0| ≤ |an|x n + |an−1|x n−1 + . . . |a1|x + |a0| = x n(|an| + |an−1|/x + . . . |a1|/x n−1 + |a0|/x n) ≤ x n(|an| + |an−1| + . . . |a1| + |a0|) = C · x n Notação grande O – caracterize O(1) Pergunta Dê exemplos de uma função f tal que f (x) ∈ O(1). Caracterize O(1) em palavras. ▶ repare que O(1) = O(24) = O(10100) = O(C) ▶ repare que sin(x) + 1 oscila entre 0 e 2 ▶ f (x) não vai para infinito se n → ∞ ▶ ou seja, ∃C : f (x) < C Notação grande O – caracterize O(1) Pergunta Dê exemplos de uma função f tal que f (x) ∈ O(1). Caracterize O(1) em palavras. ▶ repare que O(1) = O(24) = O(10100) = O(C) ▶ repare que sin(x) + 1 oscila entre 0 e 2 ▶ f (x) não vai para infinito se n → ∞ ▶ ou seja, ∃C : f (x) < C Notação grande O – caracterize O(1) Pergunta Dê exemplos de uma função f tal que f (x) ∈ O(1). Caracterize O(1) em palavras. ▶ repare que O(1) = O(24) = O(10100) = O(C) ▶ repare que sin(x) + 1 oscila entre 0 e 2 ▶ f (x) não vai para infinito se n → ∞ ▶ ou seja, ∃C : f (x) < C Notação grande O – caracterize O(1) Pergunta Dê exemplos de uma função f tal que f (x) ∈ O(1). Caracterize O(1) em palavras. ▶ repare que O(1) = O(24) = O(10100) = O(C) ▶ repare que sin(x) + 1 oscila entre 0 e 2 ▶ f (x) não vai para infinito se n → ∞ ▶ ou seja, ∃C : f (x) < C Notação grande O – Exemplo Exemplo [3.2.6] Mostre que n! ∈ O(nn). Solução n! = 1 · 2 · 3 · · · n ≤ n · n · n · · · n = nn Essa é uma cota superior. Uma aproximação mais precisa é n! = √ 2πn( n e )n. Existem aproximações mais precisas (fórmula de Stirling). Tomando o log dos dois lados, obtemos log n! ≤ log nn = n log n então log n! ∈ O(n log n). Notação grande O – Exemplo Exemplo [3.2.6] Mostre que n! ∈ O(nn). Solução n! = 1 · 2 · 3 · · · n ≤ n · n · n · · · n = nn Essa é uma cota superior. Uma aproximação mais precisa é n! = √ 2πn( n e )n. Existem aproximações mais precisas (fórmula de Stirling). Tomando o log dos dois lados, obtemos log n! ≤ log nn = n log n então log n! ∈ O(n log n). Notação grande O – Exemplo Exemplo [3.2.6] Mostre que n! ∈ O(nn). Solução n! = 1 · 2 · 3 · · · n ≤ n · n · n · · · n = nn Essa é uma cota superior. Uma aproximação mais precisa é n! = √ 2πn( n e )n. Existem aproximações mais precisas (fórmula de Stirling). Tomando o log dos dois lados, obtemos log n! ≤ log nn = n log n então log n! ∈ O(n log n). Notação grande O – Exemplo Exemplo [3.2.6] Mostre que n! ∈ O(nn). Solução n! = 1 · 2 · 3 · · · n ≤ n · n · n · · · n = nn Essa é uma cota superior. Uma aproximação mais precisa é n! = √ 2πn( n e )n. Existem aproximações mais precisas (fórmula de Stirling). Tomando o log dos dois lados, obtemos log n! ≤ log nn = n log n então log n! ∈ O(n log n). Notação grande O – Teoremas Teorema (transitividade) Se f (x) ∈ O(g(x)) e g(x) ∈ O(h(x)), então f (x) ∈ O(h(x)). Prova Exercício para o aluno. Notação grande O – Teoremas Teorema (transitividade) Se f (x) ∈ O(g(x)) e g(x) ∈ O(h(x)), então f (x) ∈ O(h(x)). Prova Exercício para o aluno. Notação grande O – Teoremas Teorema [3.2.2 – maximo] Suponha que f1 ∈ O(g1) e f2 ∈ O(g2). Então (f1 + f2) ∈ O(max(g1, g2)). Prova Sabemos que existem contantes C1, x1 tal que f1(x) ≤ C1 · g1(x) para x > x1. Analogamente existem contantes C2, x2 tal que f2(x) ≤ C2 · g2(x) para x > x2. Então, para x > x3 = max(x1, x2): (f1 + f2)(x) = f1(x) + f2(x) ≤ C1 · g1(x) + C2 · g2(x) ≤ C1 · max(g1(x), g2(x)) + C2 · max(g1(x), g2(x)) ≤ (C1 + C2) · max(g1(x), g2(x)) Portanto C3 = C1 + C2 e x3 = max(x1, x2) são os constantes. Notação grande O – Teoremas Teorema [3.2.2 – maximo] Suponha que f1 ∈ O(g1) e f2 ∈ O(g2). Então (f1 + f2) ∈ O(max(g1, g2)). Prova Sabemos que existem contantes C1, x1 tal que f1(x) ≤ C1 · g1(x) para x > x1. Analogamente existem contantes C2, x2 tal que f2(x) ≤ C2 · g2(x) para x > x2. Então, para x > x3 = max(x1, x2): (f1 + f2)(x) = f1(x) + f2(x) ≤ C1 · g1(x) + C2 · g2(x) ≤ C1 · max(g1(x), g2(x)) + C2 · max(g1(x), g2(x)) ≤ (C1 + C2) · max(g1(x), g2(x)) Portanto C3 = C1 + C2 e x3 = max(x1, x2) são os constantes. Notação grande O – Teoremas Teorema [3.2.2 – maximo] Suponha que f1 ∈ O(g1) e f2 ∈ O(g2). Então (f1 + f2) ∈ O(max(g1, g2)). Prova Sabemos que existem contantes C1, x1 tal que f1(x) ≤ C1 · g1(x) para x > x1. Analogamente existem contantes C2, x2 tal que f2(x) ≤ C2 · g2(x) para x > x2. Então, para x > x3 = max(x1, x2): (f1 + f2)(x) = f1(x) + f2(x) ≤ C1 · g1(x) + C2 · g2(x) ≤ C1 · max(g1(x), g2(x)) + C2 · max(g1(x), g2(x)) ≤ (C1 + C2) · max(g1(x), g2(x)) Portanto C3 = C1 + C2 e x3 = max(x1, x2) são os constantes. Notação grande O – Teoremas Teorema [Corolário 3.2.1 – soma] Se f1, f2 ∈ O(g), então f1 + f2 ∈ O(g). Prova 1 Sabemos que existem contantes C1, x1 tal que f1(x) ≤ C1 · g(x) para x > x1. Analogamente existem contantes C2, x2 tal que f2(x) ≤ C2 · g(x) para x > x2. Fica claro que, para os constantes C3 = C1 + C2 e x3 = max(x1, x2) temos que f1(x) + f2(x) ≤ C1 · g(x) + C2 · g(x) = C3 · g(x) para x > x3 Prova 2 (do livro) Aplique o teorema anterior com g1 = g2 = g, e nota que max(g, g) = g. Notação grande O – Teoremas Teorema [Corolário 3.2.1 – soma] Se f1, f2 ∈ O(g), então f1 + f2 ∈ O(g). Prova 1 Sabemos que existem contantes C1, x1 tal que f1(x) ≤ C1 · g(x) para x > x1. Analogamente existem contantes C2, x2 tal que f2(x) ≤ C2 · g(x) para x > x2. Fica claro que, para os constantes C3 = C1 + C2 e x3 = max(x1, x2) temos que f1(x) + f2(x) ≤ C1 · g(x) + C2 · g(x) = C3 · g(x) para x > x3 Prova 2 (do livro) Aplique o teorema anterior com g1 = g2 = g, e nota que max(g, g) = g. Notação grande O – Teoremas Teorema [Corolário 3.2.1 – soma] Se f1, f2 ∈ O(g), então f1 + f2 ∈ O(g). Prova 1 Sabemos que existem contantes C1, x1 tal que f1(x) ≤ C1 · g(x) para x > x1. Analogamente existem contantes C2, x2 tal que f2(x) ≤ C2 · g(x) para x > x2. Fica claro que, para os constantes C3 = C1 + C2 e x3 = max(x1, x2) temos que f1(x) + f2(x) ≤ C1 · g(x) + C2 · g(x) = C3 · g(x) para x > x3 Prova 2 (do livro) Aplique o teorema anterior com g1 = g2 = g, e nota que max(g, g) = g. Notação grande O – Teoremas Teorema [3.2.1 – polinomio – prova alternativa] Suponha an ∈ R>0 e f (x) = anx n + an−1x n−1 + . . . a1x + a0. Então f (x) ∈ O(x n). Prova alternativa A prova é por indução no número de termos: aplicando o teorema anterior, prova-se que x k ∈ O(x n) se k < n. Fica claro que x n é o termo cuja ordem é o máximo. Notação grande O – Teoremas Teorema [3.2.1 – polinomio – prova alternativa] Suponha an ∈ R>0 e f (x) = anx n + an−1x n−1 + . . . a1x + a0. Então f (x) ∈ O(x n). Prova alternativa A prova é por indução no número de termos: aplicando o teorema anterior, prova-se que x k ∈ O(x n) se k < n. Fica claro que x n é o termo cuja ordem é o máximo. Notação grande O – Teoremas Teorema [3.2.3 – produto] Se f1(x) ∈ O(g1(x)) e f2(x) ∈ O(g2(x)), então (f1 · f2)(x) ∈ O(g1(x) · g2(x)). Prova Exercício Notação grande O – Teoremas Teorema [3.2.3 – produto] Se f1(x) ∈ O(g1(x)) e f2(x) ∈ O(g2(x)), então (f1 · f2)(x) ∈ O(g1(x) · g2(x)). Prova Exercício Resumo c · f (n) ∈ O(f (n)) para c um constante f (x) ∈ O(g(x)) ∧ g(x) ∈ O(h(x)) ⇒ f (x) ∈ O(h(x)) f1 ∈ O(g1) ∧ f2 ∈ O(g2) =⇒ (f1 + f2) ∈ O(max(g1, g2)) f1, f2 ∈ O(g) =⇒ f1 + f2 ∈ O(g) f1(x) ∈ O(g1(x)) ∧ f2(x) ∈ O(g2(x)) =⇒ (f1 · f2)(x) ∈ O(g1(x) · g2(x)) nk ∈ O(nl) se k ≤ l Notação grande O Exemplo [3.2.8] Estime a ordem de f (n) = 3n log n! + (n2 + 3) log n ▶ log n! ∈ O(n log n) então 3n log n! ∈ O(n2 log n) ▶ (n2 + 3) < 2n2 ∈ O(n2) então (n2 + 3) log n ∈ O(n2 log n) ▶ Conclusão: f (n) = 3n log n! + (n2 + 3) log n ∈ O(n2 log n) Notação grande O Exemplo [3.2.8] Estime a ordem de f (n) = 3n log n! + (n2 + 3) log n ▶ log n! ∈ O(n log n) então 3n log n! ∈ O(n2 log n) ▶ (n2 + 3) < 2n2 ∈ O(n2) então (n2 + 3) log n ∈ O(n2 log n) ▶ Conclusão: f (n) = 3n log n! + (n2 + 3) log n ∈ O(n2 log n) Notação grande O Exemplo [3.2.8] Estime a ordem de f (n) = 3n log n! + (n2 + 3) log n ▶ log n! ∈ O(n log n) então 3n log n! ∈ O(n2 log n) ▶ (n2 + 3) < 2n2 ∈ O(n2) então (n2 + 3) log n ∈ O(n2 log n) ▶ Conclusão: f (n) = 3n log n! + (n2 + 3) log n ∈ O(n2 log n) Notação grande O Exemplo [3.2.8] Estime a ordem de f (n) = 3n log n! + (n2 + 3) log n ▶ log n! ∈ O(n log n) então 3n log n! ∈ O(n2 log n) ▶ (n2 + 3) < 2n2 ∈ O(n2) então (n2 + 3) log n ∈ O(n2 log n) ▶ Conclusão: f (n) = 3n log n! + (n2 + 3) log n ∈ O(n2 log n) Notação grande O Exemplo [3.2.9] Estime a ordem de f (x) = (x + 1) log(x 2 + 1) + 3x 2 ▶ x + 1 ∈ O(x) ▶ Já que log(x 2 + 1) ≤ log(2x 2) = log 2 + log x 2 = log 2 + 2 log x ≤ 3 log x temos que log(x 2 + 1) ∈ O(log x) ▶ Então (x + 1) log(x 2 + 1) ∈ O(x log x) ▶ 3x 2 ∈ O(x 2) ▶ Então f (x) = (x + 1) log(x 2 + 1) + 3x 2 ∈ O(x 2) Notação grande O Exemplo [3.2.9] Estime a ordem de f (x) = (x + 1) log(x 2 + 1) + 3x 2 ▶ x + 1 ∈ O(x) ▶ Já que log(x 2 + 1) ≤ log(2x 2) = log 2 + log x 2 = log 2 + 2 log x ≤ 3 log x temos que log(x 2 + 1) ∈ O(log x) ▶ Então (x + 1) log(x 2 + 1) ∈ O(x log x) ▶ 3x 2 ∈ O(x 2) ▶ Então f (x) = (x + 1) log(x 2 + 1) + 3x 2 ∈ O(x 2) Notação grande O Exemplo [3.2.9] Estime a ordem de f (x) = (x + 1) log(x 2 + 1) + 3x 2 ▶ x + 1 ∈ O(x) ▶ Já que log(x 2 + 1) ≤ log(2x 2) = log 2 + log x 2 = log 2 + 2 log x ≤ 3 log x temos que log(x 2 + 1) ∈ O(log x) ▶ Então (x + 1) log(x 2 + 1) ∈ O(x log x) ▶ 3x 2 ∈ O(x 2) ▶ Então f (x) = (x + 1) log(x 2 + 1) + 3x 2 ∈ O(x 2) Notação grande O Exemplo [3.2.9] Estime a ordem de f (x) = (x + 1) log(x 2 + 1) + 3x 2 ▶ x + 1 ∈ O(x) ▶ Já que log(x 2 + 1) ≤ log(2x 2) = log 2 + log x 2 = log 2 + 2 log x ≤ 3 log x temos que log(x 2 + 1) ∈ O(log x) ▶ Então (x + 1) log(x 2 + 1) ∈ O(x log x) ▶ 3x 2 ∈ O(x 2) ▶ Então f (x) = (x + 1) log(x 2 + 1) + 3x 2 ∈ O(x 2) Notação grande O Exemplo [3.2.9] Estime a ordem de f (x) = (x + 1) log(x 2 + 1) + 3x 2 ▶ x + 1 ∈ O(x) ▶ Já que log(x 2 + 1) ≤ log(2x 2) = log 2 + log x 2 = log 2 + 2 log x ≤ 3 log x temos que log(x 2 + 1) ∈ O(log x) ▶ Então (x + 1) log(x 2 + 1) ∈ O(x log x) ▶ 3x 2 ∈ O(x 2) ▶ Então f (x) = (x + 1) log(x 2 + 1) + 3x 2 ∈ O(x 2) Notação grande O Exemplo [3.2.9] Estime a ordem de f (x) = (x + 1) log(x 2 + 1) + 3x 2 ▶ x + 1 ∈ O(x) ▶ Já que log(x 2 + 1) ≤ log(2x 2) = log 2 + log x 2 = log 2 + 2 log x ≤ 3 log x temos que log(x 2 + 1) ∈ O(log x) ▶ Então (x + 1) log(x 2 + 1) ∈ O(x log x) ▶ 3x 2 ∈ O(x 2) ▶ Então f (x) = (x + 1) log(x 2 + 1) + 3x 2 ∈ O(x 2) Notação grande Ômega Definição Sejam f , g funções de N ou R para R+. Então f (x) ∈ O(g(x)) se houver constantes C e x0 tal que ∀x > x0 : f (x) ≥ Cg(x) Ou seja, f (x) ∈ Ω(g(x)) se g(x) ∈ O(f (x)). Notação grande Ômega Definição Sejam f , g funções de N ou R para R+. Então f (x) ∈ O(g(x)) se houver constantes C e x0 tal que ∀x > x0 : f (x) ≥ Cg(x) Ou seja, f (x) ∈ Ω(g(x)) se g(x) ∈ O(f (x)). Notação grande Ômega Exemplo [3.2.11] Mostre que b_n = 1 + 2 + 3 + ... + n é Ω(n^2). Notação grande Ômega Exemplo [3.2.11] Mostre que b_n = 1 + 2 + 3 + ... + n é Ω(n^2). Prova Suponha n seja par. Somando apenas os termos maior que n/2 temos 1 + 2 + ... n/2 + (n + 1)/2 + ... + n \_________________/ > n/2 + n/2 + ... + n/2 n/2 termos = n/2 ⋅ n/2 = n^2/4 Notação grande Teta Definição Sejam f , g funções de N ou R para R+. Então f (x) ∈ Θ(g(x)) se houver constantes c, C e x0 tal que ∀x > x0 : c · g(x) ≤ f (x) ≤ C · g(x) Então, f e g têm a mesma ordem. Ou seja, f (x) ∈ Θ(g(x)) se f (x) ∈ O(g(x)) e g(x) ∈ O(f (x)) Notação grande Teta Definição Sejam f , g funções de N ou R para R+. Então f (x) ∈ Θ(g(x)) se houver constantes c, C e x0 tal que ∀x > x0 : c · g(x) ≤ f (x) ≤ C · g(x) Então, f e g têm a mesma ordem. Ou seja, f (x) ∈ Θ(g(x)) se f (x) ∈ O(g(x)) e g(x) ∈ O(f (x)) Notação grande Teta ▶ AVISO: Muitas vezes um autor usa a notação O(f (x)) no sentido de Θ(f (x)). Exemplo: ‘O algoritmo XYZ é O(n log n)’ quer dizer que o tempo de execuão de XYZ, t(n), é da ordem n log n (onde n é o tamanho da entrada em bits). Ele pode até escrever ‘t(n) = O(n log n)’. ▶ Ou seja, O(f (x)) pode indicar ▶ (1) uma cota superior, ou ▶ (2) ser a ordem exata. Sempre ler com cautela. Notação grande Teta ▶ AVISO: Muitas vezes um autor usa a notação O(f (x)) no sentido de Θ(f (x)). Exemplo: ‘O algoritmo XYZ é O(n log n)’ quer dizer que o tempo de execuão de XYZ, t(n), é da ordem n log n (onde n é o tamanho da entrada em bits). Ele pode até escrever ‘t(n) = O(n log n)’. ▶ Ou seja, O(f (x)) pode indicar ▶ (1) uma cota superior, ou ▶ (2) ser a ordem exata. Sempre ler com cautela. Notação Grande O – resumo Theorem (a) Suppose there exists constants n0, C such that for all positive integer n > n0 : f (n) g(n) ≤ C < ∞ Then [f ] ⪯ [g]. (b) Suppose there exists constants n0, c such that for all positive integer n > n0 : 0 < c ≤ f (n) g(n) Then [f ] ⪰ [g]. Notação Grande O – resumo (c) Suppose there exists constants n0, c, C such that for all positive integer n > n0 : 0 < c ≤ f (n) g(n) ≤ C ≤ ∞ Then [f ] = [g]. (d) If no constant C as described in (a) and no constant c as described in (b) exist, then f and g are not comparable, i.e. neither [f ] ⪯ [g] nor [g] ⪯ [f ]. However, such examples are very difficult to create; f and g must alternate an infinite number of times and limn→∞ f (n) g(n) must not exist. In practice such cases never occur. Notação Grande O - Ômega - Theta – resumo [f ] ⪯ [g] f é da ordem de g ∃C ∀n : f (n) g(n) ≤ C < ∞ f ∈ O(g) [f ] ⪰ [g] f é cota inferior de g ∃c ∀n : 0 < c ≤ f (n) g(n) f ∈ Ω(g) [f ] = [g] f , g são da mesma ordem ∃c, C ∀n : c ≤ f (n) g(n) ≤ C f ∈ Θ(g), g ∈ Θ(f ) [f ] ̸⪯ [g]∧ f , g são incomparaveis ¬[∃c, C ∀n : ...] [g] ̸⪯ [f ] Problema computacional – exemplos RAIZ QUADRADA ENTRADA: x ∈ R SAÍDA: a raíz √x FATORAR ENTRADA: n ∈ N SAÍDA: primos p1, p2, . . . , pk tal que n = p1 · · · pk CAIXEIRO VIAJANTE ENTRADA: T, a tabela com distâncias; M SAÍDA: cidades c1, c2, . . . , ck tal que a rota que passa por essas cidades tem distância ≤ M Problema computacional – exemplos RAIZ QUADRADA ENTRADA: x ∈ R SAÍDA: a raíz √x FATORAR ENTRADA: n ∈ N SAÍDA: primos p1, p2, . . . , pk tal que n = p1 · · · pk CAIXEIRO VIAJANTE ENTRADA: T, a tabela com distâncias; M SAÍDA: cidades c1, c2, . . . , ck tal que a rota que passa por essas cidades tem distância ≤ M Problema computacional – exemplos RAIZ QUADRADA ENTRADA: x ∈ R SAÍDA: a raíz √x FATORAR ENTRADA: n ∈ N SAÍDA: primos p1, p2, . . . , pk tal que n = p1 · · · pk CAIXEIRO VIAJANTE ENTRADA: T, a tabela com distâncias; M SAÍDA: cidades c1, c2, . . . , ck tal que a rota que passa por essas cidades tem distância ≤ M Algoritmo Definição Um algoritmo é um conjunto finito de instruções necessárias para resolver um problema computacional. Distingua bem entre 1. Problema computacional 2. Algoritmo 3. Programa Algoritmo Definição Um algoritmo é um conjunto finito de instruções necessárias para resolver um problema computacional. Distingua bem entre 1. Problema computacional 2. Algoritmo 3. Programa Algoritmo Definição Um algoritmo é um conjunto finito de instruções necessárias para resolver um problema computacional. Distingua bem entre 1. Problema computacional 2. Algoritmo 3. Programa Algoritmo Definição Um algoritmo é um conjunto finito de instruções necessárias para resolver um problema computacional. Distingua bem entre 1. Problema computacional 2. Algoritmo 3. Programa Complexidade dos algoritmos ▶ Uma operação básica é uma operação que pode ser executada num tempo unitária. ▶ Essa definição se justifica, porque quase sempre o tempo de execução das operações pode ser limitada acima por um constante, dependendo somente da implementação (processador, linguagem de programação etc). ▶ A complexidade de algoritmos se faz contando o número de operação básicas, e não o tempo-de-relógio em si. ▶ (Quem faz pesquisa em hardware (engenheiros etc) se importam com tempo-de relógio sim) Complexidade dos algoritmos ▶ Uma operação básica é uma operação que pode ser executada num tempo unitária. ▶ Essa definição se justifica, porque quase sempre o tempo de execução das operações pode ser limitada acima por um constante, dependendo somente da implementação (processador, linguagem de programação etc). ▶ A complexidade de algoritmos se faz contando o número de operação básicas, e não o tempo-de-relógio em si. ▶ (Quem faz pesquisa em hardware (engenheiros etc) se importam com tempo-de relógio sim) Complexidade dos algoritmos ▶ Uma operação básica é uma operação que pode ser executada num tempo unitária. ▶ Essa definição se justifica, porque quase sempre o tempo de execução das operações pode ser limitada acima por um constante, dependendo somente da implementação (processador, linguagem de programação etc). ▶ A complexidade de algoritmos se faz contando o número de operação básicas, e não o tempo-de-relógio em si. ▶ (Quem faz pesquisa em hardware (engenheiros etc) se importam com tempo-de relógio sim) Complexidade dos algoritmos ▶ Uma operação básica é uma operação que pode ser executada num tempo unitária. ▶ Essa definição se justifica, porque quase sempre o tempo de execução das operações pode ser limitada acima por um constante, dependendo somente da implementação (processador, linguagem de programação etc). ▶ A complexidade de algoritmos se faz contando o número de operação básicas, e não o tempo-de-relógio em si. ▶ (Quem faz pesquisa em hardware (engenheiros etc) se importam com tempo-de relógio sim) Complexidade dos algoritmos ▶ Para avaliar a complexidade de um algoritmo, em muitos casos é suficiente contar o número de iterações, contando quantas vezes um determinado comando (for, if, while) é executado. ▶ Distinguir ▶ Complexidado pior caso (worst case) ▶ Complexidade de caso medio Hierarquia de complexidade (3.3) Complexidade Terminologia Θ(1) Complexidade constante Θ(log n) Complexidade logaritmico Θ(n) Complexidade linear Θ(n log n) Complexidade n log n Θ(n2) Complexidade quadrática Θ(n3) Complexidade cúbica Θ(nk) Complexidade polinomial Θ(an) para a > 1 Complexidade exponencial Θ(n!) Complexidade fatorial Θ(nn) Complexidade nn Porque complexidade exponencial é desastroso Porque complexidade exponencial é desastroso Temos 3 algoritimos: ▶ A tem complexidade linear ▶ B tem complexidade quadrática ▶ C tem complexidade exponencial Vamos calcular qual é o impacto de se ter um processador 100 (resp. 1000000) vezes mas rápido no tamanho das instâncias que o algoritmo consegue calcular num prazo de uma hora. Porque complexidade exponencial é desastroso – Algoritmo A ▶ Um supercomputador é capaz de fazer X operações por hora. ▶ O problema computacional A tem complexidade linear, e numa hora é capaz de resolver uma instância de tamanho nA. ▶ Portanto um computador 100 vezes mais rápido, pode resolver uma instância de tamanho n′ A = 100nA numa hora. ▶ E um computador 1000000 vezes mais rápido, pode resolver uma instância de tamanho n′′ A = 1000000nA numa hora. Porque complexidade exponencial é desastroso – Algoritmo A ▶ Um supercomputador é capaz de fazer X operações por hora. ▶ O problema computacional A tem complexidade linear, e numa hora é capaz de resolver uma instância de tamanho nA. ▶ Portanto um computador 100 vezes mais rápido, pode resolver uma instância de tamanho n′ A = 100nA numa hora. ▶ E um computador 1000000 vezes mais rápido, pode resolver uma instância de tamanho n′′ A = 1000000nA numa hora. Porque complexidade exponencial é desastroso – Algoritmo A ▶ Um supercomputador é capaz de fazer X operações por hora. ▶ O problema computacional A tem complexidade linear, e numa hora é capaz de resolver uma instância de tamanho nA. ▶ Portanto um computador 100 vezes mais rápido, pode resolver uma instância de tamanho n′ A = 100nA numa hora. ▶ E um computador 1000000 vezes mais rápido, pode resolver uma instância de tamanho n′′ A = 1000000nA numa hora. Porque complexidade exponencial é desastroso — Algoritmo B ► Um supercomputador é capaz de fazer X operações por hora. ► Problema computacional B tem complexidade quadrática, e numa hora é capaz de resolver uma instância de tamanho n_B. Ou seja, X = n_B^2. Qual é o tamanho das instâncias que podemos calcular com um computador 100 vezes mais rápido? E 1000000 vezes mais rápido? Porque complexidade exponencial é desastroso — Algoritmo B ► Um supercomputador é capaz de fazer X operações por hora. ► Problema computacional B tem complexidade quadrática, e numa hora é capaz de resolver uma instância de tamanho n_B. Ou seja, X = n_B^2. Qual é o tamanho das instâncias que podemos calcular com um computador 100 vezes mais rápido? E 1000000 vezes mais rápido? ► Suponha que 100X operações correspondam a uma instância de tamanho n'_B. Então (n'_B)^2 = 100X = 100(n_B)^2. Portanto n'_B = \sqrt{100(n_B)^2} = 10n_B Porque complexidade exponencial é desastrosa – Algoritmo B ► Um supercomputador é capaz de fazer X operações por hora. ► Problema computacional B tem complexidade quadrática, e numa hora é capaz de resolver uma instância de tamanho n_B. Ou seja, X = n_B^2. Qual é o tamanho das instâncias que podemos calcular com um computador 100 vezes mais rápido? E 1000000 vezes mais rápido? ► Suponha que 100X operações correspondam a uma instância de tamanho n'_B. Então (n'_B)^2 = 100X = 100(n_B)^2. Portanto n'_B = \sqrt{100(n_B)^2} = 10n_B ► Suponha que 1000000X operações correspondam a uma instância de tamanho n''_B. Então (n''_B)^2 = 1000000X = 1000000(n_B)^2. Portanto n''_B = \sqrt{1000000(n_B)^2} = 1000n_B Porque complexidade exponencial é desastroso – Algoritmo C ▶ Um supercomputador é capaz de fazer X operações por hora. ▶ Problema computacional C tem complexidade exponencial,e numa hora é capaz de resolver uma instância de tamanho nC. Ou seja, X = 2nC . Qual é o tamanho das instâncias que podemos calcular com um computador 100 vezes mais rápido? ▶ Suponha que 100X operações correspondam a uma instância de tamanho n′ C, então 2n′ C = 100X = 100 · 2nc . Portanto n′ C = lg 100 + nC = nC + 6.64 ▶ Suponha que 1000000X operações correspondam uma instância de tamanho n′′ C, então 2n′′ C = 1000000 · 2nc . Portanto n′′ C = lg 1000000X = lg 1000000 + nC = nC + 19.93 Porque complexidade exponencial é desastroso – Algoritmo C ▶ Um supercomputador é capaz de fazer X operações por hora. ▶ Problema computacional C tem complexidade exponencial,e numa hora é capaz de resolver uma instância de tamanho nC. Ou seja, X = 2nC . Qual é o tamanho das instâncias que podemos calcular com um computador 100 vezes mais rápido? ▶ Suponha que 100X operações correspondam a uma instância de tamanho n′ C, então 2n′ C = 100X = 100 · 2nc . Portanto n′ C = lg 100 + nC = nC + 6.64 ▶ Suponha que 1000000X operações correspondam uma instância de tamanho n′′ C, então 2n′′ C = 1000000 · 2nc . Portanto n′′ C = lg 1000000X = lg 1000000 + nC = nC + 19.93 Porque complexidade exponencial é desastroso – Algoritmo C ▶ Um supercomputador é capaz de fazer X operações por hora. ▶ Problema computacional C tem complexidade exponencial,e numa hora é capaz de resolver uma instância de tamanho nC. Ou seja, X = 2nC . Qual é o tamanho das instâncias que podemos calcular com um computador 100 vezes mais rápido? ▶ Suponha que 100X operações correspondam a uma instância de tamanho n′ C, então 2n′ C = 100X = 100 · 2nc . Portanto n′ C = lg 100 + nC = nC + 6.64 ▶ Suponha que 1000000X operações correspondam uma instância de tamanho n′′ C, então 2n′′ C = 1000000 · 2nc . Portanto n′′ C = lg 1000000X = lg 1000000 + nC = nC + 19.93 Resumo Algoritmo A B C Complexidade n n2 2n Processador padrão nA nB nC Proc 100x mais rapido n′ a = 100nA n′ B = 10nB n′ C = nC + lg(10) Proc 1000000x mais rapido n′′ a = 1000000nA n′′ B = 1000nB n′′ C = nC + lg(1000000) Proc k vezes mais rapido factor k factor √ k incremento lg(k) Conclusão Um aumento de velocidade significativo tem quase nenhum impacto num problema exponencial Problema computacionais não-computáveis Existem 3 classes de problemas computacionais: 1. Os problemas tratáveis : tempo de execução (memória) viável (polinomial) 2. Os problemas intratáveis: tempo de execução/memória inviável (exponencial) 3. Os problemas impossíveis: não existe algoritmo (indecidível) (Final 3.1) Problema computacionais não-computáveis Existem 3 classes de problemas computacionais: 1. Os problemas tratáveis : tempo de execução (memória) viável (polinomial) 2. Os problemas intratáveis: tempo de execução/memória inviável (exponencial) 3. Os problemas impossíveis: não existe algoritmo (indecidível) (Final 3.1) Problema computacionais não-computáveis Existem 3 classes de problemas computacionais: 1. Os problemas tratáveis : tempo de execução (memória) viável (polinomial) 2. Os problemas intratáveis: tempo de execução/memória inviável (exponencial) 3. Os problemas impossíveis: não existe algoritmo (indecidível) (Final 3.1) Problema de parada PROBLEMA DE PARADA [Final 3.1] ENTRADA: P, x, onde P é um programa, e x uma entrada para P SAÍDA: ▶ se a execução de P com entrada x termina, retorne SIM ▶ se a execução de P com entrada x entra em loop infinito, retorne NÃO NÃO PODE EXISTIR UM ALGORITMO PARA DECIDIR O PROBLEMA DE PARADA Problema de parada PROBLEMA DE PARADA [Final 3.1] ENTRADA: P, x, onde P é um programa, e x uma entrada para P SAÍDA: ▶ se a execução de P com entrada x termina, retorne SIM ▶ se a execução de P com entrada x entra em loop infinito, retorne NÃO NÃO PODE EXISTIR UM ALGORITMO PARA DECIDIR O PROBLEMA DE PARADA Problema de parada PROBLEMA DE EQUIVALÊNCIA ENTRADA: P1, P2, onde P1 e P2 são programas SAÍDA: ▶ se P1 é equivalente a P2, retorne SIM ▶ senão, retorne NÃO onde P1 é equivalente a P2 se ∀x : saida(P1(x)) = saida(P2(x)) NÃO PODE EXISTIR UM ALGORITMO PARA DECIDIR O PROBLEMA DA EQUIVALÊNCIA Problema de parada PROBLEMA DE EQUIVALÊNCIA ENTRADA: P1, P2, onde P1 e P2 são programas SAÍDA: ▶ se P1 é equivalente a P2, retorne SIM ▶ senão, retorne NÃO onde P1 é equivalente a P2 se ∀x : saida(P1(x)) = saida(P2(x)) NÃO PODE EXISTIR UM ALGORITMO PARA DECIDIR O PROBLEMA DA EQUIVALÊNCIA Problema de correspondência de Post \[\begin{array}{|c|c|c|c|c|c|}\hline & 1 & 2 & 3 & 4 & 5 \\\hline X & abb & a & bab & baba & aba \\\hline Y & bbab & aa & ab & aa & a \\\hline \end{array}\] (a) Admits a correspondence: 2, 1, 1, 4, 1, 5 \[\begin{array}{|c|c|c|c|c|c|}\hline & 1 & 2 & 3 & 4 & 5 \\\hline X & bb & a & bab & baba & aba \\\hline Y & bab & aa & ab & aa & a \\\hline \end{array}\] (b) Admits no correspondence