Livro “Projeto de Algoritmos” – Nívio Ziviani Capítulo 1 ... · AlgoritmoseEstruturade Dados II Tipos de Problemas na Análise de Algoritmos Análise de um algoritmo particular

AlgoritmoseEstruturade Dados II

Me

did

ad

o T

em

po

de

Exe

cu

çã

od

e u

mP

rog

ram

a

Livr

o“P

roje

tode

Alg

oritm

os”

–N

ívio

Ziv

iani

Cap

ítulo

1 –

Seç

ão1.

3

http

://w

ww

2.dc

c.uf

mg.

br/li

vros

/alg

oritm

os/


Med

ida

do T

empo

de

Exe

cuçã

o de

um

Pro

gram

a

O

proj

eto

deal

gorit

mos

éfo

rtem

ente

inf

luen

ciad

o pe

lo e

stud

ode

seus

com

port

amen

tos.

D

epoi

s qu

eum

prob

lem

aé

anal

isad

oe

deci

sões

depr

ojet

o sã

o fin

aliz

adas

, éne

cess

ário

est

udar

asvá

rias

opçõ

esde

algo

ritm

osa

sere

m u

tiliz

ados

,co

nsid

eran

do o

s as

pect

osde

tem

po d

eex

ecuç

ãoe

espa

ço o

cupa

do.

M

uito

s de

sses

alg

oritm

os s

ão e

ncon

trad

os e

m á

reas

co

mo

pesq

uisa

ope

raci

onal

,otim

izaç

ão,t

eoria

dos

graf

os,e

stat

ístic

a,pr

obab

ilida

des,

entr

e ou

tras

.


Tip

osde

Pro

blem

as n

a A

nális

ede

Alg

oritm

os

A

ná

lis

ed

e u

ma

lgo

ritm

op

art

icu

lar.

Q

ualé

ocu

sto

deus

arum

dad

oal

gorit

mo

para

res

olve

rum

prob

lem

a es

pecí

fico?


Tip

osde

Pro

blem

as n

a A

nális

ede

Alg

oritm

os

A

ná

lis

ed

e u

ma

lgo

ritm

op

art

icu

lar.

Q

ualé

ocu

sto

deus

arum

dad

oal

gorit

mo

para

res

olve

rum

prob

lem

a es

pecí

fico?

C

arac

terí

stic

as q

ue d

evem

ser

inve

stig

adas

:

anál

ise

donú

mer

ode

veze

s qu

e ca

da p

arte

doal

gorit

mo

deve

ser

exec

utad

a,

estu

do d

a qu

antid

ade

dem

emór

ia n

eces

sária


Tip

osde

Pro

blem

as n

a A

nális

ede

Alg

oritm

os

A

ná

lis

ed

e u

ma

lgo

ritm

op

art

icu

lar.

Q

ualé

ocu

sto

deus

arum

dad

oal

gorit

mo

para

res

olve

rum

prob

lem

a es

pecí

fico?

C

arac

terí

stic

as q

ue d

evem

ser

inve

stig

adas

:

anál

ise

donú

mer

ode

veze

s qu

e ca

da p

arte

doal

gorit

mo

deve

ser

exec

utad

a,

estu

do d

a qu

antid

ade

dem

emór

ia n

eces

sária

.

A

ná

lis

ed

eu

ma

cla

ss

ed

ea

lgo

ritm

os

.

Qua

léo

algo

ritm

ode

men

or c

usto

pos

síve

l par

a re

solv

erum

prob

lem

apa

rtic

ular

?

Tod

aum

a fa

míli

ade

algo

ritm

osé

inve

stig

ada.

P

rocu

ra-s

eid

entif

icar

umqu

e se

jao

mel

hor

poss

ível

.

Col

oca-

seli

mit

es

par

aa

com

plex

idad

e co

mpu

taci

onal

dos

algo

ritm

os p

erte

ncen

tes

àcl

asse

.


Cus

tode

um

Alg

oritm

o

D

eter

min

ando

om

enor

cus

to p

ossí

vel p

ara

reso

lver

pro

blem

asde

uma

dada

clas

se,t

emos

am

edid

a da

difi

culd

ade

iner

ente

pa

ra r

esol

ver

opr

oble

ma.

Q

uand

oo

cust

ode

um

algo

ritm

oé

igua

l ao

men

or c

usto

po

ssív

el, o

algo

ritm

oé

óti

mo

par

aa

med

ida

decu

sto

cons

ider

ada.

P

odem

exi

stir

vário

s al

gorit

mos

par

a re

solv

ero

mes

mo

prob

lem

a.

S

e a

mes

ma

med

ida

decu

sto

éap

licad

aa

dife

rent

es a

lgor

itmos

,en

tão

épo

ssív

el c

ompa

rá-lo

se

esco

lher

om

ais

adeq

uado

.


Med

ida

doC

usto

pel

a E

xecu

ção

doP

rogr

ama

T

ais

med

idas

são

bas

tant

e in

adeq

uada

se

os r

esul

tado

s ja

mai

s de

vem

ser

gene

raliz

ados

:

os r

esul

tado

s sã

o de

pend

ente

sdo

com

pila

dor

que

pode

favo

rece

r al

gum

as

cons

truç

ões

em d

etrim

ento

deou

tras

;

os

res

ulta

dos

depe

ndem

do h

ard

ware

;

qu

ando

gra

ndes

qua

ntid

ades

dem

emór

ia s

ão u

tiliz

adas

, as

med

idas

de

tem

popo

dem

dep

ende

r de

ste

aspe

cto.

A

pesa

rdi

sso,

háar

gum

ento

sa

favo

rde

se

obte

rem

med

idas

rea

isde

te

mpo

.

Ex.

:qua

ndo

hává

rios

algo

ritm

os d

istin

tos

para

res

olve

rum

mes

mo

tipo

depr

oble

ma,

todo

sco

m u

mcu

sto

deex

ecuç

ão d

entr

ode

uma

mes

ma

orde

mde

gran

deza

.

A

ssim

,são

con

side

rado

s ta

nto

os c

usto

s re

ais

das

oper

açõe

s co

mo

os

cust

os n

ão a

pare

ntes

,tai

s co

mo

aloc

ação

dem

emór

ia,i

ndex

ação

,car

ga,

dent

re o

utro

s.


Med

ida

doC

usto

por

mei

o de

um

Mod

elo

Mat

emát

ico

U

saum

mod

elo

mat

emát

ico

base

ado

emum

com

puta

dor

idea

lizad

o.

D

eve

ser

espe

cific

ado

oco

njun

tode

oper

açõe

se

seus

cus

tos

deex

ecuç

ões.

É

mai

sus

uali

gnor

aro

cust

ode

algu

mas

das

oper

açõe

se

cons

ider

ar a

pena

sas

oper

açõe

s m

ais

sign

ifica

tivas

.

E

x.:a

lgor

itmos

deor

dena

ção.

Con

side

ram

oso

núm

ero

deco

mpa

raçõ

es e

ntre

os

elem

ento

sdo

conj

unto

a se

ror

dena

doe

igno

ram

osas

oper

açõe

s ar

itmét

icas

, de

atrib

uiçã

oe

man

ipul

açõe

sde

índi

ces,

caso

exi

stam

.


Fun

ção

deC

ompl

exid

ade

P

ara

med

iro

cust

ode

exec

ução

de u

mal

gorit

mo

éco

mum

def

inir

uma

funç

ãode

cust

o ou

fu

nç

ão

de

co

mp

lexid

ad

ef.

f(

n)

éa

med

ida

do te

mpo

nece

ssár

io p

ara

exec

utar

umal

gorit

mo

para

umpr

oble

ma

deta

man

hon.

F

unçã

ode

co

mp

lexid

ad

ed

e t

em

po

: f(n

)m

ede

o te

mpo

nece

ssár

io

para

exe

cuta

rum

algo

ritm

o em

umpr

oble

ma

deta

man

hon.

F

unçã

ode

co

mp

lexid

ad

ed

eesp

aço

: f(n

)m

ede

am

emór

ia n

eces

sária

pa

ra e

xecu

tar

umal

gorit

mo

emum

prob

lem

ade

tam

anho

n.

U

tiliz

arem

osfp

ara

deno

tar

uma

funç

ãode

com

plex

idad

ede

tem

poda

qui p

ara

afr

ente

.

A

com

plex

idad

ede

tem

pona

rea

lidad

e nã

o re

pres

enta

tem

podi

reta

men

te,m

aso

núm

ero

deve

zes

que

dete

rmin

ada

oper

ação

co

nsid

erad

a re

leva

nte

éex

ecut

ada.


Exe

mpl

o:m

aior

ele

men

to

C

onsi

dere

oal

gorit

mo

para

enc

ontr

aro

mai

or e

lem

ento

de u

mve

tor

dein

teiro

sA

[n];

n ≥

1.

S

eja

fum

a fu

nção

deco

mpl

exid

ade

tal q

uef(

n)

éo

núm

ero

deco

mpa

raçõ

es e

ntre

os

elem

ento

sde

A, s

e A

cont

iver

nel

emen

tos.

Q

ua

la

fun

çã

of(

n)?

#define n 10

int

Max(int

A[n])

int

i, Temp;

Temp = A[0];

for (i = 1; i < n; i++)

if (Temp < A[i])

Temp = A[i];

return Temp;


Exe

mpl

o:m

aior

ele

men

to

C

onsi

dere

oal

gorit

mo

para

enc

ontr

aro

mai

or e

lem

ento

de u

mve

tor

dein

teiro

sA

[n];

n ≥

1.

S

eja

fum

a fu

nção

deco

mpl

exid

ade

tal q

uef(

n)

éo

núm

ero

deco

mpa

raçõ

es e

ntre

os

elem

ento

sde

A, s

e A

cont

iver

nel

emen

tos.

L

og

o f

(n)

= n

-1

#define n 10

int

Max(int

A[n])

int

i, Temp;

Temp = A[0];

for (i = 1; i < n; i++)

if (Temp < A[i])

Temp = A[i];

return Temp;


Exe

mpl

o:m

aior

ele

men

to

T

eo

rem

a:Q

ualq

uer

algo

ritm

o pa

ra e

ncon

trar

om

aior

elem

ento

de u

mco

njun

toco

m n

elem

ento

s, n

≥1,

faz

pelo

men

osn

-1co

mpa

raçõ

es.


Exe

mpl

o:m

aior

ele

men

to

T

eo

rem

a:Q

ualq

uer

algo

ritm

o pa

ra e

ncon

trar

om

aior

elem

ento

de u

mco

njun

toco

m n

elem

ento

s, n

≥1,

faz

pelo

men

osn

-1co

mpa

raçõ

es.

P

rov

a:C

ada

