资源描述：
《数据结构与算法分析c++版课件_2》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、数据结构与算法分析APracticalIntroductiontoDataStructuresandAlgorithmAnalysis2MathematicalPreliminaries2MathematicalPreliminariesSetconceptsandnotationLogarithmsSummationsandRecurrencesRecursionMthMathematitilPcalProoffThiTechniquesEstimation2SetsandRelationsSetsandRelations¢Set:Acollectionofdisti
2、nguishablemembersorelements.{2,3,5}x∈P¢Bag:Acollectionofelementswithnoorder(likeaset),butwithduplicate-valuedelements.[3,4,5,4]¢Sequence:Acollectionofelementswithanorder,andwhichmaycontainduplicate-valuedelements.<34543,4,5,4>¢ArelationRoversetSisasetoforderedpairsfromS.ßEx:ifSis{a,b,c},
3、then{,,}isarelation.SetsandRelationsSetsandRelations¢IftupleisinrelationR,wemayusetheinfixnotationxRy.¢DfithDefinethepropertitiesofltifrelationsasfllfollows,withRithRabinaryrelationoversetS.ßRisRisreflexiveifaRaforallaifaRaforalla∈S.ßRissymmetricifwheneveraRb,thenbRa,
4、foralla,b∈S.ßRisantisymmetricifwheneveraRbandbRa,thena=b,foralla,b∈S.ßRistransitiveifwheneveraRbandbRc,thenaRc,foralla,b,c∈S.5、quivalenceRelation¢RisanequivalencerelationonsetSifitisreflexive,symmetric,andtransitive.¢Anequivalencerelationcanbeusedtopartitionasetintoequivalenceclassespartitionasetintoequivalenceclasses.ßIftwoelementsaandbareequivalenttoeachotherwewriteabother,wewriteab.ßApartitionofasetSisacollec
6、tionofsubsetsthtthataredijitdisjointfhfromeachoththeranddwhhoseunionisS.EquivalenceRelationEquivalenceRelation¢Example2.1Fortheintegg,ers,=isaneqquivalencerelationthatpartitionseachelementintoadistinctsubset.Inotherwords,,ygforanyintegera,,threethingsaretrue.ßa=a,ßifa=bthenb=aßifa=bandb=
7、cthena=cifa=bandb=c,thena=c.MiscellaneousNotationMiscellaneousNotation¢Unitsofmeasure：ßBbKBMBGBßSpacesarenotplacedbetweenthenumberandtheunitabbreviationwhenapoweroftwoisintended.ßSpacesareusedwhenadecimalvalueisintended.¢2Kband2KbMiscellaneousNotationMiscellaneousNotation
