计算机研究与发展
計算機研究與髮展
계산궤연구여발전
JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
2003年
5期
706-711
,共6页
等概分档%分档映射%分档排序%定位排序%分档查找
等概分檔%分檔映射%分檔排序%定位排序%分檔查找
등개분당%분당영사%분당배서%정위배서%분당사조
分析了"王向阳二次分档排序"的不足.给出了等概分档映射算法,对已知分布函数的n个任意数据,仅需遍历计算一次,就可以分为m档,实现档之间有序化(档内仍无序).令m≥n,可以使得每档数据量期望值不大于1,待排序序列已经接近有序化了,只需用很少的时耗即可完成档内排序,从而建立一个有序且等概分档的查找表.在此基础上,提出了分档定位查找算法,其优势是:①对于待查找的某个数,不需要进行"比较",而只要进行"计算",就可以直接在该查找表中确定一个数据"档"作为查找目标;②可以在该"档"范围内使用折半查找等高效查找;③适用于任意数据且数据量很大的查找表;④在避免了全程查找的同时也避免了"冲突"现象.
分析瞭"王嚮暘二次分檔排序"的不足.給齣瞭等概分檔映射算法,對已知分佈函數的n箇任意數據,僅需遍歷計算一次,就可以分為m檔,實現檔之間有序化(檔內仍無序).令m≥n,可以使得每檔數據量期望值不大于1,待排序序列已經接近有序化瞭,隻需用很少的時耗即可完成檔內排序,從而建立一箇有序且等概分檔的查找錶.在此基礎上,提齣瞭分檔定位查找算法,其優勢是:①對于待查找的某箇數,不需要進行"比較",而隻要進行"計算",就可以直接在該查找錶中確定一箇數據"檔"作為查找目標;②可以在該"檔"範圍內使用摺半查找等高效查找;③適用于任意數據且數據量很大的查找錶;④在避免瞭全程查找的同時也避免瞭"遲突"現象.
분석료"왕향양이차분당배서"적불족.급출료등개분당영사산법,대이지분포함수적n개임의수거,부수편력계산일차,취가이분위m당,실현당지간유서화(당내잉무서).령m≥n,가이사득매당수거량기망치불대우1,대배서서렬이경접근유서화료,지수용흔소적시모즉가완성당내배서,종이건립일개유서차등개분당적사조표.재차기출상,제출료분당정위사조산법,기우세시:①대우대사조적모개수,불수요진행"비교",이지요진행"계산",취가이직접재해사조표중학정일개수거"당"작위사조목표;②가이재해"당"범위내사용절반사조등고효사조;③괄용우임의수거차수거량흔대적사조표;④재피면료전정사조적동시야피면료"충돌"현상.