um d

os n

-1

elem

ento

ste

m d

e s

erin

vest

igad

o po

r m

eio

deco

mpa

raçõ

es,q

ueé

men

ordo

que

algu

m o

utro

ele

men

to.


Exe

mpl

o:m

aior

ele

men

to

T

eo

rem

a:Q

ualq

uer

algo

ritm

o pa

ra e

ncon

trar

om

aior

elem

ento

de u

mco

njun

toco

m n

elem

ento

s, n

≥1,

faz

pelo

men

osn

-1co

mpa

raçõ

es.

P

rov

a:C

ada

um d

os n

-1

elem

ento

ste

m d

e s

erin

vest

igad

o po

r m

eio

deco

mpa

raçõ

es,q

ueé

men

ordo

que

algu

m o

utro

ele

men

to.

Lo

go, n

-1c

om

pa

raçõ

es

sã

o n

ec

es

sá

rias


Exe

mpl

o:m

aior

ele

men

to

T

eo

rem

a:Q

ualq

uer

algo

ritm

o pa

ra e

ncon

trar

om

aior

elem

ento

de u

mco

njun

toco

m n

elem

ento

s, n

≥1,

faz

pelo

men

osn

-1co

mpa

raçõ

es.

P

rov

a:C

ada

um d

os n

-1

elem

ento

ste

m d

e s

erin

vest

igad

o po

r m

eio

deco

mpa

raçõ

es,q

ueé

men

ordo

que

algu

m o

utro

ele

men

to.

Lo

go, n

-1co

mpa

raçõ

es s

ão n

eces

sária

s

Ote

orem

a ac

ima

nos

diz

que,

se

onú

mer

ode

com

para

ções

for

utili

zado

com

o m

edid

ade

cust

o,en

tão

afu

nção

Max

do

prog

ram

aan

terio

r é

óti

ma

.


Tam

anho

da

Ent

rada

de D

ados

A

med

ida

docu

sto

deex

ecuç

ãode

um

algo

ritm

o de

pend

e pr

inci

palm

ente

dota

man

ho d

a en

trad

ado

s da

dos.

É

com

um c

onsi

dera

ro

tem

po d

eex

ecuç

ãode

um

prog

ram

a co

mo

uma

funç

ãodo

tam

anho

da

entr

ada.

P

ara

algu

ns a

lgor

itmos

, ocu

sto

deex

ecuç

ãoé

uma

funç

ão d

a en

trad

apa

rtic

ular

dos

dad

os,n

ão a

pena

sdo

tam

anho

da

entr

ada.

N

oca

so d

a fu

nção

Max

do

prog

ram

ado

exem

plo,

ocu

sto

éun

iform

e so

bre

todo

s os

pro

blem

asde

tam

anho

n.

Jápa

raum

algo

ritm

ode

orde

naçã

o is

so n

ão o

corr

e:

seos

dado

s de

entr

ada

jáes

tiver

em q

uase

or

dena

dos,

entã

oo

algo

ritm

o po

de te

r qu

e tr

abal

har

men

os.


Melh

or

Caso

,P

ior

Caso

eC

aso

Méd

io

M

elh

or

cas

o:m

enor

tem

po d

eex

ecuç

ão s

obre

to

das

asen

trad

asde

tam

anho

n.

P

ior

ca

so

:mai

orte

mpo

de

exec

ução

sob

re to

das

asen

trad

asde

tam

anho

n.

S

e f é

uma

funç

ãode

com

plex

idad

e ba

sead

a na

aná

lise

depi

or c

aso,

ocu

sto

deap

licar

oal

gorit

mo

nunc

aé

mai

ordo

que

f(n)

.

C

aso

méd

io(o

u ca

so e

sper

ado)

:méd

iado

s te

mpo

s de

exec

ução

deto

das

asen

trad

asde

tam

anho

n.


An

álise

de

Melh

or

Caso

,P

ior

Caso

e

Caso

Méd

io

N

aan

ális

edo

caso

esp

erad

o,su

põe-

seum

a d

istr

ibu

ição

de

pro

bab

ilid

ad

es s

obre

oco

njun

tode

entr

adas

deta

man

hon

e o

cust

o m

édio

éob

tido

com

bas

ene

ssa

dist

ribui

ção.

A

anál

ise

doca

so m

édio

ége

ralm

ente

mui

to m

ais

difíc

ilde

obte

rdo

que

asan

ális

esdo

mel

hor

e do

pior

cas

o.

É

com

um s

upor

um

a di

strib

uiçã

ode

prob

abili

dade

s em

que

toda

s

asen

trad

as p

ossí

veis

são

igua

lmen

te p

rová

veis

.

N

apr

átic

a is

so n

em s

empr

eé

verd

ade.


Exe

mpl

o-

Reg

istr

osde

um

Arq

uivo

C

onsi

dere

opr

oble

ma

deac

essa

r os

re

gis

tro

sde

um

arqu

ivo.

C

ada

regi

stro

con

tém

um

a ch

ave ú

nica

que

éut

iliza

da p

ara

recu

pera

r re

gist

ros

doar

quiv

o.

O

prob

lem

a: d

ada

uma

chav

e qu

alqu

er,

loca

lize

ore

gist

ro q

ue c

onte

nha

esta

cha

ve.

O

algo

ritm

ode

pesq

uisa

mai

ssi

mpl

es é

oqu

e fa

za

pesq

uis

a s

eq

üen

cia

l.


Exe

mpl

o-

Reg

istr

osde

um

Arq

uivo

S

eja

fum

a fu

nção

deco

mpl

exid

ade

tal q

uef(

n)

éo

núm

ero

dere

gist

ros

cons

ulta

dos

noar

quiv

o(n

úmer

ode

veze

s qu

ea

chav

ede

cons

ulta

éco

mpa

rada

com

ach

ave

deca

da r

egis

tro)

.

m

elh

or

caso

:

p

ior

caso

:

caso

méd

io:


Exe

mpl

o-

Reg

istr

osde

um

Arq

uivo

S

eja

fum

a fu

nção

deco

mpl

exid

ade

tal q

uef(

n)

éo

núm

ero

dere

gist

ros

cons

ulta

dos

noar

quiv

o(n

úmer

ode

veze

s qu

ea

chav

ede

cons

ulta

éco

mpa

rada

com

ach

ave

deca

da r

egis

tro)

.

m

elh

or

caso

:

re

gist

ro p

rocu

rado

éo

prim

eiro

con

sulta

do

p

ior

caso

:

caso

méd

io:


Exe

mpl

o-

Reg

istr

osde

um

Arq

uivo

S

eja

fum

a fu

nção

deco

mpl

exid

ade

tal q

uef(

n)

éo

núm

ero

dere

gist

ros

cons

ulta

dos

noar

quiv

o(n

úmer

ode

veze

s qu

ea

chav

ede

cons

ulta

éco

mpa

rada

com

ach

ave

deca

da r

egis

tro)

.

m

elh

or

caso

:

re

gist

ro p

rocu

rado

éo

prim

eiro

con

sulta

do

f(

n)

= 1

p

ior

caso

:

caso

méd

io:


Exe

mpl

o-

Reg

istr

osde

um

Arq

uivo

S

eja

fum

a fu

nção

deco

mpl

exid

ade

tal q

uef(

n)

éo

núm

ero

dere

gist

ros

cons

ulta

dos

noar

quiv

o(n

úmer

ode

veze

s qu

ea

chav

ede

cons

ulta

éco

mpa

rada

com

ach

ave

deca

da r

egis

tro)

.

m

elh

or

caso

:

re

gist

ro p

rocu

rado

éo

prim

eiro

con

sulta

do

f(

n)

= 1

p

ior

caso

:

re

gist

ro p

rocu

rado

éo

últim

o co

nsul

tado

ou

não

está

pres

ente

noar

quiv

o;

caso

méd

io:


Exe

mpl

o-

Reg

istr

osde

um

Arq

uivo

S

eja

fum

a fu

nção

deco

mpl

exid

ade

tal q

uef(

n)

éo

núm

ero

dere

gist

ros

cons

ulta

dos

noar

quiv

o(n

úmer

ode

veze

s qu

ea

chav

ede

cons

ulta

éco

mpa

rada

com

ach

ave

deca

da r

egis

tro)

.

m

elh

or

caso

:

re

gist

ro p

rocu

rado

éo

prim

eiro

con

sulta

do

f(

n)

= 1

p

ior

caso

:

re

gist

ro p

rocu

rado

éo

últim

o co

nsul

tado

ou

não

está

pres

ente

noar

quiv

o;

f(

n)

= n

caso

méd

io:


Exe

mpl

o-

Reg

istr

osde

um

Arq

uivo

N

oes

tudo

doca

so m

édio

,vam

os c

onsi

dera

r qu

e to

da p

esqu

isa

recu

pera

umre

gist

ro.

S

e p

ifo

r a

prob

abili

dade

dequ

eo

i-ési

mo

regi

stro

sej

a pr

ocur

ado,

eco

nsid

eran

do q

ue

para

rec

uper

aro

i-ési

mo

regi

stro

são

ne

cess

ária

sico

mpa

raçõ

es,e

ntão

:

f(n)

= 1

x p

1+

2 x

p2

+ 3

x p

3+

... +

n x

pn


Exe

mpl

o-

Reg

istr

osde

um

Arq

uivo

P

ara

calc

ular

f(n)

bast

a co

nhec

era

dist

ribui

ção

depr

obab

ilida

des

pi.

S

eca

da r

egis

tro

tiver

am

esm

a pr

obab

ilida

dede

ser

aces

sado

que

todo

s os

out

ros,

entã

o

pi=

1/n

, 1

≤i ≤

n


Exe

mpl

o-

Reg

istr

osde

um

Arq

uivo

P

ara

calc

ular

f(n)

bast

a co

nhec

era

dist

ribui

ção

depr

obab

ilida

des

pi.

S

eca

da r

egis

tro

tiver

am

esm

a pr

obab

ilida

dede

ser

aces

sado

que

todo

s os

out

ros,

entã

o

N

esse

cas

o:

A

anál

ise

doca

so e

sper

ado

reve

la q

ue u

ma

pesq

uisa

com

suce

sso

exam

ina

apro

xim

adam

ente

m

etad

edo

sre

gist

ros.

pi=

1/n

, 1

≤i ≤

n


Exe

mpl

o-

Reg

istr

osde

um

Arq

uivo

S

eja

fum

a fu

nção

deco

mpl

exid

ade

tal q

uef(

n)

éo

núm

ero

dere

gist

ros

cons

ulta

dos

noar

quiv

o(n

úmer

ode

veze

s qu

ea

chav

ede

cons

ulta

éco

mpa

rada

com

ach

ave

deca

da r

egis

tro)

