算法设计与分析基础第三版ch06

TransformandConquerThisgroupoftechniquessolvesaproblembyatransformationto

asimpler/moreconvenientinstanceofthesameproblem(instancesimplification)

adifferentrepresentationofthesameinstance(representationchange)

adifferentproblemforwhichanalgorithmisalreadyavailable(problemreduction)

1精选pptInstancesimplification-PresortingSolveaproblem’sinstancebytransformingitintoanothersimpler/easierinstanceofthesameproblemPresortingManyproblemsinvolvinglistsareeasierwhenlistissorted,e.g.searchingcomputingthemedian(selectionproblem)checkingifallelementsaredistinct(elementuniqueness)

Also:Topologicalsortinghelpssolvingsomeproblemsfordags.Presortingisusedinmanygeometricalgorithms.2精选pptHowfastcanwesort?Efficiencyofalgorithmsinvolvingsortingdependsonefficiencyofsorting.Theorem(seeSec.11.2):log2n!nlog2ncomparisonsarenecessaryintheworstcasetosortalistofsizenbyanycomparison-basedalgorithm.

Note:Aboutnlog2ncomparisonsarealsosufficienttosortarrayofsizen(bymergesort).3精选pptSearchingwithpresortingProblem:SearchforagivenKinA[0..n-1]

Presorting-basedalgorithm: Stage1SortthearraybyanefficientsortingalgorithmStage2ApplybinarysearchEfficiency:Θ(nlogn)+O(logn)=Θ(nlogn)Goodorbad?Whydowehaveourdictionaries,telephonedirectories,etc.sorted?

4精选pptElementUniquenesswithpresortingPresorting-basedalgorithmStage1:sortbyefficientsortingalgorithm(e.g.mergesort)Stage2:scanarraytocheckpairsofadjacentelementsEfficiency:Θ(nlogn)+O(n)=Θ(nlogn)

Bruteforcealgorithm

Compareallpairsofelements

Efficiency:O(n2)

Anotheralgorithm?Hashing5精选pptInstancesimplification–GaussianEliminationGiven:Asystemofnlinearequationsinnunknownswithanarbitrarycoefficientmatrix.

Transformto:Anequivalentsystemofnlinearequationsinnunknownswithanuppertriangularcoefficientmatrix.

Solvethelatterbysubstitutionsstartingwiththelastequationandmovinguptothefirstone.

a11x1+a12x2+…+a1nxn=b1

a1,1x1+a12x2+…+a1nxn=b1

a21x1+a22x2+…+a2nxn=b2

a22x2+…+a2nxn=b2

an1x1+an2x2+…+annxn=bn annxn=bn

精选pptGaussianElimination(cont.)Thetransformationisaccomplishedbyasequenceofelementaryoperationsonthesystem’scoefficientmatrix(whichdon’tchangethesystem’ssolution):

for

i←1ton-1do

replaceeachofthesubsequentrows(i.e.,rowsi+1,…,n)by

adifferencebetweenthatrowandanappropriatemultiple

ofthei-throwtomakethenewcoefficientinthei-th

column

ofthatrow0

精选pptExampleofGaussianEliminationSolve2x1-4x2+x3=6

3x1-x2+x3=11

x1+x2-x3=-3

Gaussianelimination2

-4

162

-4

1

63-1111row2–(3/2)*row105-1/2211-1

-3row3–(1/2)*row103-3/2-6row3–(3/5)*row2

2

-4

1

605-1/2200-6/5-36/5

Backwardsubstitutionx3=(-36/5)/(-6/5)=6

x2=(2+(1/2)*6)/5=1

x1=(6–6+4*1)/2=2精选pptPseudocodeandEfficiencyofGaussianEliminationStage1:Reductiontoanupper-triangularmatrixfor

i←1to

n-1dofor

j←i+1to

ndo

for

k←ito

n+1do

A[j,k]←A[j,k]-A[i,k]*A[j,i]/A[i,i]//improve!

Stage2:Backsubstitutions

for

j←ndownto1do

t←0

for

k←j+1

to

ndo

t←t+A[j,k]*x[k]

x[j]←(A[j,n+1]-t)/A[j,j]

Efficiency:Θ(n3)+Θ(n2)=Θ(n3)

精选pptSearchingProblemProblem:Givena(multi)setSofkeysandasearch

keyK,findanoccurrenceofKinS,ifany

