Complexidade de Algoritmos
Edson Prestes
Complexidade de Algoritmos
Exemplos
Seja
Mostre que
a)
b)
Onde Max(f,g)(n)=Max{f(n),g(n)},
Min(f,g)(n)=Min{f(n),g(n)}
e (f+g)(n)=f(n)+g(n)
Complexidade de Algoritmos
Exemplos
Complexidade de Algoritmos
Exemplos
Suponha que f e g são funções polinomiais :f(n)= Θ(nr) e g(n)= Θ(ns). O que se pode
afirmar sobre a função composta g(f(n)) ?
Complexidade de Algoritmos
Exemplos
Suponha que fi = O(gi ) para i=1,2. Mostre ou dê um contra-exemplo:
f1 + f2 = O(g1 + g2 )
Sabemos que
Complexidade de Algoritmos
Exemplos
Suponha que fi = O(gi ) para i=1,2. Mostre ou dê um contra-exemplo:
f1 f2 = O(g1 g2 )
Sabemos que
Complexidade de Algoritmos
Exemplos
Complexidade de Algoritmos
Exemplos
A complexidade no pior caso é linear e igual a n, ou seja, é O(n)
A complexidade média é linear e igual a (1+n)/2, ou seja, é O(n)