complexidade-1x2

8/17/2019 complexidade-1x2

1/9

7. Introdução à Complexidade de Algoritmos

Fernando Silva

DCC-FCUP

Estruturas de Dados

Fernando Silva (DCC-FCUP) 7. Introdução à Complexidade de Algoritmos Estruturas de Dados 1 / 1

Análise de Algoritmos

No desenvolvimento de algoritmos é importante ter a noção da eficiênciade um algoritmo, i.e. da eficiência que pode ter uma implementação doalgoritmo.

Eficiência normalmente mede-se em tempo de execução ou espaço

(memória) necessário à execução do algoritmo (ou programaassociado).

Tempo de Execução de um algoritmo varia com o input enormalmente aumenta com o tamanho do input. caso médio é difícil de determinar. normalmente, olha-se para o pior caso possível de tempo de execução:

mais simples de analizar

crucial nas aplicações mais exigentes, jogos, etc.



2/9

Como aferir a eficiência

Como aferir a eficiência, por exemplo, o tempo de execução?

Análise empírica – executando o programa com inputs de tamanho e

composição variados, mas nem sempre é simples concretizar o algoritmo, ou os resultados podem não ser conclusivos, comparação de algoritmos obriga a usar igual software e hardware.

Análise teórica usa uma descrição de mais alto nível do algoritmo em vez da

implementação, caracteriza o tempo de execução como uma função do tamanho do

input, n, tem em conta todos os possíveis inputs, permite avaliar eficiência de forma independente do ambiente de

hardware/software.


Exemplo de análise de complexidade - findMax()

Como calcular o tempo de execução do algoritmo seguinte:

Pressupostos (RAM -Random Access Memory):

memória ilimitada e endereços contêm um no arbitrário ou caracteres,aceder ao conteúdo de um endereço custa uma unidade de tempo.

max= A[0]; → 1 leitura de A[0] + 1 atribuição a max.Fernando Silva (DCC-FCUP) 7. Introdução à Complexidade de Algoritmos Estruturas de Dados 4 / 1


3/9

Determinar complexidade do findMax()

Casos possíveis:

caso mais favorável (A[0] é o maior elemento):t (n) = 2 + 1 + n + 4(n − 1) + 1 = 5n operações primitivaspior caso:t (n) = 2 + 1 + n + 6(n − 1) + 1 = 7n − 2caso médio? difícil de calcular, depende da distribuição do input; usarteoria de probabilidades.

Normalmente, olharemos para o pior caso, pois dá-nos um limite superiordo tempo de execução.

Cálculo do tempo de execução:

seja a o tempo observado para a operação primitiva mais rápida

seja b o tempo observado para a operação primitiva mais lenta

então, o pior tempo de execução T (n) seráa (7n − 2) ≤ T (n) ≤ b (7n − 2) ⇒ T (n) limitado por 2 funções lineares


Taxa de crescimento do tempo de execução

Saliente-se que:

o tempo de execução, T (n), pode ser afectado pela alteração doambiente hardware/software, mas

tal não acontece se considerarmos a taxa de crescimento de T (n)

A taxa de crescimento de T (n) correspondeao crescimento de T (n) quando se aumenta o valor de n.

O exemplo findMax()

mostrava T (n) limitado por 2 funções lineares em n, significando queo tempo de execução varia na mesma proporção que n.

Logo, diz-se que o crescimento de T (n) é linear.



4/9

Taxas de crescimento (1)

logarítmica ≈ log2 nlinear ≈ nquadrática

≈n2

cúbica ≈ n3polinomial ≈ nk exponencial ≈ a n(a > 1)

Crescimento de algumas funções:n log2 n

√ n n n log2 n n

2 n3 2n

2 1 1.4 2 2 4 8 48 3 2.8 8 24 64 512 256

16 4 4.0 16 64 256 4096 65536. . . . . . . . . . . . . . . . . . . . . . . .

1024 10 32 1024 10240 > 106 > 109 > 10308


Taxas de crescimento (2)

Se assumirmos que cada operação pode ser executada em 1µs (micro-sec),qual será o maior problema (função de n) para um programa que executeem 1 seg., 1 min., 1 hora?

Tamanho máximo problema (n)

T (n) 1 seg. 1 min. 1 hora 400n 2500 150,000 9,000,00020nlog n 4096 166,666 7,826,087

2n2 707 5,477 42,426n4 31 88 2442n 19 25 31

No caso de crescimento exponencial, apenas conseguimos tratar problemaspara dimensões muito pequenas de n.



5/9

A definição “big-Oh” O()Definição de ordem de complexidade assimptótica:

Sejam f (n) e g (n) funções de N0 −→ R.f (n) é