Searchingmustbeconsideredinthecontextof:filesize(internalvs.external)dynamicsofdata(staticvs.dynamic)Dictionaryoperations(dynamicdata):find(search)insertdelete10精选pptTaxonomyofSearchingAlgorithmsListsearchingsequentialsearchbinarysearchinterpolationsearchTreesearchingbinarysearchtreebinarybalancedtrees:AVLtrees,red-blacktreesmultiwaybalancedtrees:2-3trees,2-3-4trees,BtreesHashingopenhashing(separatechaining)closedhashing(openaddressing)11精选pptBinarySearchTreeArrangekeysinabinarytreewiththebinarysearchtreeproperty:K<K>KExample:5,3,1,10,12,7,912精选pptDictionaryOperationsonBinarySearchTreesSearching–straightforwardInsertion–searchforkey,insertatleafwheresearchterminatedDeletion–3cases:deletingkeyataleafdeletingkeyatnodewithsinglechilddeletingkeyatnodewithtwochildrenEfficiencydependsofthetree’sheight:log2nhn-1,

withheightaverage(randomfiles)beabout3log2nThusallthreeoperationshave

worstcaseefficiency:(n)averagecaseefficiency:(logn)

Bonus:inordertraversalproducessortedlist13精选pptBalancedSearchTreesAttractivenessofbinarysearchtreeismarredbythebad(linear)worst-caseefficiency.Twoideastoovercomeitare:

torebalancebinarysearchtreewhenanewinsertion

makesthetree“toounbalanced”

AVLtrees

red-blacktrees

toallowmorethanonekeypernodeofasearchtree

2-3trees

2-3-4trees

B-trees

14精选pptBalancedtrees:AVLtreesDefinitionAnAVLtreeisabinarysearchtreeinwhich,foreverynode,thedifferencebetweentheheightsofitsleftandrightsubtrees,calledthebalancefactor,isatmost1(withtheheightofanemptytreedefinedas-1)

Tree(a)isanAVLtree;tree(b)isnotanAVLtree15精选pptRotationsIfakeyinsertionviolatesthebalancerequirementatsomenode,thesubtreerootedatthatnodeistransformedviaoneofthefourrotations.(Therotationisalwaysperformedforasubtreerootedatan“unbalanced”nodeclosesttothenewleaf.)SingleR-rotationDoubleLR-rotation16精选pptGeneralcase:SingleR-rotation17精选pptGeneralcase:DoubleLR-rotation18精选pptAVLtreeconstruction-anexampleConstructanAVLtreeforthelist5,6,8,3,2,4,7

19精选pptAVLtreeconstruction-anexample(cont.)

20精选pptAnalysisofAVLtreesh

1.4404log2(n+2)-1.3277averageheight:1.01log2n+0.1forlargen(foundempirically)

SearchandinsertionareO(logn)

DeletionismorecomplicatedbutisalsoO(logn)

Disadvantages:frequentrotationscomplexity

Asimilaridea:red-blacktrees(heightofsubtreesisallowedtodifferbyuptoafactorof2)21精选pptMultiwaySearchTreesDefinitionAmultiwaysearchtreeisasearchtreethatallows

morethanonekeyinthesamenodeofthetree.DefinitionAnodeofasearchtreeiscalledann-nodeifitcontainsn-1orderedkeys(whichdividetheentirekeyrangeintonintervalspointedtobythenode’snlinkstoitschildren):

Note:Everynodeinaclassicalbinarysearchtreeisa2-node

k1<k2

<…<kn-1<k1[k1,k2

)

kn-122精选ppt2-3TreeDefinitionA2-3treeisasearchtreethatmayhave2-nodesand3-nodesheight-balanced(allleavesareonthesamelevel)

A2-3treeisconstructedbysuccessiveinsertionsofkeysgiven,withanewkeyalwaysinsertedintoaleafofthetree.Iftheleafisa3-node,it’ssplitintotwowiththemiddlekeypromotedtotheparent.23精选ppt2-3treeconstruction–anexampleConstructa2-3treethelist9,5,8,3,2,4,7

24精选pptAnalysisof2-3treeslog3(n+1)-1h

log2(n+1)-1Search,insertion,anddeletionarein(logn)

Theideaof2-3treecanbegeneralizedbyallowingmorekeyspernode2-3-4treesB-trees

25精选pptHeapsandHeapsortDefinition

Aheapisabinarytreewithkeysatitsnodes(onekeypernode)suchthat:Itisessentiallycomplete,i.e.,allitslevelsarefullexceptpossiblythelastlevel,whereonlysomerightmostkeysmaybemissingThekeyateachnodeis≥keysatitschildren26精选pptIllustrationoftheheap’sdefinitionaheapnotaheapnotaheapNote:Heap’selementsareorderedtopdown(alonganypath

downfromitsroot),buttheyarenotorderedlefttoright27精选pptSomeImportantPropertiesofaHeapGivenn,thereexistsauniquebinarytreewithnnodesthatisessentiallycomplete,withh=log2n