.

m

elh

or

caso

:

re

gist

ro p

rocu

rado

éo

prim

eiro

con

sulta

do

f(

n)

= 1

p

ior

caso

:

re

gist

ro p

rocu

rado

éo

últim

o co

nsul

tado

ou

não

está

pres

ente

noar

quiv

o;

f(

n)

= n

caso

méd

io:

f(

n)

= (

n +

1)/

2.


Exe

mpl

o-

Mai

ore

Men

or E

lem

ento

(1)

C

onsi

dere

opr

oble

ma

deen

cont

rar

om

aior

e o

men

or

elem

ento

de u

mve

tor

dein

teiro

sA

[n];

n ≥

1.

U

mal

gorit

mo

sim

ples

pode

ser

deriv

ado

doal

gorit

mo

apre

sent

ado

nopr

ogra

ma

para

ach

aro

mai

or e

lem

ento

.

void MaxMin1(intA[n],int*Max,int*Min)

inti;

*Max = A[0];

*Min = A[0];

for (i = 1; i < n; i++)

if (A[i] > *Max) *Max = A[i];

if (A[i] < *Min) *Min = A[i];


Qua

lafu

nção

deco

mpl

exid

ade

para

Max

Min

1?


inti;

*Max = A[0];

*Min = A[0];

for (i = 1; i < n; i++)




Qua

lafu

nção

deco

mpl

exid

ade

para

Max

Min

1?

S

eja

f(n

)o

núm

ero

deco

mpa

raçõ

es e

ntre

os

elem

ento

sde

A, s

e A

cont

iver

nel

emen

tos.

Lo

go f

(n)

= 2

(n-1

)pa

ran

> 0

,par

ao

mel

hor

caso

,pio

r ca

soe

caso

méd

io.


inti;

*Max = A[0];

*Min = A[0];

for (i = 1; i < n; i++)




Exe

mpl

o-

Mai

ore

Men

or E

lem

ento

(2)

M

axM

in1

pode

ser

faci

lmen

te m

elho

rado

: aco

mpa

raçã

oA

[i] <

Min

sóé

nece

ssár

ia q

uand

oa

com

para

ção

A[i]

> M

axdá

fals

o.


inti;

*Max = A[0];

*Min = A[0];

for (i = 1; i < n; i++)


elseif (A[i] < *Min) *Min = A[i];


Qua

lafu

nção

deco

mpl

exid

ade

para

Max

Min

2?


inti;

*Max = A[0];

*Min = A[0];

for (i = 1; i < n; i++)




Qua

lafu

nção

deco

mpl

exid

ade

para

Max

Min

2?

Melh

or

caso

:

Pio

r caso

:

Caso

méd

io:


inti;

*Max = A[0];

*Min = A[0];

for (i = 1; i < n; i++)




Qua

lafu

nção

deco

mpl

exid

ade

para

Max

Min

2?

Melh

or

caso

:

quan

do o

s el

emen

tos

estã

o em

ord

em c

resc

ente

;

Pio

r caso

:

Caso

méd

io:


inti;

*Max = A[0];

*Min = A[0];

for (i = 1; i < n; i++)




Qua

lafu

nção

deco

mpl

exid

ade

para

Max

Min

2?

Melh

or

caso

:

quan

do o

s el

emen

tos

estã

o em

ord

em c

resc

ente

;

f(n

) =

n –

1

Pio

r caso

:

Caso

méd

io:


inti;

*Max = A[0];

*Min = A[0];

for (i = 1; i < n; i++)




Qua

lafu

nção

deco

mpl

exid

ade

para

Max

Min

2?

Melh

or

caso

:

quan

do o

s el

emen

tos

estã

o em

ord

em c

resc

ente

;

f(n)

= n

–1

Pio

r caso

:

quan

do o

s el

emen

tos

estã

o em

ord

em d

ecre

scen

te;

Caso

méd

io:


inti;

*Max = A[0];

*Min = A[0];

for (i = 1; i < n; i++)




Qua

lafu

nção

deco

mpl

exid

ade

para

Max

Min

2?

Melh

or

caso

:

quan

do o

s el

emen

tos

estã

o em

ord

em c

resc

ente

;

f(n)

= n

–1

Pio

r caso

:

quan

do o

s el

emen

tos

estã

o em

ord

em d

ecre

scen

te;

f(

n)

= 2

(n –

1)

Caso

méd

io:


inti;

*Max = A[0];

*Min = A[0];

for (i = 1; i < n; i++)




Qua

lafu

nção

deco

mpl

exid

ade

para

Max

Min

2?

Melh

or

caso

:

quan

do o

s el

emen

tos

estã

o em

ord

em c

resc

ente

;

f(n)

= n

–1

Pio

r caso

:

quan

do o

s el

emen

tos

estã

o em

ord

em d

ecre

scen

te;

f(

n)

= 2

(n –

1)

Caso

méd

io:

N

oca

so m

édio

, A[i]

ém

aior

doqu

eM

ax a

met

ade

das

veze

s.


inti;

*Max = A[0];

*Min = A[0];

for (i = 1; i < n; i++)




Qua

lafu

nção

deco

mpl

exid

ade

para

Max

Min

2?

Melh

or

caso

:

quan

do o

s el

emen

tos

estã

o em

ord

em c

resc

ente

;

f(n

) =

n –

1

Pio

r caso

:

quan

do o

s el

emen

tos

estã

o em

ord

em d

ecre

scen

te;

f(

n)

= 2

(n –

1)

Caso

méd

io:

N

oca

so m

édio

, A[i]

ém

aior

doqu

eM

ax a

met

ade

das

veze

s.

f(n

) =

3n

/2 –

3/2


inti;

*Max = A[0];

*Min = A[0];

for (i = 1; i < n; i++)




Qua

lafu

nção

deco

mpl

exid

ade

para

Max

Min

2?

Melh

or

caso

:

quan

do o

s el

emen

tos

estã

o em

ord

em c

resc

ente

;

f(n)

= n

–1

Pio

r caso

:

quan

do o

s el

emen

tos

estã

o em

ord

em d

ecre

scen

te;

f(

n)

= 2

(n –

1)

Caso

méd

io:

N

oca

so m

édio

, A[i]

ém

aior

doqu

eM

ax a

met

ade

das

veze

s.

f(n

) =

n –

1 +

(n

–1

)/2 =

3n

/2 –

3/2


inti;

*Max = A[0];

*Min = A[0];

for (i = 1; i < n; i++)




Exe

mpl

o-

Mai

ore

Men

or E

lem

ento

(3)

C

onsi

dera

ndo

onú

mer

ode

com

para

ções

rea

lizad

as,e

xist

ea

poss

ibili

dade

deob

ter

umal

gorit

mo

mai

s ef

icie

nte:

•C

ompa

reos

ele

men

tos

de A

aos

pare

s,se

para

ndo-

os e

m

dois

sub

conj

unto

s(m

aior

es e

mum

em

enor

es e

m o

utro

), a

um

cust

ode

n/

2co

mpa

raçõ

es.

•O

máx

imo

éob

tido

dosu

bcon

junt

o qu

e co

ntém

os

mai

ores

el

emen

tos,

a u

mcu

sto

de

n/2

-1co

mpa

raçõ

es

•O

mín

imo

éob

tido

dosu

bcon

junt

o qu

e co

ntém

os

men

ores

el

emen

tos,

a u

mcu

sto

de

n/2

-1co

mpa

raçõ

es


Exe

mpl

o-

Mai

ore

Men

or E

lem

ento

(3)

C

onsi

dera

ndo

onú

mer

ode

com

para

ções

rea

lizad

as,e

xist

ea

poss

ibili

dade

deob

ter

umal

gorit

mo

mai

s ef

icie

nte:

•C

ompa

reos

ele

men

tos

de A

aos

pare

s,se

para

ndo-

os e

m

dois

sub

conj

unto

s(m

aior

es e

mum

em

enor

es e

m o

utro

), a

um

cust

ode

n/

2co

mpa

raçõ

es.

•O

máx

imo

éob

tido

dosu

bcon

junt

o qu

e co

ntém

os

mai

ores

el

emen

tos,

a u

mcu

sto

de

n/2

-1co

mpa

raçõ

es

•O

mín

imo

éob

tido

dosu

bcon

junt

o qu

e co

ntém

os

men

ores

el

emen

tos,

a u

mcu

sto

de

n/2

-1co

mpa

raçõ

es


Qua

lafu

nção

deco

mpl

exid

ade

para

est

eno

voal

gorit

mo?

O

sel

emen

tos

de A

são

com

para

dos

dois

ado

is. O

sel

emen

tos

mai

ores

são

com

para

dos

com

Ma

x e

os

elem

ento

s m

enor

es s

ão c

ompa

rado

sco

m M

in.

Q

uand

on

éím

par,

oel

emen

to q

ue e

stá

na p

osiç

ãoA

[n] é

dupl

icad

o na

pos

ição

A[n

+ 1

]par

a ev

itar

umtr

atam

ento

deex

ceçã

o.

P

ara

esta

impl

emen

taçã

o:

nopi

or c

aso,

mel

hor

caso

eca

so m

édio


Exe

mpl

o-

Mai

ore

Men

or E

lem

ento

(3)

void MaxMin3(VetorA,

int*Max,

int*Min)

int

i,FimDoAnel;

if ((n % 2) > 0)

A[n] = A[n -1];

FimDoAnel= n;

elseFimDoAnel= n -1;

if (A[0] > A[1])

*Max = A[0]; *Min = A[1];

else

*Max = A[1]; *Min = A[0];

i = 3;

while (i <=FimDoAnel)

if (A[i -1] > A[i])

if (A[i -1] > *Max) *Max = A[i -1];


else

if (A[i -1] < *Min) *Min = A[i -1];

if (A[i] > *Max)*Max = A[i];

i += 2;


Qua

lafu

nção

deco

mpl

exid

ade

para

Max

Min

3?

Qua

ntas

com

para

ções

são

feita

s em

Max

Min

3?


Qua

lafu

nção

deco

mpl

exid

ade

para

Max

Min

3?

Qua

ntas

com

para

ções

são

feita

s em

Max

Min

3?

1ª

.com

para

ção

feita

1ve

z

2ª

.com

para

ção

feita

n/2

-1

veze

s

3ª

. e 4

ª.co

mpa

raçõ

es fe

itas

n/2

–1

veze

s


Qua

lafu

nção

deco

mpl

exid

ade

para

Max

Min

3?

Qua

ntas

com

para

ções

são

feita

s em

Max

Min

3?

1ª

.com

para

ção

feita

1ve

z

2ª

.com

para

ção

feita

n/2

-1

veze

s

3ª

. e 4

