Complexite d'un algorithme

Mpsi1 - Lycée Thiers

Description

Introduction, Fonctions de complexité, Exemple

Informations

• Publié par: Force_IT
• Nombre de lectures: 48
• Licence : En savoir +
  Paternité, pas d'utilisation commerciale, partage des conditions initiales à l'identique
• Langue: Français
• Poids de l'ouvrage: 1 Mo

Extrait

Cours 8 :
Complexit´ed’unalgorithme

MPSI1-Lyc´eeThiers

2013/2014

Introduction

Fonctionsdecomplexite´

Exemple

Introduction
Fonctionsdecomplexite´
Exemple

MPSI1-Lyce´eThiers

Cours8:Complexit´ed’unalgorithme

Introduction
Fonctionsdecomplexite´
Exemple

Pourbienprogrammer,ilfautd’abord´eviterleserreursdesyntaxe,e´crireducodeclair,bien
comment´e,de´composersonprogrammeenfonctions,ete´ventuellementlesregrouperdansdes
modulesquel’onpourrar´e-employer.
Maisunbonprogrammedoitsurtoutappliquerlesbonsalgorithmes.Defa¸con´evidentecertains
algorithmes seront meilleurs que d’autres.
Exemple:Ecrireenpythonunefonctionquiprendenargumentunechaˆınedecaract`ereet
d´eterminesilecaracte`re’a’estpre´sentdanslachaˆıne.Analysonsplusieurssolutions.

MPSI1-Lyc´eeThiers

Cours8:Complexit´ed’unalgorithme

Introduction
Fonctionsdecomplexite´
Exemple