TherootcontainsthelargestkeyThesubtreerootedatanynodeofaheapisalsoaheap

Aheapcanberepresentedasanarray28精选pptHeap’sArrayRepresentationStoreheap’selementsinanarray(whoseelementsindexed,forconvenience,1ton)intop-downleft-to-rightorderExample:Leftchildofnodejisat2jRightchildofnodejisat2j+1Parentofnodejisatj/2Parentalnodesarerepresentedinthefirstn/2locations91534212345695314229精选pptStep0:InitializethestructurewithkeysintheordergivenStep1:Startingwiththelast(rightmost)parentalnode,fixtheheaprootedatit,ifitdoesn’tsatisfytheheapcondition:keepexchangingitwithitslargestchilduntiltheheap

conditionholds

Step2:RepeatStep1fortheprecedingparentalnodeHeapConstruction(bottom-up)30精选pptExampleofHeapConstructionConstructaheapforthelist2,9,7,6,5,831精选pptPseudopodiaofbottom-upheapconstruction32精选pptStage1:ConstructaheapforagivenlistofnkeysStage2:Repeatoperationofrootremovaln-1times:Exchangekeysintherootandinthelast(rightmost)leafDecreaseheapsizeby1Ifnecessary,swapnewrootwithlargerchilduntiltheheapconditionholdsHeapsort33精选pptSortthelist2,9,7,6,5,8byheapsortStage1(heapconstruction) Stage2(root/maxremoval)197658 968257298657 76825|9

298657 86725|9928657 5672|89968257 7652|89 265|789

625|789

52|6789

52|6789 2|56789ExampleofSortingbyHeapsort34精选pptStage1:Buildheapforagivenlistofnkeysworst-case

C(n)=

Stage2:Repeatoperationofrootremovaln-1times(fixheap)worst-case

C(n)=

Bothworst-caseandaverage-caseefficiency:(nlogn)

In-place:yes

Stability:no(e.g.,11)

2(h-i)2i=2(n–log2(n+1))

(n)i=0h-1#nodesatlevelii=1n-1

2log2i(nlogn)

AnalysisofHeapsort35精选pptApriorityqueueistheADTofasetofelementswithnumericalprioritieswiththefollowingoperations:findelementwithhighestprioritydeleteelementwithhighestpriorityinsertelementwithassignedpriority(seebelow)Heapisaveryefficientwayforimplementingpriorityqueues

Twowaystohandlepriorityqueueinwhich

highestpriority=smallestnumberPriorityQueue36精选pptInsertionofaNewElementintoaHeapInsertthenewelementatlastpositioninheap.Compareitwithitsparentand,ifitviolatesheapcondition,

exchangethemContinuecomparingthenewelementwithnodesupthetreeuntiltheheapconditionissatisfiedExample:

Insertkey10Efficiency:O(logn)37精选pptHorner’sRuleForPolynomialEvaluationGivenapolynomialofdegreen p(x)=anxn+an-1xn-1+…+a1x+a0andaspecificvalueofx,findthevalueofpatthatpoint.Twobrute-forcealgorithms:p

0 p

a0;power

1fori

n

downto0

do fori1tondopower

1 power

power*xforj

1toido p

p+ai*power

power

power*xreturnp

p

p+ai

*powerreturnp38精选pptHorner’sRule

Example:p(x)=2x4-x3+3x2+x-5==x(2x3-x2+3x+1)-5= =x(x(2x2-x+3)+1)-5= =x(x(x(2x-1)+3)+1)-5SubstitutionintothelastformulaleadstoafasteralgorithmSamesequenceofcomputationsareobtainedbysimply

arrangingthecoefficientinatableandproceedingasfollows: coefficients 2 -1 3 1 -5

x=3

39精选pptHorner’sRulepseudocodeEfficiencyofHorner’sRule:#multiplications=#additions=n

Syntheticdivisionofofp(x)by(x-x0)

Example:Letp(x)=2x4-x3+3x2+x-5.Findp(x):(x-3)

40精选pptComputingan(revisited)Left-to-rightbinaryexponentiation

Initializeproductaccumulator

by1.Scann’sbinaryexpansionfromlefttorightanddothefollowing:Ifthecurrentbinarydigitis0,squaretheaccumulator(S);

ifthebinarydigitis1,squaretheaccumulatorandmultiplyitbya(SM).Example:Computea13.Here,n=13=11012

binaryrep.of13:11 01

SMSM