7. Análise de Algoritmos Show
Aula – Complexidade de Algoritmos – PPT Contents
Introdução
7.1. Idéias básicas
inteiro potência (x, n) inteiro x, y, n, j; início i <- n; y <- 1; enquanto (i > 0) faça y <- y * x; i <- i - 1; fim enquanto retorne y; fim inteiro potência_recursiva (x, n) início se (n = 1) então retorne x; y <- potência_recursiva ( x, (n div 2) ); se (ímpar(n)) então retorne x*y*y; senão retorne y*y; fim se fim
7.2. Problema básico na Análise de Algoritmos:
Modelo de computação: As operações são todas executadas seqüencialmente. A execução de toda e qualquer operação toma uma unidade de tempo. A memória do computador é infinita. Assim nos sobram duas grandezas:
7.3. Complexidade de Tempo
7.3.1. Primeiro caso: BubblesortBubblesort é o mais primitivo dos métodos de ordenação de um vetor. A idéia é percorrer um vetor de n posições n vezes, a cada vez comparando dois elementos e trocando-os caso o primeiro seja maior que o segundo: ordenaBolha /* Bubblesort */ inteiro i,j,x,a[n]; início para i de 1 até n faça para j de 2 até n faça se (a[j-1]>a[j]) então x <- a[j-1]; a[j-1] <- a[j]; a[j] <- x; fim se fim para fim para fim A comparação (a[j-1]>a[j]) vai ser executada n*(n-1) vezes. No caso de um vetor na ordem inversa, as operações da atribuição triangular poderão ser executadas até 3*n*(n-1) vezes, já uma troca de elementos não significa que um dos elementos trocados tenha encontrado o seu lugar definitivo. 7.3.2. Segundo caso: StraightSelectionO método da seleção direta é uma forma intuitiva de ordenarmos um vetor: escolhemos o menor elemento do vetor e o trocamos de posição com o primeiro elemento. Depois começamos do segundo e escolhemos novamente o menor dentre os restantes e o trocamos de posição com o segundo e assim por diante. seleçãoDireta inteiro i,j,k,x,a[n]; início para i de 1 até n-1 faça k <- i; x <- a[i]; para j de i +1 até n faça se (a[j] < x) então k <- j; x <- a[k]; fim se fim para a[k] <- a[i]; a[i] <- x; fim para fim Neste algoritmo o número de vezes que a comparação (a[j] < x) é executada é expresso por (n-1)+(n-2)+…+2+1 = (n/2)*(n-1). O número de trocas a[k] <- a[i]; a[i] <- x é realizado no pior caso, onde o vetor está ordenado em ordem inversa, somente n-1 vezes, num total de 2*(n-1). 7.3.3. InterpretaçãoComo já foi dito, a única forma de se poder comparar dois algoritmos é descrevendo o seu comportamento temporal em função do tamanho do conjunto de dados de entrada, Talgoritmo = f(n), onde n é o tamanho dos dados. Assim, se tomarmos as operações de troca de valores como critério-base, podemos dizer que: Tbubblesort = 3*n*(n-1) sempre e Tstraightselection = 2*(n-1) para o pior caso.
Se eu uso esses algoritmos para um conjunto de 30 dados, o segundo com Tb=3000 é pior do que o primeiro com Ta=900. Se eu os uso para um conjunto de 30.000 dados, porém, terei Ta=900.000.000 e Tb=3.000.000.
Podemos ver isto expresso no gráfico abaixo: 7.4. Interpretação da Complexidade de TempoO gráfico acima nos mostra qual é o aspecto essecial que deve ser expresso pelo cálculo de complexidade: Qual é o comportamento assintótico predominante de um algoritmo em função do tamanho do conjunto de dados a ser processado?
7.4.2. Diferentes Tempos de ExecuçãoProblema da Subseqüência de Soma Máxima: Dada uma
seqüência de números a1, a2, … , an, positivos ou negativos, encontre uma subseqüência aj,…,ak dentro desta seqüência cuja soma seja máxima. A soma de uma seqüência contendo só números negativos é por definição Exemplo: Para a seqüência -2, 11, -4, 13, -5, -2, a resposta é 20 Este problema oferece um bom exemplo para o estudo de como diferentes algoritmos que resolvem o mesmo problema possuem diferentes comportamentos, pois para ele existem muitas soluções diferentes. Abaixo, um exemplo dos tempos de execução dos diferentes algoritmos da subseqüência de maior soma: 7.5. Cálculo da Complexidade de TempoUm exemplo intuitivo: Cálculo de inteiro somaCubos (inteiro n) inteiro i, somaParcial; início 1 somaParcial <- 0; 2 para i de 1 até n faça 3 somaParcial <- somaParcial + i * i * i; 4 fim para 5 retorne somaParcial; fim Análise:
7.5.1. Regras para o cálculo
O tempo de execução de um laço é, no máximo, a soma dos tempos de execução de todas as instruções dentro do laço (incluindo todos os testes) multiplicado pelo númerode iterações.
O tempo total de execução de uma instrução dentro de um grupo de laços aninhados é o tempo de execução da instrução multiplicado pelo produto dos tamanhos de todos os laços. Exemplo O(n2): para i de 1 até n para j de 1 até n k <- k + 1; fim para fim para
para i de 1 até a[i] <- 0; fim para para i de 1 até n para j de 1 até n a[i] <- a[j] + k + 1; fim para fim para
se cond então expresssão1 senão expressão2 fim se o tempo de execução de um comando IF/THEN/ELSE nunca é maior do que o tempo de execução do teste cond em si mais o tempo de execução da maior dentre as expressões expressão1 e expressão2. Ou seja: se expressão1 é O(n3) e expressão2 é O(n), então o teste é O(n3) + 1 = O(n3).
inteiro Fatorial (inteiro n) início se n <= 1 então retorne 1; senão retorne ( n * Fatorial ( n - 1 ) ); fim se fim O exemplo acima é realmente um exemplo pobre de recursão e pode ser “iterativisado” de forma extremamente simples com apenas um laço para-faça: inteiro FatorialIterativo (inteiro n) inteiro i, fatorial; início fatorial <- 1; para i de 2 até n faça fatorial <- fatorial * i; fim para retorne fatorial; fim A complexidade de FatorialIterativo pode então ser facilmente calculada e é evidente que é O(n). O caso dos números de Fibonacci abaixo não é tão simples e requer a resolução de uma relação de recorrência: inteiro Fibonacci (inteiro n) início se n <= 1 então retorne 1; senão retorne ( Fibonacci(n-1) + Fibonacci(n-2)); fim se fim Observando o algoritmo, vemos que para n>= 2 temos um tempo de execução T(n) = T(n-1)+T(n-2)+2. A resolução desta relação nos mostra que Fibonacci é O((2)n) 7.5.2. Logaritmos e Outros no Tempo de Execução
7.6. Checando a sua análiseUma vez que a análise de complexidade tenha sido executada, é interessante verificar-se se a resposta está correta e é tão boa quanto possível. Uma forma de se fazer isto é o procedimento pouco matemático de se codificar o trecho de algoritmo cuja complexidade se tentou descrever e verificar se o tempo de execução coincide com o tempo previsto pela análise:
Distinguir programas n log n de programas lineares só em evidência de tempo de execução pode também ser muito difícil. Uma boa praxe é, caso o programa não seja exponencial (o que você vai descobrir muito rápido), fazer alguns experimentos com conjuntos maiores de dados de entrada 7.7. ExercíciosO objetivo desta lista de exercícios é permitir a você revisar o conteúdo desta parte de Análise de Algoritmos e verificar os seus conhecimentos. O teste a ser realizado conterá exercícos semelhantes a estes e será do mesmo nível de dificuldade. (1) Um dos pontos importantes a serem considerados ao se tomar a decisão de utilizar um algoritmo para a solução de um problema, é a sua correção. Um algoritmo incorreto não produzirá os resultados esperados e não pode ser utilizado. Outro ponto importante a ser considerado, quando temos mais de uma opção de algoritmos tradicionais para resolver um
problema ou quando podemos projetar um algoritmo para um problema de diversas maneiras, é a questão de sua eficiência. (2) Uma das possíveis formas de se descrever a complexidade de um algoritmos é a chamada Notação-Big-Oh, que é definida da seguinte forma: T(n) = O(f(n)) se existem constantes c e n0 tais que T(n) <= c.f(n) quando n > n0. Explique o que você entendeu por esta definição. (3) Vimos que existem duas formas de se implementar listas: como conjuntos de dados fisicamente adjacentes, atraves da utilização de vetores e como conjuntos de dados apenas logicamente interligados, mas sem adjacência física, através da utilização de listas encadeadas. As listas encadeadas possuem vantagens de economia de memória bastante óbvias, uma vez que é somente utilizada a memória realmente necessária para armazenar um determinado conjunto de dados. Do ponto de vista de complexidade, discutimos em sala de aula também vantagens e desvantagens dos dois modelos. Explique qual dos dois modelos é melhor em termos de complexidade de tempo de acesso e explique por que isto ocorre, exemplificando atrav’es de um desenho. Diga qual é a complexidade média de tempo de acesso a um dado em uma lista com vetor de n dados e uma lista encadeada com n dados. Justifique. (4) Para o cálculo da complexidade de algoritmos não recursivos, existe um conjunto de regras bastante simples de serem seguidas. Cite e descreva estas regras. (5) Algoritmos recursivos são bem mais difíceis de se analisar com respeito ao seu comportamento assintótico (complexidade de tempo). Quando nós tentamos descrever a complexidade de tempo de um algoritmo recursivo utilizando as regras
acima, acabamos obtendo uma fórmula também recursiva, que nós chamamos de relação de recorrência. Para resolver esta fórmula existe um conjunto de regras matemáticas que você ainda não viu. Mas você pode, para alguns problemas, “estimar” a complexidade de execução de um algoritmo recursivo com base em algumas de suas características sem a necessidade de resolver um problema matemático mais complexo. (6) O que diferencia os problemas tratáveis dos não-tratáveis ? Explique o termo NP (isto não foi visto em aula. Pesquise na literatura). (7) Calcule, passo a passo, a complexidade do algoritmo abaixo. Algoritmo Prova Variáveis inteiro i,j,k,n,x(n) Início para I de 1 até n faça: leia x(i); fim para para i de 1 até n - 2 faça: para j de 1 até 2*n faça: se i for ímpar então para k de 1 até n2 faça: x(k) <- x(i) * x(j); fim para senão para k de 1 até n faça x(k) <- j; fim para x(j) <- 1; x(i) <- j; fim se fim para fim para Fim Como calcular complexidade de tempo?Complexidade de tempo é comumente estimada pela contagem do número de operações elementares realizadas pelo algoritmo, onde a operação elementar toma a quantia fixa de tempo para realizar. A quantidade de tempo tomada e o número de operações elementares realizadas pelo algoritmo diferem no máximo de um fator constante.
Como calcular complexidade de tempo e espaço?Por exemplo, a complexidade de tempo para a ordenação por seleção pode ser definida pela função f(n) = n²/2-n/2, como mostramos na seção anterior. Se nossa função g(n) for representada por n², encontramos uma constante c = 1 e um N₀ = 0. Enquanto N > N₀, N² será sempre maior que N²/2-N/2.
O que é análise de complexidade?A complexidade é usada para medir a velocidade de um algoritmo. Sendo o algoritmo um agrupamento de etapas para se executar uma tarefa, o tempo que leva para um algoritmo ser executado é baseado no número de passos. Digamos que um algoritmo percorre um array de dez posições somando o índice das posições a 200.
Como medir o tempo de complexidade de um algoritmo?Para calcular a complexidade de um algoritmo a ∈ a, deve-se determinar as operações fundamentais e definir a função tamanho do problema. Se houver mais de uma operação fundamental é necessário que se defina o peso de cada operação. Considere E o conjunto de todas as seqüências de execução das operações fundamentais.
|