資源描述：
《storing a sparse table with o(1) worst case access time》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。
1、StoringaSparseTablewithO(1)WorstCaseAccessTimeMICHAELL.FREDMANANDJ/~NOSKOMLOSUniversityofCaliforma,SanDtego,LaJolla,CahformaANDENDRESZEMERI3DIUntversttyofSouthCarohnaAbstract.Adatastructureforrepresentingasetofnitemsfromaumverseofmitems,whichusesspacen+o(n)andaccommodatesmembershipqueriesmc
2、onstanttimeisdescribed.Boththedatastructureandthequeryalgorithmareeasyto~mplement.CategoriesandSubjectDescriptors:E.1IDataStrncturesl:Tables;F.2.2[AnalysisofAlgorithmsandProblemComplexitYl:NonnumericalAlgorithmsandProblems--sortmgandsearchmgGeneralTerms:Algorithms,TheoryAdditzonalKeyWordsan
3、dPhrases:Hashing,complexity,sparsetables.1.IntroductionThefollowingsearchingproblemisconsidered.AsetSofndistinctnamesfromauniverseUofmpossiblenames(m>n)istobestoredinamemoryTinamannerpermittingefficientprocessingofmembershipqueriesoftheform,"IsqinS,andifso,thenwherecanitbefoundinT?."Weassum
4、ethatthesetSisstatic,sothatourmainconcernsarethestoragerequiredforSandthetimerequiredforprocessingqueries.HashingschemesprovideasolutiontothisproblemutilizingO(n)storageandpermittingqueriesin(9(1)averagetimeperquery.Inthispaper,weconcentrateontheworstcasetimerequiredforaquery,whileretaining
5、anO(n)boundonstorage.Thisquestionhasbeenconsideredinvariouspapers,forexample,[1]-[4].Yao[4]proposesaninterestingcomplexitymodelforthisproblem.InYao'sframework,SisasubsetofU={l,2.....mtofcardinalityn.ThememoryTstoresanitemfromUineachofitscells,andthesecellscanberandomlyaccessedbyaddress.Aque
6、ryforanelementqinUisprocessedbyprobingasequenceofcellsinT.Thissequenceofprobescanbeadaptive:TheThismaterialisbaseduponworksupportedinpartbyNationalSoenceFoundationGrantsMCS76-08543,MCS82-0403l,andMCS79-06228.Authors'Addresses:M.L.FredmanandJ.Komlrs,DepartmentofElectricalEngineeringandComput
7、erScience,UmversltyofCahfornia,SanDiego,MallCodeC-014,LaJolla,CA92093;E.Szemerrdi,MathematicalInstitute,PF428,1395Budapest,Hungary.PermissiontocopywithoutfeeallorpartofthismaterialIsgrantedprovidedthatthecopiesarenotmadeordistributedfordirectcommeroaladv