ª.co

mpa

raçõ

es fe

itas

n/2

–1

veze

s

f(n)

= 1

+ n

/2 –

1 +

2

* (

n/2

–1)

f(n)

= (

3n –

6)/

2 +

1

f(n)

= 3

n/2

–3 +

1 =

3n/2

-2


Com

para

ção

entr

e os

Alg

oritm

os

A

tabe

la a

pres

enta

um

a co

mpa

raçã

o en

tre

os a

lgor

itmos

dos

prog

ram

asM

axM

in1,

Max

Min

2 e

Max

Min

3,co

nsid

eran

doo

núm

ero

deco

mpa

raçõ

es c

omo

med

ida

deco

mpl

exid

ade.

O

sal

gorit

mos

Max

Min

2 e

Max

Min

3sã

o su

perio

res

ao a

lgor

itmo

Max

Min

1 de

form

age

ral.

O

algo

ritm

oM

axM

in3

ésu

perio

rao

alg

oritm

oM

axM

in2

com

rela

ção

ao p

ior

caso

eba

stan

te p

róxi

mo

quan

to a

o ca

so m

édio

.


Lim

ite In

ferio

r -

Uso

de

um O

rácu

lo

E

xist

epo

ssib

ilida

de

de

obte

r um

al

gorit

mo

Max

Min

m

ais

efic

ient

e?

P

ara

resp

onde

r te

mos

de

conh

ecer

o l

imit

e i

nfe

rio

r pa

ra e

ssa

clas

se d

e al

gorit

mos

.

T

écni

cam

uito

util

izad

a: u

so d

e um

orá

culo

.

D

ado

um

mod

elo

de

com

puta

ção

que

expr

esse

o

com

port

amen

to d

o al

gorit

mo,

o o

rácu

lo i

nfor

ma

o re

sulta

do d

e ca

da p

asso

pos

síve

l (no

cas

o, o

res

ulta

do d

e ca

da c

ompa

raçã

o).

P

ara

deriv

ar o

lim

ite in

ferio

r, o

orá

culo

pro

cura

sem

pre

faze

r co

m

que

o al

gorit

mo

trab

alhe

o m

áxim

o, e

scol

hend

o co

mo

resu

ltado

da

pr

óxim

a co

mpa

raçã

o aq

uele

qu

e ca

use

o m

aior

tr

abal

ho

poss

ível

nec

essá

rio p

ara

dete

rmin

ar a

res

post

a fin

al.


Exe

mpl

o de

Uso

de

um O

rácu

lo

T

eo

rem

a:

Qu

alq

ue

r a

lgo

ritm

o p

ara

e

nc

on

tra

r o

m

aio

re

o

m

en

or

ele

me

nto

d

e

um

c

on

jun

to

co

m

ne

lem

en

tos

n

ão

o

rde

na

do

s,

n>

1,

faz p

elo

me

no

s

3n

/2 -

2 c

om

pa

raç

õe

s.

P

rov

a:

A t

éc

nic

a u

tili

za

da

de

fin

e u

m o

rác

ulo

que

des

crev

e o

com

port

amen

to

do

algo

ritm

o po

r m

eio

de

um

conj

unto

de

n–tu

plas

, m

ais

um c

onju

nto

de r

egra

s as

soci

adas

que

mos

tram

as

tup

las

poss

ívei

s (e

stad

os)

queu

m a

lgor

itmo

pode

ass

umir

a pa

rtir

de u

ma

dada

tupl

a e

uma

únic

a co

mpa

raçã

o.


Exe

mpl

o de

Uso

de

um O

rácu

lo

U

ma

4–tu

pla,

rep

rese

ntad

a po

r (a

; b; c

; d),

ond

e os

ele

men

tos

de:

a:

nun

ca fo

ram

com

para

dos;

b:

fora

mve

nced

ores

e

nunc

a pe

rder

am

em

com

para

ções

re

aliz

adas

;

c:

fora

mpe

rded

ores

e

nunc

a ve

ncer

amem

co

mpa

raçõ

es

real

izad

as;

d:

fora

mve

nced

ores

e p

erde

dore

s em

com

para

ções

rea

lizad

as.

O

algo

ritm

o in

icia

noes

tado

(n, 0

, 0, 0

)

e te

rmin

aco

m (

0, 1

, 1, n

-2)

.


Exe

mpl

o de

Uso

de

um O

rácu

lo

A

pós

cada

com

para

ção

a tu

pla

(a;

b; c

; d)

con

segu

e pr

ogre

dir

apen

as

se e

la a

ssum

e um

den

tre

os s

eis

esta

dos

poss

ívei

s ab

aixo

:

(a

-2,

b +

1, c

+ 1

, d)

se a

≥2

(do

is e

lem

ento

s de

a s

ão c

ompa

rado

s)

(a

-1,

b +

1, c

, d)

ou (

a -

1, b

, c +

1, d

) ou

(a

-1,

b, c

, d +

1)

se a

≥1

(um

ele

men

to d

e a

com

para

do c

om u

m d

e b

ou u

m d

e c)

(a

, b -

1, c

, d +

1)

se b

≥2

(doi

s el

emen

tos

de b

são

com

para

dos)

(a

, b, c

-1,

d +

1)

se c

≥2

(doi

s el

emen

tos

de c

são

com

para

dos)


Exe

mpl

o de

Uso

de

um O

rácu

lo

O

pr

imei

ro

pass

o re

quer

ne

cess

aria

men

te

a m

anip

ulaç

ão

do

com

pone

nte

a.

O

ca

min

ho

mai

s rá

pido

pa

ra

leva

ra

até

zero

re

quer

[n

/2]

mud

ança

s de

est

ado

e te

rmin

a co

m a

tup

la (

0, n

/2,

n/2,

0)

(por

m

eio

de c

ompa

raçã

o do

s el

emen

tos

de a

dois

a d

ois)

.

A

segu

ir,pa

ra r

eduz

iro

com

pone

nte

bat

éum

são

nece

ssár

ias

n/

2 -

1 e

mud

ança

sde

esta

do(m

ínim

ode

com

para

ções

ne

cess

ária

s pa

ra o

bter

om

aior

ele

men

tode

b).

Id

empa

rac,

com

n/2

-1

mud

ança

sde

esta

do.


Exe

mpl

o de

Uso

de

um O

rácu

lo

Lo

go, p

ara

obte

r o

esta

do (

0, 1

, 1, n

-2)

a p

artir

do

esta

do (

n,

0, 0

, 0)

são

nec

essá

rias

n/2

+ n

/2 -

1 +

[ n/

2 ] -

1= [3

n/2]

–2

com

para

ções

.

O

teor

ema

nos

diz

que

se o

núm

ero

de c

ompa

raçõ

es e

ntre

os

elem

ento

s de

um

vet

or f

or u

tiliz

ado

com

o m

edid

a de

cus

to,

entã

o o

algo

ritm

o M

axM

in3

éó

tim

o.


Com

port

amen

to A

ssin

tótic

o de

Fun

ções

O

pa

râm

etro

n

forn

ece

uma

med

ida

da

dific

ulda

de

para

se

re

solv

er o

pro

blem

a.

P

ara

valo

res

sufic

ient

emen

te p

eque

nos

de n

, qu

alqu

er a

lgor

itmo

cust

a po

uco

para

ser

exe

cuta

do, m

esm

o os

inef

icie

ntes

.

A

e

sc

olh

a

do

a

lgo

ritm

o

não

éum

pr

oble

ma

críti

co

para

pr

oble

mas

de

tam

anho

peq

ueno

.

Lo

go,

a an

ális

e de

alg

oritm

os é

real

izad

a pa

ra v

alor

es g

rand

es

de n

.

E

stud

a-se

o c

ompo

rtam

ento

ass

intó

tico

das

fun

çõ

es

de

cu

sto

(c

ompo

rtam

ento

de

suas

fun

ções

de

cust

o pa

ra v

alor

es g

rand

es

de n

)

O

co

mpo

rtam

ento

as

sint

ótic

o de

f(

n)

repr

esen

ta

o lim

ite

do

com

port

amen

to d

o cu

sto

quan

do n

cre

sce.


Dom

inaç

ão a

ssin

tótic

a

A

aná

lise

de u

m a

lgor

itmo

gera

lmen

te c

onta

com

ape

nas

algu

mas

ope

raçõ

es e

lem

enta

res.

A

med

ida

de c

usto

ou

med

ida

de c

ompl

exid

ade

rela

ta o

cr

esci

men

to a

ssin

tótic

o da

ope

raçã

o co

nsid

erad

a.

D

efi

niç

ão

: Um

a fu

nção

f(n)

do

min

a a

ss

into

tic

am

en

te o

utra

fu

nção

g(n

)se

exi

stem

dua

s co

nsta

ntes

pos

itiva

s c

e m

tais

que

, pa

ra n

≥m

, tem

os |g

(n)|

≤c

x |f(

n)|.


Dom

inaç

ão a

ssin

tótic

a

Ex

em

plo

:

S

ejam

g(n)

= (

n +

1)²

e f(

n) =

n².

A

s fu

nçõe

s g(

n) e

f(n)

dom

inam

ass

into

ticam

ente

um

a

a ou

tra,

des

de q

ue

|(n

+ 1

)²| ≤

4|n²

| par

a n ≥

1 e

|n²|

≤|(

n +

1)²

| par

a n ≥

0.


Nota

ção O

D

efi

niç

ão

: Um

a fu

nção

g(n

)é

O(f

(n))

se e

xist

em

duas

con

stan

tes

posi

tivas

ce

mta

is q

ue

g(n

) ≤ ≤≤≤

cf(

n),

par

a to

do n

≥ ≥≥≥m

.

O

valo

r da

con

stan

tem

mos

trad

oé

om

enor

val

or

poss

ível

,mas

qua

lque

r va

lor

mai

or ta

mbé

mé

válid

o.


Nota

ção O

E

scre

vem

os g

(n)

= O

(f(n

))pa

ra e

xpre

ssar

que

f(n

)do

min

a as

sint

otic

amen

teg

(n).

Lê-

se g

(n)

éda

ord

em n

o m

áxim

o f(

n).

E

xem

plo:

qua

ndo

dize

mos

que

o te

mpo

de

exec

ução

T(n

)de

um

pr

ogra

ma

éO

(n²)

, sig

nific

a qu

e ex

iste

m c

onst

ante

s c

e m

tais

que

, pa

ra v

alor

es d

en≥ ≥≥≥

m, T

(n)≤ ≤≤≤

cn

².

E

xem

plo

gráf

ico

de d

omin

ação

ass

intó

tica

que

ilust

ra a

not

ação

O.


Exem

plo

s d

e N

ota

ção O

E

xe

mp

lo: g

