Mathematics">
Aula 07
Aula 07
Aula 07
• Algoritmos
• Correção e Análise
• Complexidade de um algoritmo
Algoritmos e Estruturas de Dados I
• Algoritmos
• processo sistemático (sequência de operações) para a resolução de um
problema;
• procedimento computacional bem definido que recebe um conjunto de
valores de entrada e produz outro conjunto de valores de saída.
• Correção e Análise
• Complexidade de um algoritmo
Algoritmos e Estruturas de Dados I
• Algoritmos
• processo sistemático (sequência de operações) para a resolução de um problema;
• procedimento computacional bem definido que recebe um conjunto de valores de entrada e produz
outro conjunto de valores de saída.
• Correção e Análise
• Correção: verifica a exatidão do método empregado;
• Análise: define parâmetros para avaliar a eficiência em termos de tempo de
execução e memória ocupada.
• Complexidade de um algoritmo
Algoritmos e Estruturas de Dados I
• Algoritmos
• processo sistemático (sequência de operações) para a resolução de um problema;
• procedimento computacional bem definido que recebe um conjunto de valores de entrada e produz
outro conjunto de valores de saída.
• Correção e Análise
• Correção: verifica a exatidão do método empregado;
• Análise: define parâmetros para avaliar a eficiência em termos de tempo de execução e memória
ocupada.
• Complexidade de um algoritmo
• É a quantidade de “trabalho” necessária para a sua execução, expressa
em função do volume de dados de entrada;
• “trabalho” -> memória e de tempo.
Algoritmos e Estruturas de Dados I
Estrutura de dados
• Para gerar uma saída, um algoritmo manipula dados a partir de um
conjunto de entrada;
• Dados dispostos e manipulados de forma homogênea = Tipo Abstrato
de Dados (TAD);
• Tipo Abstrato de Dados: formado por um conjunto de valores e
funções que podem ser aplicadas sobre esses valores;
• Estrutura de dados: é uma representação do Tipo Abstrato de Dados.
Algoritmos e Estruturas de Dados I
Estrutura de dados
• Meio para o armazenamento e organização de dados visando facilitar
o acesso e as modificações;
• As estruturas de dados diferem entre sim pela disposição e
manipulação de seus dados;
• A escolha da estrutura de dados adequada depende do
conhecimento dos algoritmos que a manipulam de forma eficiente.
Algoritmos e Estruturas de Dados I
Complexidade de Algoritmos: como avaliar?
• Espaço
Quantidade de recursos (memória) utilizados.
• Tempo
Tempo de execução do algoritmo ou o total de instruções executadas.
Algoritmos e Estruturas de Dados I
Complexidade de Algoritmos: como medir?
• Empiricamente
• Analiticamente
Algoritmos e Estruturas de Dados I
Complexidade de Algoritmos: como medir?
• Empiricamente
• Organização de um conjunto de entradas para o algoritmo que contenha
níveis diferentes de exigência de recursos;
• Execução e medição do consumo do recurso;
• Apresentação do resultado dos experimentos utilizando tabelas e gráficos;
• Análise de funções que possam descrever o gráfico.
Algoritmos e Estruturas de Dados I
Complexidade de Algoritmos: como medir?
• Analiticamente
Estudo do algoritmo;
A complexidade será medida em função do tamanho dos dados
de entrada do algoritmo;
Será obtida através de métodos analíticos, determinando uma
expressão matemática que traduza o comportamento de tempo do
algoritmo.
Algoritmos e Estruturas de Dados I
Complexidade de Algoritmos: como medir?
1 9 4 26 18 55 30
0 1 2 3 4 5 ... n
Algoritmos e Estruturas de Dados I
Exemplo linear
1 9 4 26 18 55 30
0 1 2 3 4 5 ... n
• Pior caso
Maior tempo de execução sobre todas as entradas de tamanho n.
• Melhor caso
Menor tempo de execução sobre todas as entradas de tamanho n.
• Caso médio
Média dos tempos de execução do algoritmo sobre todas as entradas de tamanho n.
Algoritmos e Estruturas de Dados I
Exemplo linear: Considere a busca por um determinado valor em um vetor.
A função de complexidade de tempo T é obtida a partir do número de
comparações efetuadas.
Assim:
• Melhor caso
Quando o valor a ser procurado encontra-se na primeira posição do vetor.
Algoritmos e Estruturas de Dados I
Exemplo linear: Considere a busca por um determinado valor em um vetor.
A função de complexidade de tempo T é obtida a partir do número de
comparações efetuadas.
Assim:
• Pior caso
Quando o valor a ser procurado encontra-se na última posição do vetor ou não está
armazenado no vetor.
Algoritmos e Estruturas de Dados I
Exemplo linear: Considere a busca por um determinado valor em um vetor.
A função de complexidade de tempo T é obtida a partir do número de
comparações efetuadas.
Assim:
• Caso médio
Leva em consideração uma distribuição de probabilidade, considerando pi como a
probabilidade de procurar o i-ésimo elemento do vetor e supondo que a probabilidade de
encontrar cada elemento seja 1/n..
Algoritmos e Estruturas de Dados I
Exemplo Quadrático
Dadas duas matrizes A =(aij) e B = (bij), ambas nxn, determinar a matriz
soma C = (cij).
funcao somaMatriz(m1: matriz, m2:matriz): matriz
inicio
mSoma: matriz
lin, col: inteiro
para lin:=0 até (n-1) faça
para col:=0 até (n-1) faça
mSoma[lin][col] = m1[lin][col] + m2[lin][col]
fim-para
fim-para
retorne -1
fim
Algoritmos e Estruturas de Dados I
Exemplo Quadrático
Dadas duas matrizes A =(aij) e B = (bij), ambas nxn, determinar a matriz
soma C = (cij).
funcao somaMatriz(m1: matriz, m2:matriz): matriz
inicio
mSoma: matriz
Tamanho da entrada: n2
lin, col: inteiro
Tempo = total de passos = total
para lin:=0 até (n-1) faça
de instruções executadas: n2
para col:=0 até (n-1) faça
mSoma[lin][col] = m1[lin][col] + m2[lin][col]
fim-para
fim-para
retorne -1
fim
Algoritmos e Estruturas de Dados I
Complexidade de Algoritmos
• Ordem de grandeza
• Operação dominante
• Pior caso
• Descarte de constantes aditivas e/ou multiplicativas
• Comportamento assintótico = entradas com tamanho suficientemente grande.
Algoritmos e Estruturas de Dados I
Complexidade de Algoritmos
𝑓(𝑛) ≤ 𝑐 × 𝑔(𝑛)
Algoritmos e Estruturas de Dados I
Complexidade de Algoritmos – notação assintótica
• Alguns tipos:
• Notação 𝑂
• Notação Ω
• Notação 𝜃
Algoritmos e Estruturas de Dados I
Complexidade de Algoritmos – notação assintótica
• Notação 𝑂
Exemplo: Considere dois algoritmos A1 e A2 que
realizam o upload de arquivos para um servidor.
Suponha que a complexidade de A1 seja O(n2) e
de A2 seja O(n). Considere o gráfico a seguir
representando o comportamento desses
algoritmos.
Algoritmos e Estruturas de Dados I
Complexidade de Algoritmos – notação assintótica
• Notação 𝑂
• Notação 𝑂
A notação O se refere ao limite superior de uma função. Ou seja, existe uma função à
qual o algoritmo analisado não terá um ponto acima da curva desta função.
Isto é, a função f(n) cresce no máximo como a função g(n).
Algoritmos e Estruturas de Dados I
Complexidade de Algoritmos – notação assintótica
• Notação 𝑂
Algoritmos e Estruturas de Dados I
Complexidade de Algoritmos
Exemplo:
Considere um algoritmo com três trechos cujos tempos de execução são O(n), O(n2)
e O(n log n). Qual a complexidade de pior caso na notação O do algoritmo?
Algoritmos e Estruturas de Dados I
Complexidade de Algoritmos
Exemplo:
Considere um algoritmo com três trechos cujos tempos de execução são
O(n), O(n2) e O(n log n). Qual a complexidade de pior caso na notação O do
algoritmo?
O tempo de execução do algoritmo será:
O(n) + O(n2) + O(n log n) = O(max(n, n2, n log n)) = O(n2)
Algoritmos e Estruturas de Dados I
Complexidade de Algoritmos – notação assintótica
• Notação 𝑂
Algoritmos e Estruturas de Dados I
Complexidade de Algoritmos – notação assintótica
• Notação 𝑂
Algoritmos e Estruturas de Dados I
Complexidade de Algoritmos – notação assintótica
• Notação 𝑂
Algoritmos e Estruturas de Dados I
Complexidade de Algoritmos – notação assintótica
• Notação 𝑂
Algoritmos e Estruturas de Dados I
Complexidade de Algoritmos – notação assintótica
• Notação 𝑂
Algoritmos e Estruturas de Dados I
Complexidade de Algoritmos – notação assintótica
• Notação 𝑂
Algoritmos e Estruturas de Dados I
Complexidade de Algoritmos – notação assintótica
• Notação 𝑂
Algoritmos e Estruturas de Dados I
Complexidade de Algoritmos – notação assintótica
• Notação 𝑂 – Operações e propriedades
Algoritmos e Estruturas de Dados I
Complexidade de Algoritmos
Exercício
FIM