O(g (n)) (ou seja, f (n) é da ordem de g (n))

se ∃c > 0, ∃n0 ≥ 1 : f (n) ≤ cg (n), ∀n ≥ n0Interpretação gráfica:

O(g (n)) corresponde ao limitesuperior da taxa de crescimento def (n).

dizer que f (n) é O(g (n)), significadizer que f (n) não cresce mais do queg (n).


Exemplos - O()2n + 10 é O(n)porque:

2n + 10

≤cn

⇒ (c

−2)n

≥10

⇒ n

≥

10

(c

− 2)para c = 3 e n0 = 10 verifica-se sempre que 2n + 10 ≤ cnoutras funções:

20n3 + 10n log n + 5 — O(n3)a k n

k + a k −1nk −1 + . . . + a 0 — O(nk )

3log n + log log n — O(log n)

2100

— O(1)5n

— O( 1n

)



6/9

Regras de simplificação

Algumas regras que olhando para expressões mais complexas,permitem-nos fazer simplificações:

Se d (n) ∼ O(f (n)), então ad (n) (com a > 0) ∼ O(f (n))Se d (n) ∼ O(f (n)) e e (n) ∼ O(g (n)), então d (n) + e (n) ∼ O(f (n) + g (n))

Se d (n) ∼ O(f (n)) e e (n) ∼ O(g (n)), então d (n)e (n) ∼ O(f (n)g (n))

Se d (n) ∼ O(f (n)) e f (n) ∼ O(g (n)), então d (n) ∼ O(g (n))


Complexidade do método da bolha (bubble-sort)

Façamos a análise de complexidade do método da bolha:

Efectivamente, o número de iterações total é a soma das iterações que ociclo j faz para cada valor de i, i.e.

n−1i =1 (n − i ) = (n − 1) + (n − 2) + . . . + 2 + 1 =

= n(n−1)2 = n2

2 − n2 ⇒ O(n2)Fernando Silva (DCC-FCUP) 7. Introdução à Complexidade de Algoritmos Estruturas de Dados 12 / 1


7/9

Complexidade de funções recursivas

Considere-se a função factorial fact() e seja T (n) o tempo de execuçãopara fact(n), então:

∴ T (n) =

c + T (n − 1), se n > 1d , se n ≤ 1

assumindo n ≥ 2: T (n − 1) = c + T (n − 2) ⇒ T (n) = 2c + T (n − 2)em geral: T (n) = ic + T (n − i ), n > i se i = n − 1, então T (n) = c (n − 1) + T (1) = c (n − 1) + d donde podemos concluir T (n) ≈ O(n), i.e. fact() tem complexidade n.


Complexidade da pesquisa binária (1)

Considere-se o método pesqbin() (pesquisa binária não recursiva):

Inicialmente o intervalo de valores é n (e = 0 e d = n − 1). Em cadapasso do ciclo, o intervalo reduz-se a metade.Portanto, a questão que se coloca é:

dado um inteiro n, quantas divisões inteiras por 2 são necessárias paraque chegue a 1? i.e. qual dos valores seguintes será o primeiro a ser


8/9

Complexidade da pesquisa binária (2)

É necessário resolver a equação: n/2k log2 n

Podemos então dizer que: com k = log2 n sabemos que ao fim de um máximo de k iterações,

encontramos o valor ou podemos concluir que o valor que procuramosnão existe.

Em resumo, dizemos que a função pesqbin() tem complexidadelogarítmica, O(log2 n), pois o número de iterações necessárias nãoexcede log

2 n, sendo n a dimensão dos dados.


Complexidade de árvores binárias de pesquisa (1)

Ver primeiro capítulo sobre árvores!

Se inserirmos n valores aleatórios numa árvore binária de pesquisa,sabemos que

o comprimento médio do caminho da raíz até uma folha é O(log2 n) –correspondente à profundidade da árvore.

verificar se x pertence à árvore é assim O(log2 n)Se a árvore for completa, então nenhum caminho da raíz até um dadonó pode ter mais do que 1 + log2 n nós. métodos insertBTNode(), contains() e removeBTNode() são

O(log2 n).É comum que ao inserirmos n valores aleatórios, a árvore não seja

completa, pode até ficar uma sequência ordenada. Neste caso cadainserção é O(n).



9/9

Complexidade de árvores binárias de pesquisa (2)

A questão a saber é se uma árvore binária em média estará próxima de uma árvore

completa ou de uma sequência? isto decide se o tempo médio é O(log2 n) ou O(n).

A demonstração deste resultado é complexa, envolvendoprobabilidades, basta-nos aqui saber que é possível mostrar porindução que a complexidade será O(log2 n).


complexidade-1x2

Documents