(n)

= (

n+

1)2 .

–Lo

go g

(n)

éO

(n2 )

, qua

ndo

m=

1 e

c=

4.

–Is

to p

orqu

e (n

+ 1

)2 ≤

4n2

para

n≥

1.

E

xe

mp

lo: g

(n)

= n

e f(

n)

= n

2 .

–S

abem

os q

ue g

(n)

éO

(n2 )

, poi

s pa

ra n≥

0, n≤

n2 .

–E

ntre

tant

o f(

n)

não

éO

(n).

–S

upon

ha q

ue e

xist

am c

onst

ante

s c

e m

tais

que

par

a to

do n

≥m

, n

2 ≤

cn

.

–Lo

go c≥

npa

ra q

ualq

uer

n≥

m, e

não

exi

ste

uma

cons

tant

e c

que

poss

a se

r m

aior

ou

igua

l a n

para

todo

n.


Opera

ções c

om

a N

ota

ção O


Exem

plo

s d

e N

ota

ção O

E

xe

mp

lo: g

(n)

= 3

n3

+ 2

n2

+ n

éO

(n3 )

.

–B

asta

mos

trar

que

3n

3+

2n

2 +

n ≤

6n3 ,

par

a n≥

0.

–A

funç

ão g

(n)

= 3

n3

+ 2

n2

+ n

éta

mbé

m O

(n4 )

, ent

reta

nto

esta

af

irmaç

ão é

mai

s fr

aca

do q

ue d

izer

que

g(n

) é

O(n

3 ).

E

xe

mp

lo: g

(n)

= lo

g 5n

éO

(log

n).

–O

log b

ndi

fere

do

log c

npo

r um

a co

nsta

nte

que

no c

aso

élo

g bc.

–C

omo

n=

clo

gcn, t

oman

do o

loga

ritm

o ba

se b

em a

mbo

s os

lado

s da

igua

ldad

e, te

mos

que

log b

n=

log b

clo

gcn

= lo

g cn

x lo

g bc.


Opera

ções c

om

a N

ota

ção O

Ex

em

plo

: reg

ra d

a so

ma

O(f

(n))

+ O

(g(n

)).

S

upon

ha tr

ês tr

echo

s cu

jos

tem

pos

de e

xecu

ção

são

O(n

), O

(n2 )

e

O(n

log

n).

O

tem

po d

e ex

ecuç

ão d

os d

ois

prim

eiro

s tr

echo

s é

O(m

ax(n

, n2 )

),

que

éO

(n2 )

.

O

tem

po d

e ex

ecuç

ão d

e to

dos

os tr

ês tr

echo

s é

entã

o O

(max

(n2 ,

nlo

g n

)), q

ue é

O(n

2 ).


No

taçã

o Ω

E

spec

ifica

um li

mite

infe

rior

para

g(n)

.

D

efi

niç

ão

: Um

a fu

nção

g(n)

é(f

(n))

se

exis

tirem

dua

s co

nsta

ntes

c e

m ta

is q

ueg(

n) ≥

cf(n

), p

ara

todo

n ≥

m.

E

xem

plo

: Par

a m

ostr

ar q

ueg(

n) =

3n3

+ 2

n2éΩ

(n3 )

bas

ta

faze

rc

= 1

, e e

ntão

3n3

+ 2

n2≥

n3pa

ran ≥

0.

E

xem

plo

gráf

ico

para

a no

taçã

o:

P

ara

todo

s os

val

ores

àdi

reita

de m

, o v

alor

de

g(n)

est

áso

bre

ou

acim

ado

val

or d

e cf

(n).


No

taçã

o Ө

D

efi

niç

ão

: Um

a fu

nção

g(n

)éӨ

(f(n

))se

exi

stire

m

cons

tant

es p

ositi

vas

c 1, c

2e

m ta

is q

ue

0 ≤

c 1f(

n) ≤

g(n)

≤c 2

f(n)

, par

a to

don ≥

m.

E

xem

plo

gráf

ico

para

a no

taçã

o:


No

taçã

o Ө

D

izem

os q

ueg(n

)=

Ө(f

(n))

se e

xist

irem

con

stan

tes

c 1,

c 2e

m ta

is q

ue, p

ara

todo

n ≥

m, o

val

or d

e g(

n) e

stá

sobr

e ou

aci

ma

de c

1f(n

) e

sobr

e ou

aba

ixo

de c

2f(n

).

Is

toé,

par

a to

don ≥

m, a

funç

ãog(n

)é

igua

la f(

n)

a m

enos

de u

ma

cons

tant

e.

N

este

cas

o, f(

n)

éum

lim

ite a

ssin

tóti

co

fir

me.


No

taçãoo

U

sada

para

def

inir

um li

mite

sup

erio

r qu

e nã

o é

assi

ntot

icam

ente

firm

e.

D

efi

niç

ão

: Um

a fu

nção

g(n

) é

o(f

(n))

se,

par

a qu

alqu

er

cons

tant

e c

> 0

, ent

ão 0

≤g(n

) <

cf(

n)

para

todo

n≥

m.

E

xem

plo

: 2n

= o

(n2 )

, mas

2n

2 ≠

o(n

2 ).


No

taçãoo

E

mg(n

) =

O(f

(n))

, a e

xpre

ssão

0 ≤

g(n

) ≤

cf(

n)

évá

lida

para

al

gum

a co

nsta

nte

c>

0, m

as e

m g

(n)

= o

(f(n

)), a

exp

ress

ão 0

≤g(n

) <

cf(

n)

évá

lida

para

toda

s as

con

stan

tes

c>

0.

N

a no

taçã

o o, a

funç

ão g

(n)

tem

um

cre

scim

ento

mui

to m

enor

qu

e f(

n)

quan

do n

tend

e pa

ra in

finito

.

Alg

uns

auto

res

usam

pa

ra a

def

iniç

ão d

a no

taçã

o o.


No

tação

ω

P

or a

nalo

gia,

a n

otaç

ão ω

está

rela

cion

ada

com

a n

otaç

ão Ω

da

mes

ma

form

a qu

e a

nota

ção

oes

táre

laci

onad

a co

m a

not

ação

O.

D

efi

niç

ão

: Um

a fu

nção

g(n

) éω

(f(n

)) s

e, p

ara

qual

quer

co

nsta

nte

c>

0, e

ntão

0 <

= c

f(n)

< g

(n)

para

todo

n >

= m

.

E

xem

plo

:

, m

as

A

rel

ação

g(n

) =

ω(f

(n))

impl

ica

se

o lim

ite

exis

tir.


Cla

sses d

e C

om

po

rtam

en

toA

ssin

tóti

co

S

e f

éum

a fu

nção

de c

om

ple

xid

ad

e p

ara

um a

lgor

itmo

F,

entã

o O

(f)

éco

nsid

erad

a a

co

mp

lexid

ad

e a

ssin

tóti

ca o

u o

com

port

amen

to a

ssin

tótic

o do

alg

oritm

o F

.

A

rel

ação

de

dom

inaç

ão a

ssin

tótic

a pe

rmite

com

para

r fu

nçõe

s de

com

plex

idad

e.

E

ntre

tant

o, s

e as

funç

ões

fe

gdo

min

am a

ssin

totic

amen

te u

ma

a ou

tra,

ent

ão o

s al

gorit

mos

ass

ocia

dos

são

equi

vale

ntes

.

N

este

sca

sos,

o c

ompo

rtam

ento

ass

intó

tico

não

serv

e pa

ra

com

para

r os

alg

oritm

os.


Cla

sses d

e C

om

po

rtam

en

toA

ssin

tóti

co

P

orex

empl

o, c

onsi

dere

doi

s al

gorit

mos

F e

G a

plic

ados

àm

esm

a cl

asse

de

prob

lem

as, s

endo

que

F le

va tr

ês v

ezes

o

tem

po d

e G

ao

sere

m e

xecu

tado

s, is

to é

, f(n

) =

3g(n

), s

endo

que

O

(f(n

)) =

O(g

(n))

.

Lo

go, o

com

port

amen

to a

ssin

tótic

o nã

o se

rve

para

com

para

r os

al

gorit

mos

F e

G, p

orqu

e el

es d

ifere

m a

pena

s po

r um

a co

nsta

nte.


Co

mp

ara

ção

de P

rog

ram

as

P

odem

osav

alia

r pr

ogra

mas

com

para

ndo

as fu

nçõe

s de

co

mpl

exid

ade,

neg

ligen

cian

do a

s co

nsta

ntes

de

prop

orci

onal

idad

e.

U

m p

rogr

ama

com

tem

po d

e ex

ecuç

ão O

(n)

ém

elho

r qu

e ou

tro

com

tem

po O

(n2 )

.

P

orém

, as

cons

tant

es d

e pr

opor

cion

alid

ade

pode

m a

ltera

r es

ta

cons

ider

ação

.


Co

mp

ara

ção

de P

rog

ram

as

E

xem

plo:

um

pro

gram

a le

va 1

00n

unid

ades

de

tem

po p

ara

ser

exec

utad

o e

outr

o le

va 2

n2 .

Q

uald

os d

ois

prog

ram

as é

mel

hor?

–de

pend

e do

tam

anho

do

prob

lem

a.–

Par

a n

< 5

0, o

pro

gram

a co

m te

mpo

2n

2é

mel

hor

do q

ue o

qu

e po

ssui

tem

po 1

00n.

–P

ara

prob

lem

as c

om e

ntra

da d

e da

dos

pequ

ena

épr

efer

ível

us

ar o

pro

gram

a cu

jo te

mpo

de

exec

ução

éO

(n2 )

.–

Ent

reta

nto,

qua

ndo

ncr

esce

, o p

rogr

ama

com

tem

po d

e ex

ecuç

ão O

(n2 )

leva

mui

to m

ais

tem

po q

ue o

pro

gram

a O

(n).


Pri

ncip

ais

Cla

sses d

e P

rob

lem

as

f(

n)

= O

(1).

–A

lgor

itmos

de

com

plex

idad

e O

(1)

são

dito

s de

co

mp

lex

ida

de

c

on

sta

nte

.

–U

sodo

alg

oritm

o in

depe

nde

de n

.

–A

s in

stru

ções

do

algo

ritm

o sã

o ex

ecut

adas

um

núm

ero

fixo

de

veze

s.


Pri

ncip

ais

Cla

sses d

e P

rob

lem

as

f(

n)

= O

(log

n).

–U

m a

lgor

itmo

de c

ompl

exid

ade

O(lo

g n

) é

dito

ter

co

mp

lex

ida

de

lo

ga

rítm

ica

.

–T

ípic

o em

alg

oritm

os q

ue tr

ansf

orm

am u

m p

robl

ema

em o

utro