Ylusoontimirere`eP:
def contienta(chaine):
k = 0; N = len(chaine)
result = False
while (result == False and k < N)
if chaine[k] == ’a’:
result = True
k += 1
return result
Ylaog’L`ateisnscomethriaracselriruocraptce`erdslecaahıˆnetantqu’onn’apaortse´vuel
caract`ere’a’.Ler´esultateststocke´dansunevariableboole´ennevalantinitialementFalseet
passant`aTrue`tcaereleuqraceesd`’a’est lu.
Yruednargederdroeemmˆdusteemmraogneecucrrreocmi`eaprequelitnoudrp’dxee´ucLetemps
de ’a’ dans la chaine. Il existe des constantesaetbe´po’dnosnoitartempsd’´ex´ecuti,´dpeneadtnud
e´l´ementaires,commel’affectationoul’incr´ementation,telsquesikesteeri`rpmeedalidec’lni
occurrence de’a’danschaineex´ecutietempsd’l,noesara.k+b.
YPour des chaines de tailleNspmexe’dtel,itnoe´ucualpesarusa.N+b`tcarace’a’ere(quellors
estabsentoupre´sentendernie`replace).C’estletempsd’ex´ecutiondanslepiredescaspourdes
entr´eesdetailleN´nilicitselI.mueliensqeauseairN(∞(a.N+b)~Nest finie et non-nulle (donc
limN(∞N~(a.N+b)est aussi finie).
YPour des chaines de tailleNtinfemeneur`´eriyoneeamnirtcentsecx´’esdernsioutapmetel,
a
a.N+b.rlIavtuciifficdie`ilalaclecui.tselsulp.N+b:eneffetlapremi`ereoccurrencede’a’
2
a(pouruneloideprobabilit´euniforme)autantdechanced’apparaıˆtrea`lapositioniqu’a la
positionN-iasymptotmesens:’nalsmeeˆe´iaerd(euqi.)’tseellE.nilissua..

MPSI1-Lyc´eeThiers

Cours8:Complexit´ed’unalgorithme

Introduction
Fonctionsdecomplexit´e
Exemple

YDeuxinoit:eme`ulos
def contienta(chaine):
n = chaine.count(’a’)
return bool(n)
Y! Est-il meilleur?Le code est plus court
Yecaract`ereOnmpcoletebmonedersioflu`o’a’aparıˆdtnasapchainee´malededia’la`eodth
.count()tneiqeeust´sboejcesstn´elfauls.Iesderilsuoteriatnemert`deesscleacarchaine, donc
pour n’importe quelle chaˆıne de longueurNnuetpmdsliafduaremrondioafelx´’eutecc.N+d
pour des constantescetb.
YcssaeredelipaDsnriae´nilerocnetslecualecsdmpteleailledesdonn´eeseefnnotcoidnleta.
Ymriae´osisassueet´oynmneentdesaMalsipmocixelc.N+dElle.itme´etat.aeruellinavarapu
YPour de grandes valeurs deN,cst’entdeedrunodsida`operrandetain´eesdegpe´rcee´ll,eonrt
programme devrait en moyenne deux fois plus rapide.
Y:noilotumesesi`iTor
def contienta(chaine):
return (’a’ in chaine)
YaM.truocpmetelsiecx´’esdnmneioutenteyoneelipadsnscasredepourLceodeestencoreplus
uneentre´edetailleNn´eaire.lit´e,liauqederdroemeˆme,dlempxeeeeri`emelrpadsnmoemrecas
L’utilisationdefonctionspr´eprogramme´esspe´cifiquesam´elioreletempsd’ex´ecution.Maisicice
sont les constantesaetbqu.L’instructionsinoottpmisie´seinl´´eenemdetslaepenuqturilesele
chainel’unapre`sl’autretantqu’ellen’apastrouve´’a’,puisqu’iln’yaaucunmoyendesavoira`
priori si’a’figure danschaine.
L’algorithmeemploy´eestd’aussibonnequalit´equedanslapremie`resolution.Onnepeutpasfaire
mieux.

MPSI1-Lyc´eeThiers

Cours8:Complexit´ed’unalgorithme

Introduction
Fonctionsdecomplexit´e
Exemple

Yenevrriaarmmsenodeuxprogutiondese’lAce´xurngueoledseniahcsedrupoceenerff´dinetu
petite, qu’en la mesurant (%timeitou moduletimeex´e),l’on´ecutisauqtnatnatsni-i.Peen´taar
contrepourdeschainesdetr`esgrandeslongueursonpourraitpercevoirunediff´erence,etune
relativelenteurdeladeuxie`mesolutionparrapportauxdeuxautres.
Yogolor´e,ienargse`rte´M:sedDenombreemisfnroxuystse`nimaleputimaesquee´ntedsedtnnods
gestiondutraficae´rien,statistiquesdelapopulation,traitementd’image,serveurs,re´seausociaux,
etc...
YSoitNmaxsee´nnodsedelamiaxemllaiatlmaemorrgu’pnoidnecut’ex´quelpourteexs’cu´e
efficacementdansuntempsd’ex´ecutionacceptable.Dequellecapacit´einformatiquefaudrait-ilse
doterpourdoublerlacapacite´detraitement2Nmax, pour la multiplier par 10 : 10Nmax?
Ya’liSy´lompeehmitorlgeauntempsd’ex´ectuoilnnie´iaer,a.N+b≈a.N, il suffit
approximativement respectivement de doubler, ou de multiplier par 10 son parc informatique en
pratiquantducalculenparall`ele,ouparalle´lisme.
2 2
YrithmeemSil’algoeituqraadquonticu´eex’dspmetnuae´yolpa.N+b.N+c≈a.N, il suffit de
multiplier approximativement son parc informatique par 4, ou 100!
N
Ylpexemeonennexp,partiele’dspmetoituce´xmpeehmituneay´loSlia’glroa.veref´ltluea2rdiia
lescapacit´esduparcinformatiqueaucarre´,ou`alapuissance10.
N2N2 10N10
max maxmax
En effet :2DKmaxÔ⇒2DKet 2DK.
max max
C’estpourquoiunesolutionalgorithmedecomplexite´detempsdecalcullin´eaireenfonctiondela
tailledesdonne´espre´sentedeconside´rablesavantagesparrapporta`unesolutiondecomplexite´
quadratique, pire : exponentielle, etc...

MPSI1-Lyc´eeThiers

Cours8:Complexit´ed’unalgorithme

Introduction
Fonctionsdecomplexite´
Exemple

Comparonslestempsd’ex´ecutionsurunordinateur`a10GHz(10milliardsd’ope´rations`ala
seconde)danslepiredescaspourdiverstaillesdedonne´esetdiffe´rentesfonctiondecomplexite´s.
Latailledesdonne´esestN.
N=20N=50N=100N=200
1000.N0.002s 0.005s0.01s 0.02s
2
100.N0.004s 0.025s0.1s 0.4s
3
10.N0.002s 0.1s 1s6s
N
20.1s3.6anne´es--
N10
3 5.8min. 2.a0e´nn--se1
Nan10een´--s-77!
-:sup´erieur`a100milliardsd’anne´es

MPSI1-Lyc´eeThiers

Cours8:Complexit´ed’unalgorithme

Introduction
Fonctionsdecomplexit´e
Exemple

YOneuqsatalvas’pliupuoonn,nl´eeteesmneislelnetdaetsiduseersrepbet´rro´mnueee´aiprlurq
d’exe´cutiondel’additionde2nombres,deleurmultiplication,etc...,sontborne´sparuneconstante
d´ependantdelamachineetdel’interpr´eteur.Ilenestdemˆemesil’oneffectuen’importequelle
ope´rationmathe´matiquesusuelle,commeprendreunepuissance,uneracinecarr´ee,etc...
Y:nare´poselsetuotsteanstsionscontipoe´aritanppleelmentaireons´el´eO
1.arsimoapnuceeop´t,unnteson,uaternlioiqog,ue
2.ithm´etique,unefnotcoimnta´hmetas,ueiqenue´poitarrano
3.ructnestedonuredl(si´neeahnietc,esc`acl’´le´nua`u’dtneme,sation´raes,ca.c).,ete
modification,
4.l’affectation de variable,
5.unedonn´retourd’erssoi/nsieii/pmr.iesuanchnfinarcduo,a`eee´’lsa
6.e´eonn´eedetaillefixToaritpoe´e´´dnorpnstruteionouuctinautceffedenurustbae,niefis’e,qusi
parlesyste`me,etdontletempsd’exe´cutionestmajore´paruneconstantened´ependantque
dusyste`me.
YPar exemple :
1.nemeua`tnure´le´unstp´eolineeestlee´emtnretaoi´njoutAaire.
2.laurnncot`aiaecalculdLguonalelne’urdeutseetsilre´poenun´elationtai´emei’tnerl(e´etrerp
priorioulade´duitdesadressesdespremiersetdernierse´le´ments).
3.Les instructionsliste.count(’a’)ousum(liste)erp´sodeeln´ioatiatneme´.sernsenoptsa
Leurtempsd’ex´ecutionde´penddelalongueurdeliste.

MPSI1-Lyce´eThiers

Cours8:Complexite´d’unalgorithme

Introduction
Fonctionsdecomplexit´e
Exemple

Ysdetn´eeeaillepprmumnroauomgeetnhnrtingaoraeltneu`em´