s m

enor

es.

–P

ode-

se c

onsi

dera

r o

tem

po d

e ex

ecuç

ão c

omo

men

or q

ue u

ma

cons

tant

e gr

ande

.

–Q

uand

o n

ém

il, lo

g 2n ≈

10, q

uand

o n

é1

milh

ão, l

og2n

≈20

.

–P

ara

dobr

ar o

val

or d

e lo

g n

tem

os d

e co

nsid

erar

o q

uadr

ado

de n

.

–A

bas

e do

loga

ritm

o m

uda

pouc

o es

tes

valo

res:

qua

ndo

né

1 m

ilhão

, o lo

g 2né

20 e

o lo

g 10n

é6.


Pri

ncip

ais

Cla

sses d

e P

rob

lem

as

f(

n)

= O

(n).

–U

m a

lgor

itmo

de c

ompl

exid

ade

O(n

) é

dito

ter

co

mp

lex

ida

de

lin

ea

–E

m g

eral

, um

peq

ueno

trab

alho

ére

aliz

ado

sobr

e ca

da e

lem

ento

de

entr

ada.

–É

a m

elho

r si

tuaç

ão p

ossí

vel p

ara

um a

lgor

itmo

que

tem

de

proc

essa

r/pr

oduz

ir n

elem

ento

s de

ent

rada

/saí

da.

–C

ada

vez

que

ndo

bra

de ta

man

ho, o

tem

po d

e ex

ecuç

ão d

obra

.


Pri

ncip

ais

Cla

sses d

e P

rob

lem

as

f(

n)

= O

(n lo

g n

).

–T

ípic

o em

alg

oritm

os q

ue q

uebr

am u

m p

robl

ema

em o

utro

s m

enor

es, r

esol

vem

cad

a um

del

es in

depe

nden

tem

ente

e a

junt

ando

as

solu

ções

dep

ois.

–Q

uand

o n

é1

milh

ão, n

log 2

né

cerc

a de

20

milh

ões.

–Q

uand

o n

é2

milh

ões,

nlo

g 2n

éce

rca

de 4

2 m

ilhõe

s, p

ouco

mai

s do

qu

e o

dobr

o.


Pri

ncip

ais

Cla

sses d

e P

rob

lem

as

f(

n)

= O

(n2 )

.–

Um

alg

oritm

o de

com

plex

idad

e O

(n2 )

édi

to te

r c

om

ple

xid

ad

e

qu

ad

ráti

ca

.–

Oco

rrem

qua

ndo

os it

ens

de d

ados

são

pro

cess

ados

aos

par

es,

mui

tas

veze

s em

um

ane

l den

tro

de o

utro

.–

Qua

ndo

né

mil,

o n

úmer

o de

ope

raçõ

es é

da o

rdem

de

1 m

ilhão

.–

Sem

pre

que

ndo

bra,

o te

mpo

de

exec

ução

ém

ultip

licad

o po

r 4.

–Ú

teis

par

a re

solv

er p

robl

emas

de

tam

anho

s re

lativ

amen

te p

eque

nos.

f(

n)

= O

(n3 )

.–

Um

alg

oritm

o de

com

plex

idad

e O

(n3 )

édi

to te

r c

om

ple

xid

ad

e

cú

bic

a.

–Ú

teis

ape

nas

para

res

olve

r pe

quen

os p

robl

emas

.–

Qua

ndo

né

100,

o n

úmer

o de

ope

raçõ

es é

da o

rdem

de

1 m

ilhão

.–

Sem

pre

que

ndo

bra,

o te

mpo

de

exec

ução

fica

mul

tiplic

ado

por

8.


Pri

ncip

ais

Cla

sses d

e P

rob

lem

as

f(

n)

= O

(2n).

–U

m a

lgor

itmo

de c

ompl

exid

ade

O(2

n)

édi

to te

r c

om

ple

xid

ad

e

ex

po

ne

nc

ial.

–G

eral

men

te n

ão s

ão ú

teis

sob

o p

onto

de

vist

a pr

átic

o.–

Oco

rrem

na

solu

ção

de p

robl

emas

qua

ndo

se u

sa f

orç

a b

ruta

par

a re

solv

ê-lo

s.–

Qua

ndo

né

20, o

tem

po d

e ex

ecuç

ão é

cerc

a de

1 m

ilhão

. Qua

ndo

n

dobr

a, o

tem

po fi

ca e

leva

do a

o qu

adra

do.

f(

n)

= O

(n!)

.–

Um

alg

oritm

o de

com

plex

idad

e O

(n!)

édi

to te

r co

mpl

exid

ade

expo

nenc

ial,

apes

ar d

e O

(n!)

ter

com

port

amen

to m

uito

pio

r do

que

O(2

n).

–G

eral

men

te o

corr

em q

uand

o se

usa

fo

rça

bru

ta p

ara

na s

oluç

ão d

o pr

oble

ma.

–n

= 2

0 =

> 2

0! =

243

2902

0081

7664

0000

, um

núm

ero

com

19

dígi

tos.

–n

= 4

0 =

> u

m n

úmer

o co

m 4

8 dí

gito

s.


Co

mp

ara

ção

de F

un

çõ

es d

eC

om

ple

xid

ad

e


Alg

ori

tmo

s P

olin

om

iais

A

lgo

ritm

oe

xp

on

en

cia

l no

tem

po d

e ex

ecuç

ão te

m fu

nção

de

com

plex

idad

e O

(cn);

c>

1.

A

lgo

ritm

op

oli

no

mia

l no

tem

po d

e ex

ecuç

ão te

m fu

nção

de

com

plex

idad

e O

(p(n

)), o

nde

p(n

) é

um p

olin

ômio

.

A

dis

tinçã

o en

tre

este

s do

is ti

pos

de a

lgor

itmos

torn

a-se

si

gnifi

cativ

a qu

ando

o ta

man

ho d

o pr

oble

ma

a se

r re

solv

ido

cres

ce.

P

or is

so, o

s al

gorit

mos

pol

inom

iais

são

mui

to m

ais

útei

s na

pr

átic

a do

que

os

expo

nenc

iais

.

A

lgor

itmos

exp

onen

ciai

s sã

o ge

ralm

ente

sim

ples

var

iaçõ

es d

e pe

squi

sa e

xaus

tiva.


Alg

ori

tmo

s P

olin

om

iais

A

lgor

itmos

polin

omia

is s

ão g

eral

men

te o

btid

os m

edia

nte

ente

ndim

ento

mai

s pr

ofun

do d

a es

trut

ura

do p

robl

ema.

U

m p

robl

ema

éco

nsid

erad

o:–

intr

atáv

el: s

e nã

o ex

iste

um

alg

oritm

o po

linom

ial p

ara

reso

lvê-

lo.

–be

m r

esol

vido

: qua

ndo

exis

te u

m a

lgor

itmo

polin

omia

l par

a re

solv

ê-lo

.


Alg

ori

tmo

s P

olin

om

iais

x A

lgo

ritm

os

Exp

on

en

cia

is

A

dis

tinçã

o en

tre

algo

ritm

os p

olin

omia

is e

ficie

ntes

e

algo

ritm

os e

xpon

enci

ais

inef

icie

ntes

pos

sui v

ária

s ex

ceçõ

es.

E

xem

plo:

um

alg

oritm

o co

m fu

nção

de

com

plex

idad

e

f(n)=

2n

ém

ais

rápi

do q

ue u

m a

lgor

itmo

g(n

) =

n5

para

va

lore

s de

nm

enor

es o

u ig

uais

a 2

0.

T

ambé

mex

iste

m a

lgor

itmos

exp

onen

ciai

s qu

e sã

o m

uito

út

eis

na p

rátic

a.

E

xem

plo:

o a

lgor

itmo

Sim

plex

par

a pr

ogra

maç

ão li

near

po

ssui

com

plex

idad

e de

tem

po e

xpon

enci

al p

ara

o pi

or c

aso

mas

exe

cuta

mui

to r

ápid

o na

prá

tica.

T

ais

exem

plos

não

oco

rrem

com

freq

üênc

ia n

a pr

átic

a, e

m

uito

s al

gorit

mos

exp

onen

ciai

s co

nhec

idos

não

são

mui

to

útei

s.


Exem

plo

de A

lgo

ritm

o E

xp

on

en

cia

l

U

m c

aix

eir

o v

iaja

nte

des

eja

visi

tar

n ci

dade

s de

tal f

orm

a qu

e su

a vi

agem

inic

ie e

term

ine

em u

ma

mes

ma

cida

de, e

cad

a ci

dade

dev

e se

r vi

sita

da u

ma

únic

a ve

z.

S

upon

do q

ue s

empr

e há

uma

estr

ada

entr

e du

as c

idad

es

quai

sque

r, o

pro

blem

a é

enco

ntra

r a

men

or r

ota

para

a v

iage

m.

A

figu

ra il

ustr

a o

exem

plo

para

qua

tro

cida

des

c1, c

2, c

3, c

4,e

m

que

os n

úmer

os n

os a

rcos

indi

cam

a d

istâ

ncia

ent

re d

uas

cida

des.

O

per

curs

o <

c1, c

3, c

4, c

2, c

1>

éum

a so

luçã

o pa

ra o

pro

blem

a,

cujo

per

curs

o to

tal t

em d

istâ

ncia

24.


Exem

plo

de A

lgo

ritm

o E

xp

on

en

cia

l

U

m a

lgor

itmo

sim

ples

ser

ia v

erifi

car

toda

s as

rot

as e

esc

olhe

r a

men

or d

elas

.

H

á(n

-1)

! rot

as p

ossí

veis

e a

dis

tânc

ia to

tal p

erco

rrid

a em

cad

a ro

ta

envo

lve

n a

diçõ

es, l

ogo

o nú

mer

o to

tal d

e ad

içõe

s é

n!.

N

o ex

empl

o an

terio

r te

ríam

os 2

4 ad

içõe

s.

S

upon

ha a

gora

50

cida

des:

o n

úmer

o de

adi

ções

ser

ia 5

0! ≈

1064

.

E

m u

m c

ompu

tado

r qu

e ex

ecut

a 10

9ad

içõe

s po

r se

gund

o, o

tem

po

tota

l par

a re

solv

er o

pro

blem

a co

m 5

0 ci

dade

s se

ria m

aior

do

que

1045

sécu

los

sópa

ra e

xecu

tar

as a

diçõ

es.

O

pro

blem

a do

cai

xeiro

via

jant

e ap

arec

e co

m fr

eqüê

ncia

em

pr

oble

mas

rel

acio

nado

s co

m tr

ansp

orte

, mas

tam

bém

apl

icaç

ões

impo

rtan

tes

rela

cion

adas

com

otim

izaç

ão d

e ca

min

ho p

erco

rrid

o.


Técn

icas

de

An

álise

de

Alg

ori

tmo

s

D

eter

min

aro

tem

po d

eex

ecuç

ãode

um

prog

ram

a po

dese

r um

prob

lem

a m

atem

átic

o co

mpl

exo;

D

eter

min

ara

orde

mdo

tem

po d

eex

ecuç

ão,s

em p

reoc

upaç

ãoco

m o

valo

r da

con

stan

te e

nvol

vida

,pod

ese

rum

a ta

refa

mai

ssi

mpl

es.

A

anál

ise

utili

za té

cnic

asde

mat

emát

ica

disc

reta

,env

olve

ndo

cont

agem

ou

enum

eraç

ãodo

sel

emen

tos

de u

mco

njun

to:

–m

anip

ulaç

ãode

som

as,

–pr

odut

os,

–pe

rmut

açõe

s,–

fato

riais

,–

coef

icie

ntes

bin

omia

is,

–so

luçã

ode

eq

ua

çõ

es

de

rec

orr

ên

cia

.


An

álise

do

Tem

po

de

Execu

ção

C

oman

dode

atrib

uiçã

o, d

ele

itura

ou

dees

crita

: O(1

).

S

eqüê

ncia

deco

man

dos:

dete

rmin

ado

pelo

mai

orte

mpo

de

exec

ução

dequ

alqu

er c

oman

do d

a se

qüên

cia.

C

oman

dode

deci

são:

tem

po d

osco

man

dos

dent

rodo

com

ando

con

dici

onal

,mai

ste

mpo

para

ava

liar

aco

ndiç

ão,

que

éO

(1).

A

nel:

som

a do

tem

po d

eex

ecuç

ãodo

corp

odo

anel

mai

so

tem

po d

eav

alia

ra

cond

ição

par

a te

rmin

ação

(ger

alm

ente

O(1

)),m

ultip

licad

o pe

lo n

úmer

ode

itera

ções

.


An

álise

do

Tem

po

de

Execu

ção

P

roced

ime

nto

s n

ão

recu

rsiv

os:c

ada

umde

vese

rco

mpu

tado

sep

arad

amen

teum

a u

m,i

nici

ando

com

os q

ue

não

cham

am o

utro

pro

cedi

men

tos.

Ava

lia-s

een

tão

os q

ue

cham

am o

s já

aval

iado

s(u

tiliz

ando

os

tem

pos

dess

es).

Opr

oces

soé

repe

tido

até

cheg

arno

prog

ram

apr

inci

pal.

P

roced

imen

tos r

ecu

rsiv

os:a

ssoc

iada

um

a fu

nção

deco

mpl

exid

ade

f(n)

desc

onhe

cida

,ond

en

med

eo

tam

anho

dos

argu

men

tos.


Pro

cedi

men

to n

ão R

ecur

sivo

Alg

oritm

o pa

ra o

rden

ar o

sn

elem

ento

sde

um

conj

unto

Aem

ord

em a

scen

dent

e.

(1‏(

(2‏(

(3‏(

(4‏(

(5‏(

(6‏(

(7‏(

(8‏(

void

Ordena(VetorA)

/*ordenaovetorAem ordem ascendente*/

inti, j, min,x;

for(i = 1; i < n; i++)

m

in = i;

for(j = i + 1; j <= n; j++)

if( A[j -1] < A[m

in -1] )

min = j;

/*trocaA[m

in] e A[i]*/

x = A[m

in -1];

A[m

in -1] = A[i -1];

A[i -1] = x;


Pro

cedi

men

to n

ão R

ecur

sivo

S

elec

iona

om

enor

ele

men

todo

conj

unto

.

T

roca

est

eco

m o

prim

eiro

ele

men

toA

[1].

R

epita

asdu

as o

pera

ções

aci

ma

com

osn

-1

elem

ento

s re

stan

tes,

depo

isco

mos

n-

2,at

équ

e re

ste

apen

asum

.


Ane

l Int

erno

C

onté

mum

com

ando

dede

cisã

o, c

om u

mco

man

do a

pena

sde

atrib

uiçã

o. A

mbo

sle

vam

tem

poco

nsta

nte

para

ser

em e

xecu

tado

s.

Q

uant

o ao

cor

podo

com

ando

dede

cisã

o,de

vem

os c

onsi

dera

r o

pi

or c

aso,

assu

min

do q

ue s

erá

sem

pre

exec

utad

o.

O

tem

popa

ra in

crem

enta

ro

índi

cedo

anel

eav

alia

r su

a co

ndiç

ãode

term

inaç

ãoé

O(1

).

O

tem

poco

mbi

nado

par

a ex

ecut

ar u

ma

vez

oan

elé

O(m

ax(1

,1,1

))

= O

(1),

conf

orm

e re

gra

daso

ma

para

ano

taçã

oO

Com

o o

núm

ero

deite

raçõ

esé

n-

i, o

tem

poga

sto

noan

elé

O((

n-

i) x

1) =

O(n

-i),

conf

orm

e re

gra

dopr

odut

o pa

raa

nota

ção

O.

Aná

lise

doP

roce

dim

ento

não

Rec

ursi

vo


Ane

l Ext

erno

C

onté

m,a

lém

doan

el in

tern

o,qu

atro

com

ando

sde

atrib

uiçã

o.O

(max(1

,(n

-i),

1,1,

1))

= O

(n-

i).

A

linh

a(1

) é

exec

utad

an

-1

veze

s, e

o te

mpo

tota

lpar

a ex

ecut

aro

prog

ram

a es

tálim

itado

ao

prod

uto

deum

a co

nsta

nte

pelo

so

ma

tóri

ode

(n

-i):

S

e co

nsid

era

rmo

so

nú

mero

de

co

mp

ara

çõ

es c

omo

am

edid

ade

cust

o re

leva

nte,

opr

ogra

ma

faz

(n2 )

/2 -

n/2

com

para

ções

par

a or

dena

rn

elem

ento

s.

Se

cons

ider

arm

oso

núm

ero

detr

ocas

, opr

ogra

ma

real

iza

exat

amen

ten

-1

troc

as.

Aná

lise

doP

roce

dim

ento

não

Rec

ursi

vo


Alg

ori

tmo

sR

ec

urs

ivo

s


Co

nce

ito

de

Re

cu

rsiv

ida

de

F

unda

men

tal e

mM

atem

átic

a e

Ciê

ncia

da

Com

puta

ção

U

m p

rogr

ama

recu

rsiv

o é

um p

rogr

ama

que

cham

a a

si m

esm

o

Um

a fu

nção

rec

ursi

va é

defin

ida

em te

rmos

del

a m

esm

a

E

xem

plos

N

úmer

os n

atur

ais,

Fun

ção

fato

rial

C

once

ito p

oder

oso

D

efin

e co

njun

tos

infin

itos

com

co

ma

nd

os

finito

s


De

fin

içõ

es

C

ondi

ção

nece

ssár

ia e

suf

icie

nte

para

co

dific

ar p

rogr

amas

rec

ursi

vos

P

roce

dim

ento

s ou

sub

-rot

inas

P

roce

dim

ento

dire

tam

ente

rec

ursi

vo

Cha

ma

a si

mes

mo

P

roce

dim

ento

indi

reta

men

te r

ecur

sivo

A

cham

a B

que

cham

a A


Co

nd

içã

o d

e t

erm

ina

çã

o

N

enhu

m p

rogr

ama

nem

funç

ão p

ode

ser

excl

usiv

amen

te d

efin

ido

por

si

Um

pro

gram

a se

ria u

m lo

op in

finito

U

ma

funç

ão te

ria d

efin

ição

circ

ular

C

ondi

ção

de te

rmin

ação

P

erm

ite q

ue o

pro

cedi

men

to p

are

de e

xecu

tar

F

(x)

> 0

ond

e x

éde

cres

cent

e


Imp

lem

en

taç

ão

de

Rec

urs

ivid

ad

e

U

sa-s

eum

a p

ilh

a p

ara

arm

aze

na

r o

sd

ad

os

usad

os

em c

ada

cham

ada

de u

mpr

oced

imen

to q

ue a

inda

não

te

rmin

ou.

T

odos

os

dado

snã

o gl

obai

s vã

o pa

raa

pilh

a,re

gist

rand

oo

esta

do c

orre

nte

da c

ompu

taçã

o.

Q

uand

o um

a at

ivaç

ãoan

terio

rpr

osse

gue,

osda

dos

da p

ilha

são

recu

pera

dos.


Su

má

rio

E

xem

plos

sim

ples

de

reco

rrên

cia

mat

emát

ica

U

tiliz

ação

não

prá

tica

U

so p

rátic

o

Div

idir

Par

a C

onqu

ista

r!

R

emoç

ão d

a re

curs

ivid

ade

U

tiliz

ação

de

pilh

a ex

plíc

ita


Fu

nçã

o f

ato

ria

l

F

unçã

o fa

toria

l

N

! = N

x (

N –

1)!

N

> 0

, 0! =

1

intfatorial(intN)

if (N == 0) return1;

else returnN * fatorial(N –1);


An

ális

e d

a f

un

ção

fa

tori

al

C

ompl

exid

ade

de te

mpo

O

(n)

C

ompl

exid

ade

de e

spaç

o

O(n

)!!! intfatorial(intN)

int i, fat;

fat = 1;

for (i = 2; i <= N; i++) fat = fat * i;

return fat;


Se

qu

ên

cia

de

Fib

on

ac

ci

D

efin

ição

F

n=

Fn-

1+

Fn-

2n

> 2

, F0

= F

1=

1

1, 1

, 2, 3

, 5, 8

, 13,

21,

34,

55,

89.

..

intfibonacci(int N)

if (N < 2) return 1;

else return fibonacci(N –1) + fibonacci(N –2);


An

ális

e d

a f

un

ção

Fib

on

acci

E

xem

plo

aind

a m

enos

convin

cente

N

ão u

se r

ecur

sivi

dade

ceg

amen

te

In

efic

iênc

ia e

m F

ibon

acci

T

erm

os F

n-1

e F

n-2

são

com

puta

dos

inde

pend

ente

men

te

Cus

to p

ara

cálc

ulo

de F

n

O(φ

n ) o

nde

φ=

(1

+ √

5)/2

= 1

,618

03...

G

old

en

ra

tio

E

xpon

enci

al!!!


Alt

ern

ati

va

pa

ra f

ibo

nac

ci

intfibonacci(intN)

intt1, t2, cnt, aux;

if (N < 2) return1;

else

t1 = 1; t2 = 1; cnt = 2;

while (cnt < N)

aux = t1 + t2;

t2 = t1; t1 = aux;

cnt = cnt + 1;

returnt1;

Ve

rsã

o ite

rati

va

do

Cálc

ulo

de

Fib

on

ac

ci

O

prog

ram

ate

mco

mpl

exid

ade

de te

mpo

O(n

) e

com

plex

idad

ede

espa

çoO

(1).

D

evem

os e

vita

r us

ode

recu

rsiv

idad

e qu

ando

exi

ste

solu

ção

óbvi

a po

r ite

raçã

o.

C

ompa

raçã

o ve

rsõe

s re

curs

iva

eite

rativ

a:


Qu

an

do

Não

Us

ar

Re

cu

rsiv

ida

de

N

em to

do p

robl

ema

dena

ture

za r

ecur

siva

dev

ese

rre

solv

ido

com

um

algo

ritm

o re

curs

ivo.

E

stes

pode

mse

rca

ract

eriz

ados

pel

o es

quem

a

P ≡

if B

th

en

(S

; P

)

T

ais

prog

ram

as s

ão fa

cilm

ente

tran

sfor

máv

eis

em

uma

vers

ão n

ão r

ecur

siva

P ≡

(x :=

x0;

wh

ile B

do

S)



Pro

ble

ma

s c

om

re

cu

rsiv

idad

e

P

rogr

ama

recu

rsiv

o x

Fun

ção

defin

ida

recu

rsiv

amen

te

R

elaç

ão m

ais

filos

ófic

a do

que

prá

tica

P

robl

emas

de

impl

emen

taçã

o

Não

com

o c

once

ito d

e re

curs

ivid

ade


Div

idir

pa

ra C

on

qu

ista

r

D

uas

cham

adas

rec

ursi

vas

C

ada

uma

reso

lven

do a

met

ade

do p

robl

ema

M

uito

usa

do n

a pr

átic

a

Sol

ução

efic

ient

e de

pro

blem

as

Dec

ompo

siçã

o

N

ão s

e re

duz

triv

ialm

ente

com

o fa

toria

l

Dua

s ch

amad

as r

ecur

siva

s

N

ão p

rodu

z re

com

puta

ção

exce

ssiv

a co

mo

fibon

acci

P

orçõ

es d

ifere

ntes

do

prob

lem

a


Ex

em

plo

sim

ple

s:

rég

ua

voidregua(int l, int r,int h)

int m;

if (h > 0)

m = (int) ((l + r) /2);

marca(m, h);

regua(l, m, h –1);

regua(m, r, h –1);


Ex

ec

uç

ão

: ré

gu

aregua(0, 8, 3)

marca(4, 3)

regua(0, 4, 2)

marca(2, 2)

regua(0, 2, 1)

marca(1, 1)

regua(0, 1, 0)

regua(1, 2, 0)

regua(2, 4, 1)

marca(3, 1)

regua(2, 3, 0)

regua(3, 4, 0)

regua(4, 8, 2)

marca(6, 2)

regua(4, 6, 1)

marca(5, 1)

regua(4, 5, 0)

regua(5, 6, 0)

regua(6, 8, 1)

marca(7, 1)

regua(6, 7, 0)

regua(7, 8, 0)


Ou

tro

s e

xem

plo

s d

e r

ec

urs

ivid

ad

e

voidestrela(int x, y, r)

if (r > 0)

estrela(x-r, y+r, r /2);

estrela(x+r, y+r, r /2);

estrela(x-r, y-r, r /2);

estrela(x+r, y-r, r /2);

box(x, y, r);


Fra

cta

is

R

ecur

sivi

dade

sim

ples

pod

e le

var

a co

mpu

taçõ

es a

pare

ntem

ente

mui

to

com

plex

as

Pad

rões

geo

mét

ricos

def

inid

os

recu

rsiv

amen

te

Fra

cta

is

P

adrõ

es s

urpr

eend

ente

men

te d

iver

sific

ados

po

dem

ser

obt

idos

P

rimiti

vas

de d

esen

ho m

ais

sofis

ticad

as

Fun

ções

rec

ursi

vam

ente

def

inid

as c

om r

eais

e n

o pl

ano

com

plex

o


Ou

tro

s e

xem

plo

s:

frac

tais


Fin

aliza

nd

o

R

ecur

sivi

dade

éum

tópi

co fu

ndam

enta

l

Alg

oritm

os r

ecur

sivo

s ap

arec

em n

a pr

átic

a m

uito

com

umen

te

Div

idir

e co

nqui

sta

éum

a té

cnic

a na

tura

lmen

te r

ecur

siva

par

a so

luçã

o de

pr

oble

mas

M

ais

recu

rsiv

idad

e no

nos

so fu

turo

... ;-

)


Pes

quis

a(n)

(1

)if

(n

< 1

)

(2)

‘ins

peci

one

elem

ento

’ete

rmin

e; els

e

(3)

para

cad

aum

dos

nel

emen

tos

‘ins

peci

one

el

emen

to’;

(4

)P

esqu

isa(

n/3)

;

Ana

lise

de C

ompl

exid

ade

deP

roce

dim

ento

Rec

ursi

vo


P

ara

cada

pro

cedi

men

to r

ecur

sivo

éas

soci

ada

uma

funç

ãode

com

plex

idad

ef(

n)

desc

onhe

cida

,ond

en

med

eo

tam

anho

dos

argu

men

tos

para

opr

oced

imen

to.

O

btem

os u

ma

equa

ção

dere

corr

ênci

a pa

raf(

n).

E

qu

aç

ão

de

rec

orr

ên

cia

:man

eira

dede

finir

uma

funç

ão p

or u

ma

expr

essã

o en

volv

endo

am

esm

a fu

nção

.Pro

cedi

men

to R

ecur

sivo


S

eja

T(n

)um

a fu

nção

deco

mpl

exid

ade

que

repr

esen

teo

núm

ero

dein

speç

ões

nos

nel

emen

tos

doco

njun

to.

O

cus

tode

exec

ução

das

linha

s(1

) e

(2)

éO

(1)

e o

da li

nha

(3)

éex

atam

ente

n.

U

sa-s

eum

a e

qu

açã

od

ere

co

rrê

nc

ia p

ara

dete

rmin

aro

nºde

cham

adas

rec

ursi

vas.

O

term

oT

(n)

ées

peci

ficad

o em

funç

ãodo

ste

rmos

an

terio

res

T(1

), T

(2),

... ,

T(n

-1)

.

Aná

lise

doP

roce

dim

ento

Rec

ursi

vo


T(n

) =

n +

T(n

/3);

T(1

) =

1 (

para

n =

1fa

zem

os u

ma

insp

eção

)

Por

exe

mpl

o:

T(3

) =

T(3

/3)

+ 3

= 4

,

T(9

) =

T(9

/3)

+ 9

= 1

3,

e as

sim

por

dia

nte.

P

ara

calc

ular

ova

lor

da fu

nção

seg

uind

oa

defin

ição

sã

o ne

cess

ário

sk

-1

pass

os p

ara

com

puta

ro

valo

rde

T(3

k).

Aná

lise

doP

roce

dim

ento

Rec

ursi

vo


S

ubst

itui-s

eos

term

osT

(k),

k<

n,a

téqu

e to

dos

os

term

osT

(k),

k>

1,t

enha

m s

ido

subs

tituí

dos

por

fórm

ulas

con

tend

o ap

enas

T(1

).

Exe

mpl

ode

Res

oluç

ãode

Equ

ação

deR

ecor

rênc

ia


A

dic

ion

an

do

la

do

ala

do

,te

mo

s

T(n

) =

n +

n(1

/3)

+ n

(1/3

2)

+ n

(1

/33)

+ ...

+ T

(n/3

/3.../3

)

qu

e r

ep

res

en

taa

so

ma

de

um

a s

éri

e g

eo

mé

tric

a

de

ra

zã

o1

/3,m

ult

iplic

ad

a p

or

n, e

ad

icio

nad

ad

e

T(n

/3/3

.../

3),

qu

eé

me

no

r o

u ig

ua

la

1.

Exe

mpl

ode

Res

oluç

ãode

Equ

ação

deR

ecor

rênc

ia


S

e de

spre

zarm

oso

term

oT

(n/3

/3.../

3),

quan

don

tend

e pa

ra in

finito

,ent

ão

S

eco

nsid

erar

mos

ote

rmo

T(n

/3/3

/3..

./3

)e

deno

min

arm

osx

onú

mer

ode

subd

ivis

ões

por

3 do

tam

anho

dopr

oble

ma,

entã

on

/3x=

1, e

n=

3x. L

ogo

x =

lo

g3

n

Exe

mpl

ode

Res

oluç

ãode

Equ

ação

deR

ecor

rênc

ia


L

em

bra

nd

o q

ue

T(1

) =

1te

mo

s

L

og

o, o

pro

gra

ma

do

exe

mp

loé

O(n

).

Exe

mpl

ode

Res

oluç

ãode

Equ

ação

deR

ecor

rênc

ia


void

Pes

quis

a(V

etor

A, i

nt e

sq, i

nt d

ir, C

have

ch)

in

t m;

if (e

sq <

dir)

m

= (

esq

+ d

ir)/2

;if

(A[m

].cha

ve =

= c

h) p

rintf(

“Ach

ou e

lem

ento

napo

s %

d!\n

”,m

);el

se if (A

[m].c

have

> c

h) P

esqu

isa(

A,e

sq,m

-1,c

h);

else

Pes

quis

a (A

,m+

1,di

r,ch

);

else

if (

A[e

sq].c

have

==

ch)

prin

tf(“A

chou

ele

men

to n

apo

s %

d!\n

”,es

q);

Exe

mpl

o 1


void

sor

t(V

etor

A, i

nt i,

j)

in

t k;

if (i

< j)

k

= (

(j -

i) +

1)

/ 3;

sort

(A,

i, i+

k-1)

;so

rt(A

, i+

k, i

+2k

-1);

sort

(A, i

+2k

, j);

mer

ge(A

, i, i

+k,

i+2k

, j);

// M

erge

inte

rcal

a su

bvet

ores

a c

usto

5n/

3 –2

Exe

mpl

o 2


void

Mis

terio

(in

tn; V

etor

A)

vo

idvi

sita

(in

t i, V

etor

A)

in

ti;

int j

; i=

1;

if

(i >

0)

w

hile

i <=

n)

fo

r (

j=1;

j<=

i; j+

+)

visi

ta(i,

A);

A[j]

:=T

RU

E;

i = i+

1;

visi

ta(i-

1,A

);

Exe

mpl

o 3

Documents

Livro “Projeto de Algoritmos” – Nívio Ziviani Capítulo 1 ... · AlgoritmoseEstruturade Dados II Tipos de Problemas na Análise de Algoritmos Análise de um algoritmo particular